בעיה מעניינת

[אוהבת גרפיקה]

נתונה לי הבעיה הבאה:
בכמה מחרוזות טרינאריות באורך n, כלומר מעל הקבוצה {0,1,2} יש מספר זוגי של 1-אים?
כלומר לדוגמא אם מסתכלים על n=3 אז יש את המחרוזת 002 שבה 0 1-אים אז היא נספר לעומת זאת המחרוזת 010 לא נספרת,
פתרון במתמטיקה הוא 0.5 כפול (3 בחזקת n ועוד 1) סליחה פשוט לא הצלחתי להקליד את הביטוי.
בקיצור, אני רוצה לכתוב קוד שיבדוק את זה נניח מn שווה 4 עד 20.
יש למישהו רעיון איך?

 

[יהודיה נחמדה :)]

נתונה לי הבעיה הבאה:
בכמה מחרוזות טרינאריות באורך n, כלומר מעל הקבוצה {0,1,2} יש מספר זוגי של 1-אים?
כלומר לדוגמא אם מסתכלים על n=3 אז יש את המחרוזת 002 שבה 0 1-אים אז היא נספר לעומת זאת המחרוזת 010 לא נספרת,
פתרון במתמטיקה הוא 0.5 כפול (3 בחזקת n ועוד 1) סליחה פשוט לא הצלחתי להקליד את הביטוי.
בקיצור, אני רוצה לכתוב קוד שיבדוק את זה נניח מn שווה 4 עד 20.
יש למישהו רעיון איך?

זה בסדרות??

 

[אוהבת גרפיקה]

זה בסדרות??

השאלה היא לא על הפתרון אלא על איך לכתוב את הקוד..
שיתן לי מספר ממש, נניח כמה מחרוזות באורך 19 תווים (0,1,2) יש עם מספר זוגי של 1אים..

 

[gt12]

אם יש לך נוסחה מתמטית מה הבעיה לכתוב קוד שיחשב את הנוסחה?

 

[אוהבת גרפיקה]

אם יש לך נוסחה מתמטית מה הבעיה לכתוב קוד שיחשב את הנוסחה?

כנראה לא הייתי ברורה מספיק.
אני חישבתי את הנוסחה ורציתי לבדוק אותה אם היא באמת מתקיימת, בידיים זה לא כל כך אפשרי משלב מסוים, אז רציתי לכתב קוד כזה.. על מקרים ספציפיים..

 

[s976]

באיזו שפה?

 

[s976]

ועוד 1

למה?

 

[אוהבת גרפיקה]

למה?

זה די מסובך להסביר, פתרון בפונקציות יוצרות אם את מכירה.

באיזו שפה?

לא משנה האמת, רק הרעיון הכללי..
כלומר איך ליצר את כל המספרים האפשרים באורך n המורכבים מ1 2 ו0.

 

[s976]

זה די מסובך להסביר, פתרון בפונקציות יוצרות אם את מכירה.

מכיר. כן
אבל אני לא בטוח שצריך את זה כאן.
לכל סדרה יש רק שתי אפשרויות: או שמספר של 1 הוא זוגי או שהוא אי-זוגי
אם מספר האיברים הוא זוגי, אז הכל סימטרי וברור שמספר הקוצבינציות הזוגיות שוה לכמות האי-זוגיות (זה, מה שנקרא ״הוכחה עם נפנופי ידיים״. כלומר, כיוון, ולא הוכחה גמורה). ולכן התשובה היא:

(3^n)/2

אם מספר האיברים הוא זוגי, אז נראה שאת צודקת.

לא משנה האמת, רק הרעיון הכללי..
כלומר איך ליצר את כל המספרים האפשרים באורך n המורכבים מ1 2 ו0.

יש כמה אפשרויות. להלן אפשרות שלכאורה היא די יעילה

def add_one_at(arr, i):
    quo, rem = divmod(arr[i] + 1, 3)
    arr[i] = rem
    if quo > 0:
        arr = add_one_at(arr, i - 1)
    return arr


def iter_n(n):
    arr = [0] * n
    yield arr
    for i in range(n ** 3 - 1):
        arr = add_one_at(arr, len(arr) - 1)
        yield arr


counter = 0
cardinality = 14
for a in iter_n(cardinality):
    if a.count(1) % 2 == 0:
        counter += 1

print(counter)

 

[נסיון9876]

לטעמי, זה ממש צועק תכנות דינמי.
אז הייתי חייבת לנסות...
(אם לא נכון - אז זה רק בגלל השעה כמובן )
זו לכאורה הצורה הכי יעילה מבחינת זמן ריצה (ליניארי) אבל דורש הקצאת זכרון בגודל N

ניסיתי לכתוב קוד שיהיה ברור מה הרעיון. מקווה שהצלחתי.
ואם הקוד נכון הרי שהנוסחה שהצגת לא נכונה.

def dynamic_algo(n):
  A = [0] * (n+1)
  A[0] = 1
  num_of_sub_groups = 1 #3^0
  for i in range(1, n+1):
    A[i] = A[i-1]*2 #can add to previous group 0 or 2
    odd_previous = num_of_sub_groups - A[i-1]
    A[i] += odd_previous #must have now 1
    num_of_sub_groups *= 3
  return A[n]

print(dynamic_algo(n=4))

 

[נסיון9876]

בהמשך להודעה הקודמת. אם את רוצה לראות את האפשרויות בעין. את יכולה להריץ את הקוד הנל
(מניחה שיש דרכים יותר חכמות לבצע את כל הקצאות הזכרון, אבל למספרים קטנים זה בסדר)

import numpy as np
import sys
np.set_printoptions(threshold=sys.maxsize)

def dynamic_algo(n):
  A = [0] * (n+1)
  A[0] = 1
  A[1] = 2
  options = np.array([[0],[2]])
  no_options = np.array([1])
  n_all_options = 3 #3^0
  odd_previous = 1 #3-2
  for i in range(2, n+1):
    A[i] = A[i-1]*2 #can add to previous group 0 or 2
    odd_previous = n_all_options - A[i-1]
    A[i] += odd_previous #must have now 1
    new_options = np.zeros((A[i], i))
   
    new_options[:A[i-1], :-1] = options
    new_options[:A[i-1], -1] = 0
   
    new_options[A[i-1]:A[i-1]*2, :-1] = options
    new_options[A[i-1]:A[i-1]*2, -1] = 2
   
    new_options[A[i-1]*2:, :-1] = no_options
    new_options[A[i-1]*2:, -1] = 1

    n_all_options *= 3

    new_no_options = np.zeros((n_all_options-A[i], i))
    new_no_options[:odd_previous, :-1] = no_options
    new_no_options[:odd_previous, -1] = 0
    new_no_options[odd_previous:odd_previous*2, :-1] = no_options
    new_no_options[odd_previous:odd_previous*2, -1] = 2
    new_no_options[odd_previous*2:, :-1] = options
    new_no_options[odd_previous*2:, -1] = 1

    options = new_options
    no_options = new_no_options
   
  return A[n], options

print(dynamic_algo(n=4))

 

[s976]

לטעמי, זה ממש צועק תכנות דינמי.

מעניין. תוכלי להסביר?
אמי מבין שבתכנות דינמי הפתרון צריך להיות נכון גם בשביל תת משימה. וכאן זה לא.

 

[נסיון9876]

למה לא?
המערך A נבנה בצורה כזאת שהוא מכיל את הפתרון עבור כל מספר בין 0 לn
הרעיון בתנות דינמי הוא שמסתמכים על הפתרון של הבעיות החלקיות בשביל לפתור את הבעיה היותר גדולה(בכל שלב)
ומתחילים כמובן לפתור מהבעיה ההכי קטנה.
במקרה הזה - אם נסמן את מספר הפתרונות באורך N-1 בT
ואת מספר האפשרויות הכללי של מחרוזות "טריניאריות" כאלו באורך N-1-> בQ (בעצם שווה ל3^אורך המחרוזת)
הרי שהאפשרויות בשלב N מכילים:
1. אפשרויות שהיו חוקיות בשלב הקודם- והוסיפו להם 0 או 2 (וכך לא פגעו במספר האחדות האי זוגי שהיה) => 2*T
2. אפשרויות שלא היו חוקיות בשלב הקודם - עכשיו נשרשר להם "1" ואז יהפכו להיות חוקיים => Q

סהכ 2T+Q

 

[s976]

הייתה לי טעות בקוד. חבל שאי אפשר לערוך.
זה הקוד המעודכן. הוא פשוט סופר את כל האפשרויות אחת אחת.

def add_one_at(arr, i):
    quo, rem = divmod(arr[i] + 1, 3)
    arr[i] = rem
    if quo > 0:
        arr = add_one_at(arr, i - 1)
    return arr


def iter_n(n):
    arr = [0] * n
    yield arr
    for i in range(3**n):
        arr = add_one_at(arr, len(arr) - 1)
        yield arr


counter = 0
cardinality = 5
for a in iter_n(cardinality):
    if a.count(1) % 2 == 0:
        counter += 1

print(counter)

וזה קוד רקורסיבי שסופר את האפשרוית זוגיות ואי זוגיות

def rec(n):
    if n == 1:
        return 2, 1
    prev_even, prev_odd = rec(n - 1)
    return (prev_even * 2 + prev_odd), (prev_even + prev_odd * 2)


rec_count = rec(cardinality)

 

[נסיון9876]

למה לא?
המערך A נבנה בצורה כזאת שהוא מכיל את הפתרון עבור כל מספר בין 0 לn
הרעיון בתנות דינמי הוא שמסתמכים על הפתרון של הבעיות החלקיות בשביל לפתור את הבעיה היותר גדולה(בכל שלב)
ומתחילים כמובן לפתור מהבעיה ההכי קטנה.
במקרה הזה - אם נסמן את מספר הפתרונות באורך N-1 בT
ואת מספר האפשרויות הכללי של מחרוזות "טריניאריות" כאלו באורך N-1-> בQ (בעצם שווה ל3^אורך המחרוזת)
הרי שהאפשרויות בשלב N מכילים:
1. אפשרויות שהיו חוקיות בשלב הקודם- והוסיפו להם 0 או 2 (וכך לא פגעו במספר האחדות האי זוגי שהיה) => 2*T
2. אפשרויות שלא היו חוקיות בשלב הקודם - עכשיו נשרשר להם "1" ואז יהפכו להיות חוקיים => Q , Q-T

סהכ 2T+Q

אני רואה שיש כאן כמה טעיות.
מתקנת בציטוט