אתגר תכנותי: מציאת מספר הביטים שהם 1 במספר בינארי

האתגר עוסק בעבודה עם מספרים בינאריים ובפרט ספירה של מספר הביטים שהם 1. יכולת חשובה כשעובדים עם מערכי נתונים גדולים על משימות דוגמת קריפטוגרפיה, מדע נתונים ואלגוריתמים יעילים.

האתגר

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

לדוגמה:

n = 3

הקוד יחזיר:

[0, 1, 1, 2]

על פי:

decimal → binary → num bits
0 → 000 → 0
1 → 001 → 1
2 → 010 → 1
3 → 011 → 2

הצעה לפתרון

def count_bits(num):
   dp = [0] * (num+1)
   for idx in range(1, num+1):
       r = idx % 2   # Remainder: 0 or 1
       q = idx // 2  # Quotient
       dp[idx] = dp[q] + r # Store the number of 1s for the current index
   return dp

נבחן את הפתרון:

test_cases = [
   [0, [0]],
   [9, [0, 1, 1, 2, 1, 2, 2, 3, 1, 2]],
   [15, [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]]
]


print(f"{'Result'.ljust(10)}{'Expected'.ljust(10)}{'Conclusion'}")
print(f"{'-'*10}{'-'*10}{'-'*10}")
for num, expected in test_cases:
   res = count_bits(num)
   conclusion = "😄" if res == expected else "😭"
   print(f"{str(res).ljust(10)}{str(expected).ljust(10)}{conclusion}")


print("Finito Programa")

סיבוכיות:

• זמן - O(N) בגלל שקיימת תלות קווית בין מספר הביטים למספר הפעמים שהלולאה צריכה לרוץ כאשר כל הפעולות בלולאה פועלות בזמן קבוע O(1).
• מקום - O(N) בשל אורך המערך `dp` המכיל מספר איברים N כמספר הביטים.

הסבר הפתרון:

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

שיטת החלוקה מאפשרת להמיר ספרות מייצוג דצימלי לבינארי. בשיטת החלוקה ההמרה מתבצעת על ידי חלוקת המספר העשרוני ב-2 ורישום שארית החלוקה. נחזור על התהליך עד שתוצאת החלוקה היא 0. לבסוף, הצבת שאריות החלוקה בזו אחר זו בסדר הפוך הן המהוות את ייצוגו הבינארי של המספר.

לדוגמה, המרת המספר 13 לבינארי:

13 / 2 = 6 R 1
6 / 2 = 3 R 0
3 / 2 = 1 R 1
1 / 2 = 0 R 1

ייתן ייצוג בינארי 1101.

אותה שיטה גם מאפשרת לנו לחשב כמה אחדות יש בייצוג הבינארי של כל מספר על ידי חיבור שאריות החלוקה כאשר במקרה זה: 
1 + 0 + 1 + 1 = 3.

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

הרעיון של תכנות דינאמי הוא להימנע מחישובים החוזרים על עצמם על ידי אחסון תוצאות שכבר חושבו ושימוש בהם בהמשך במקום לחשב מחדש. זה בדיוק מה שעשינו במסגרת המערך dp - אחסנו את מספר האחדות בכל ספרת אינדקס כדי שלא נצטרך לחזור ולחשב. בכל איטרציה, הלולאה מחלקת את האינדקס הנוכחי ב- 2 כדי לקבל את המחולק q, לוקחת את הערך עליו מצביע q במערך ומוסיפה לו 1 או 0 בהתאם לתוצאת חישוב שארית החלוקה r, ומאחסנת את מספר האחדות הנוכחי חזרה במערך dp.

נעקוב אחר ההבנייה של dp עבור דוגמה קטנה של n=5:

dp[i] = count 1s (binary)
--------------------------------
dp[0] = 0            (0) 
dp[1] = 1            (1) 
dp[2] = 1            (10) 
dp[3] = 2            (11) 
dp[4] = 1            (100) 
dp[5] = 2            (101)

מדריכים נוספים בסדרת הפייתון שעשויים לעניין אותך

עבודה עם מספרים בינאריים ואופרציות Bitwise בפייתון

תכנות דינמי מלמטה למעלה ובחזרה - מדריך לתכנות דינאמי שמתחיל מהבסיס

אתגר תכנותי: איזה מספר חסר

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים