פורסם ב זה רק קוד

שבע בום

קוד: seven-boom
זמן קריאה: 8 דקות

לפני כמה ימים שוטטתי לי בפייסבוק, ובאחת מקבוצות התיכנות שאני נמצאת בהן מישהו ביקש עזרה במימוש המשחק שבע בום. ההגדרה הספציפית של התרגיל הייתה לכתוב לולאה אינסופית, שמדפיסה את כל המספרים, ומדפיסה "BOOM" במקום מספרים שמתחלקים בשבע או מכילים את הספרה שבע.

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

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


אלגוריתם נאיבי

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

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

def divisible_by_seven(num):
	divisible = num % 7 == 0
	return divisible

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

def contains_seven(num):
	contains = ‘7’ in str(num)
	return contains

מעולה. עכשיו אני אשתמש בשתי הפונקציות שלי כדי לייצר את האלגוריתם המלא – 

def seven_boom():
	num = 1
	while True:
		if divisible_by_seven(num) | contains_seven(num):
			print(“BOOM”)
		else:
			print(num)
		num += 1

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

הפלט של האלגוריתם, שחקן שבע בום מצטיין.

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

  • הבדיקה הראשונה שלנו – divisible_by_seven – כוללת רק חילוק. חילוק היא פעולה מתמטית פשוטה. אל הסיבוכיות של הבדיקה הזו נוכל להתייחס כ- o(1).
  • הבדיקה השנייה שלנו – contains_seven – מכילה המרה של מספר למחרוזת, ואחר כך חיפוש ספרה בתוך המחרוזת. כיוון ששתי הפעולות הללו דורשות מעבר על כל התווים במספר, הסיבוכיות שלנו תהיה בסדר גודל של מספר הספרות במספר הנתון. כלומר – o(n).
    חשוב לשים לב שהלולאה שלנו היא אינסופית. אם כך, האלגוריתם שלנו יעבור על מספר גדולים מאוד בעלי מספר ספרות גדול, ולכן ה-n שלנו לא זניח במקרה הזה.

פעולה יחידה של האלגוריתם המלא שלנו היא בסיבוכיות o(n), ריצה של האלגוריתם על m מספרים תתבצע בסיבוכיות של o(nm).

עכשיו אני אשאל שוב – האם ניתן לשפר את הסיבוכיות של האלגוריתם? ובכן, אני לא בטוחה, אני לא הצלחתי. אבל האם ניתן לפתור את התרגיל בצורה מעניינת יותר? לדעתי אפשר בהחלט!

אלגוריתם אלטרנטיבי

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

למה להתאמץ לחלק כשאפשר פשוט לספור?

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

אני אוסיף את המונה שלי לאלגוריתם.

def seven_boom():
	num = 1
	counter = 1
	while True:
		if counter == 7:
			print(“BOOM”)
			counter = 1
		elif  contains_seven(num):
			print(“BOOM”)
		else:
			print(num)
		num += 1
		counter += 1

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

אני ממש רציתי למצוא פתרון אלגנטי ויעיל לבדיקה הזו.  בהתחלה חשבתי להשתמש גם כאן במונה. לדוגמא – כדי למצוא מספר שספרת האחדות שלו היא 7 אנחנו רק צריכות לספור עשרה מספרים מאז המספר האחרון שהספרה האחרונה שלו הייתה 7.
השיטה הזו פותרת לנו את הבעיה ל-17,27,37 וכו׳ אבל מה לגבי 70?
אחר כך חשבתי על סוג של מכונת מצבים, שבה אני אחפש הצטלבות בין מספרים שמתחלקים ב-7 למספרים שמתחלקים ב-10, ואז אעבור על הטווח שמגיע אחריהם – 71,72,73 וכו׳… אבל גם הכיוון הזה לא הבשיל.

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

מחכה לפתרונות שלכן

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

בתור התחלה אני רוצה ללכת על פתרון ששומר על רמת הסיבוכיות הנוכחית – o(n) – ולא פוגע בה. 
במקום להפוך את המספר שלי למחרוזת ולחפש בה את התו '7', אני רוצה לממש פתרון שעובר על כל הספרות במספר ובודק האם הן שוות לשבע.
איך עוברות על כל הספרות של מספר בלי להפוך אותו למחרוזת? בעזרת שתי פעולות חשבוניות – חילוק ומודולו.

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

אני אכתוב את הפונקציה החדשה שלי – 

def contains_seven_with_math(num):
	while num != 0:
		if num % 10 == 7:
			return True
		num /= 10
	return False

נעשה דוגמא קטנה ונראה שהאלגוריתם עובד – 

num = 1701
contains_seven_with_math(num):
	num != 0 → True
	num % 10 = 1 == 7 → False
	num = 170
	num != 0 → True
	num % 10 = 0 == 7 → False
	num = 17
	num != 0 → True
	num % 10 = 7 == 7 → True
	return True

נראה טוב! נשים לב שהסיבוכיות נשארה אותו הדבר – o(n) כתלות במספר הספרות.

זהו זה, היה כיף לחשוב בצורה אלגוריתמית ויצירתית על משחק שאני אוהבת. האלגוריתם המקורי והאלטרנטיבי נמצאים, כרגיל, בגיט שלי.
אני מחכה כבר לראות את הפתרונות האלטרנטיביים שלכן!

28 תגובות בנושא “שבע בום

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

    1. נראה לי שהסיבוכיות של פעולת חילוק היא גם כן O של n. לא?

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

    2. אתגר מעניין. כמו שכבר אמרו כמות הספרות זה logn בבסיס 10, אבל אם את מדפיסה את המספר בהכרח את עושה איזושהי פעולה עבור כל ספרה ולכן זה בהכרח n*logn
      אבל רק בשביל הקונספט בואו נניח שאנחנו הופכים את התנאי – רוצים להדפיס רק את המספרים שיתריגו בום, בסדר עולה, כלומר 7, 14, 17, 21 וכך הלאה.

      אפשר לעשות את זה בlogn * logn (אם החישוב שלי עובד)

      אני חשבתי לעשות את זה עם רשימת איטרטורים

      בהתחלה יש לי ברשימה איטרטור יחיד, שמתחיל מ-7 ומוסיף לו 7 כל פעם. בנוסף יש לי מספר x שמתחיל מ10 ואני אשתמש בו להוסיף איטרטורים.

      הלולאה שלי היא בגדול ככה:
      -תן לי את המספר הגדול מבין כל האיטרטורים
      -תתדפיס את המספר
      -אם המספר גדול או שווה ל-x
      — תבנה לי איטרטור ספרות עבור x ותוסיף
      לרשימה
      — תכפיל את x ב-10

      איטרטור ספרות עבור 10, יתחיל ב7 ויוסיף 10 כל פעם. עבור 100 הוא יתחיל ב-70 ויוסיף 100 בכל פעם, וכן הלאה

      כמה בדיקות אנחנו עושים? ככמות האיטרטורים, שזה כמות הספרות +1, שכבר אמרנו שזה logn לכן אני חושב שזה logn*logn

  2. אפשר גם לפתור את הבעיה הזו בלי if/else
    nums = list(range(1,100))

    ndig = len(str(nums[-1]))
    for d in range(ndig):
    for k in range(10d):
    for n in range(7*10
    d+k,len(nums),10**(d+1)):
    nums[n-1] = 'boom'

    for idx in range(6,len(nums),7):
    nums[idx] = 'boom'

    print(nums)

      1. Challenge accepted!

        def div_7():

        counter = 1
        while True:
        for i in range(6):
        yield counter
        counter += 1
        yield 'boom'
        counter += 1

        def seven_boom_digital(d, sub):

        while True:
        for i in range(10d):
        yield 'boom'
        next(sub)
        for i in range(9*10
        d):
        yield next(sub)

        def seven_boom():

        gen = div_7()
        counter = 0
        for n in range(1,7):
        yield next(gen)
        while True:
        gen = seven_boom_digital(counter, gen)
        for n in range(7*10counter,7*10(counter+1)):
        yield next(gen)
        counter += 1

        gen = seven_boom()
        [next(gen) for n in range(1000)]

  3. לשמור את המספרים שענו לתנאים ב-cache, ואז להמשיך להשתמש בו בכל פעם שכולים סדר גודל, כלומר ב-700, 7000 וכו'

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

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

      2. נתקלתי בבעיה כשהגעתי ל-17. הוא לא מתחלק ב-7 אבל מכיל 7. בגלל זה הוספתי CACHE ששומר את כל המספרים ובמקום אלה שיש בהם 7 שומר BOOM. אני מניח שאפשר ליעל את מבנה הנתונים הזה כך שלא ישמור את כל המספרים אבל אז אני צריך עבור כל מספר לחפש ב-HASHSET שזה אמנם יעיל אבל לא מביא אותי ל-O(n) עבור כל התהליך. עם קצת יותר חשיבה יצירתית אולי אפשר להעלים את ה-CACHE לגמרי. בסופו של דבר צריך להתחשב ביכולות המחשב, ומאחר שגם המונה מוגבל בספירה וכמות הזיכרון היא תא אחד לכל מספר (אם מתעלמים מה-BOOMים או שמחליפים אותם בסימן מוסכם, נניח רק B) ומה שמעניין זה דווקא הביצועים אז זה נראה לי פיתרון אידיאלי. אם מתעלמים מהמגבלות הטכניות אז כמובן שזה פיתרון אידיאלי.
        אתה יכול לראות את הפתרון שהצעתי כאן:
        https://github.com/mgershovitz/maya_solves/issues/2

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

    הנה C‪++‬:

    ⁦#include
    ⁦#include
    ⁦#include
    ⁦class Digit {
    ⁦ unsigned char val, sevenCount;
    ⁦ std::unique_ptr moreSignificant;
    ⁦public:
    ⁦ Digit(unsigned char startVal) : val(startVal), sevenCount(startVal % 7) {}
    ⁦ void inc() {
    ⁦ if (++sevenCount >= 7)
    ⁦ sevenCount = 0;
    ⁦ if (++val inc();
    ⁦ else
    ⁦ moreSignificant = std::make_unique(1);
    ⁦ }
    ⁦ }
    ⁦ bool hasSeven() {
    ⁦ return val == 7 || (moreSignificant ? moreSignificant->hasSeven() : false);
    ⁦ }
    ⁦ bool isDivisibleBySeven() {
    ⁦ return sevenCount == 0;
    ⁦ }
    ⁦};
    ⁦int main() {
    ⁦ Digit num(0);
    ⁦ for (unsigned long long i : std::ranges::views::iota(1LL, 1000LL)) { /* while (true) */
    ⁦ num.inc();
    ⁦ if (num.hasSeven() || num.isDivisibleBySeven())
    ⁦ std::cout << "BOOM" << std::endl;
    ⁦ else
    ⁦ std::cout << i << std::endl;
    ⁦ }
    ⁦}

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

      2. כל מה שאמרת נכון , אבל הכל מסבך את הקוד, ולא ברור שצריך את זה – חוק קנות' וכד'.

        אבל אשמח לראות את הגרסה שלך עם השיפורים שציינת 😄

      3. ראה קוד פייתון בתגובה למטה (https://paste.ofcode.org/326swxC8gbKS3ne3exJ5YCh). לגבי סיבוכיות- אפשר לעשות הכל בשורה אחת וכנראה שלא נרגיש בהבדל, כך שזה קצת תיאורטי. אבל אם רוצים לדבר על מה יקרה במספרים גדולים מאד (למשל אם מתחילים ב- 1 ואחריו מליון אפסים וממשיכים משם) – הקוד שלך יבדוק בכל פעם את מליון הספרות (אלא אם באמת יש 7), והקוד הזה כבר יידע שאין.

      4. הלכתי וכתבתי את הגרסה השניה שלך בגרסת ה-‪C++‬ שאני כותב (זאת עם העצמים, שהיא לא סתם C פחות מגעיל 😜), וזה נראה כך: https://gist.github.com/guss77/740790b99460804bad3e25a49e16eca4

        כצפוי, פחות קריא. ביצועים: שבע בום למיליון (אחד ואחריו שישה אפסים, לא בדקתי על גוגל כי אני רוצה להשתמש במחשב שלי גם למשהו אחר במאה הנוכחית 😅) הגרסה השניה היא פי שמונה יותר מהירה וקצת יותר ככל שמגדילים את המקסימום. האם זה שווה את זה? בשביל לנצח בתחרויות לכתיבת אלגוריתמים לשבע בום – בטוח! 😆✌️🏅

      5. הנה הסיכום שלי:
        1) במימוש שבו ממירים ל- string ובודקים אם 7 קיים צריך לייצר את הייצוד העשרוני המלא של המספר, מה שלוקח O(nlog(n)) כאשר n הוא מספר הספרות של המספר.
        2) במימוש שבו מחלקים ב- 10 בכל פעם עד שמגיעים ל- 7 הראשון, הזמן יהיה O(klog(n)) כאשר k הוא מספר הספרות עד שמגיעים ל- 7 הראשון (במקרה הגרוע ביותר זה n, אבל בתוחלת במספרים גדולים זה בערך 10). ה- log(n) מגיע מחלוקת המספר ב- 10 (או חישוב מודולו 10).
        3) במימוש שבו מחזיקים את המספר בייצוג עשרוני ועוברים על כל הספרות עד שמוצאים 7 זה O(k). כמובן שצריך לקחת בחשבון גם את הזמן שלוקח לעדכן את המערך\הרשימה המקושרת כאשר מוסיפים 1, אבל למעשה זה נכון גם לשני הייצוגים הראשונים (זה פשוט נעשה על אובייקט סטדנדרטי).
        4) במימוש שבו זוכרים כמה 7'ים יש זה O(1) (ושוב צריך גם לעדכן את המערך בהוספת 1).

        כל זה לא ממש משנה כאשר מדפיסים את כל המספרים על המסך, מה שכנראה לוקח הרבה יותר זמן, וכל החישובים האלו לא באמת אומרים לנו מה יקרה במספרים "קטנים" (נניח כאלו שנכנסים ב- 64 ביט) – למשל מאד ייתכן שדווקא מימוש 2 טוב יותר (והוא גם קריא יותר ממימושים 3 ו- 4).

      6. חשבתי שכדאי להוסיף מטה-התייחסות לעובדה שמדובר באחד הדיונים המוזרים ביותר שלקחתי בהם חלק.

        בפוסט עצמו מופיע מימוש ממש פשוט (ודי יעיל אם זה המדד) בתוספת תהיה אם יש פתרון "יפה" יותר (קרי – שלא עובר על המספר ובודק קיום 7 בייצוג העשרוני). אתה הצעת פתרון שמחזיק את הייצוג העשרוני כל העת, ואני הצעתי להוסיף ספירה של ה-7'ים כדי לחסוך מעבר על כל המספר עד ה- 7 הראשון. אתה התייחסת לחוק קנות' למרות שמלכתחילה אין הקשר כדי להתיחס אליו (למשל טווח מספרים, מה צריך לעשות עם התוצאה, איפה זה אמור לרוץ) ובצדק (השאלה היא אלגוריתמית, לא מימושית), ולמרות שלא התייחסת אליו במימוש הראשון שלך (כאמור – עבור מספרים של 64 ביט כנראה שפעולה אריתמטית יעילה יותר מגישה לזכרון, בוודאי כאשר הקומפיילר יודע לבצע את פעולת החלוקה ב- 10 והמודולו 10 ביחד).

        עכשיו קרה הדבר המוזר ביותר מבחינתי – אתה התייחסת למימוש שלי כ"מגעיל" ומימשת אותו מחדש, עם בלאק-ג'ק ורשימות מקושרות, למרות שרשימה מקושרת לא נהנית מגישה סדרתית לזכרון וכמו כן מוסיפה תקורה של החזקת פוינטרים. בנוסף המימוש הרקורסיבי כתוב בצורה שלמיטב הבנתי לא מאפשרת לקומפיילר לבצע tail recursion optimization למרות שהדבר אפשרי – כך שכנראה שהתוכנית עסוקה רוב הזמן בדחיפת דברים ל- stack והוצאתם (שוב – לא הרצתי פרופיילינג כי כל זה לא חשוב, אז אני לא יודע אם זה המצב).

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

        באמת שאני לא מבין את כל הדיון המוזר הזה.

      7. תיקון חשוב לתגובה על ניתוח הסיבוכיות – בכל מקום שכתוב log(n) צריך להיות כתוב n (כל הפעולות לוקחות O של מספר הספרות).

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

      9. בנוסף, הרבה מההערות שלי על קוד יפה וקנות' נובעות מהגישה שלי ש"בעולם האמיתי" (רוב הזמן) קריאות הרבה יותר חשובה מביצועים. הדיונים על סיבוכיות מצויינים כדי להרגיל את החשיבה על יעילות של אלגוריתמים ולאפשר להגיע לתיכון ראשוני יותר טוב, אבל אם מקריבים בשביל זה קריאות של הקוד או זמן פיתוח, אז יצא שכרנו בהפסד.

    1. תודה על התגובה וההבהרה. הכל טוב, זה פשוט היה לי מוזר (חוק פו וזה).

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

  5. כבתתי בטוויטר, אבל מצורפת פה גרסה עם יותר הסברים (וגם הסרת ייעול שלא ממש צריך ושמפשט את הקוד): https://paste.ofcode.org/326swxC8gbKS3ne3exJ5YCh
    הסבר: מחזיקים את ייצוג המספר בבסיס 10 ברשימה (ספרת האחדות במקום הראשון ברשימה, העשרות במקום השני וכו'). כמו כן זוכרים את האינדקס האחרון (הגדול ביותר) שבו מופיע 7 (ואם אין 7'ים במספר – ערך זה הוא מינוס 1). כדי להגדיל את המספר ב- 1, צריך להוסיף 1 לספרת האחדות, ואם יוצא 10 – להפוך ל- 0 ולעבור לספרה הבאה, וכו'. עדכון כזה עשוי לעבור על כל הספרות, אבל לרוב הוא ייעצר בספרת האחדות, ולמעשה תוחלת מספר הספרות שנעדכן היא מעט יותר מ- 1 (כלומר O של 1). אם מספר הספרות גדל, פשוט נוסיף עוד איבר לרשימה.

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

    1. במחשבה נוספת – אפילו פשוט יותר: עדיין נשמור את המספר כרשימה של הייצוג העשרוני, אבל נזכור את מספר ה-7'ים ברשימה. בכל פעם שמספר הופך ל- 7 הוא מגדיל את המספר הזה, בכל פעם שהוא מפסיק להיות 7 הוא מוריד את המספר הזה.
      קוד (הפעם ב- ++C): https://paste.ofcode.org/vkQ2AHzuAriHwhwhGd2tmK

השאר תגובה