היי לכולן!
אז מזמן לא כתבתי אלגוריתם, וכבר מאוד התחשק לי לחזור לזה.
בניגוד להרגלי מהעבר, הפעם זו תהיה גרסה מקוצרת. אני אציג את הבעיה, ואיך הגעתי לפתרון ובניתי אותו. בלי להציג את כל הדיבאגים, הבדיקות והבעיות.
אני ממש מקווה שפתרונות מהסוג הזה עדיין יעזרו למי שמתכוננת לראיונות (תגידו לי בתגובות אם זה עוזר). לכל מי שרוצה לקרוא פתרונות ארוכים, שכוללים “שיחה” של ממש, כפי שצריך לקיים בראיון, אני ממליצה להסתכל באלגוריתמים הישנים שפרסמתי.
השאלה לקוחה מתוך האתר InterviewBit, שהוא אתר מאוד מומלץ לאימון בפתרון שאלות אלגוריתמים ומבני נתונים.
המשימה היא כזו – בהינתן מספר כלשהו N, מהו המספר המינימאלי הדרוש של מספרים מתוך סדרת פיבונאצ’י שסכומם שווה ל-N.
בשאלה מצוין שמותר לחבר את אותו מספר כמה פעמים.
לדוגמא –
N=11 8+3=11 --> fibsum(11) = 2
לפני שהתחלתי לפתור בדקתי את הפלט הצפוי וגיליתי שבעבור N=0 צריך להחזיר 0.
אחלה, אז אפשר להתחיל.
לקח לי די הרבה זמן לחשוב על כיוון לשאלה הזו. בדרך כלל המחשבה הראשונה שלי כשאני חושבת על סדרת פיבונאצ’י היא “אני לא יכולה לחשב את כל המספרים בסדרת פיבונאצ’י! זה כל כך לא יעיל!”.
לקח לי קצת זמן, וכל מיני ניסיונות כושלים להימנע מזה, עד שהבנתי שאין מנוס. התשובה חייבת לכלול חישוב של כל המספרים בסדרת פיבונאצ’י עד N עצמו.
בדיעבד זה היה צריך להיות הגיוני מההתחלה – כיוון שאני רוצה למצוא מספרים מהסדרה עצמה שירכיבו לי את הסכום, אני חייבת לחשב את המספרים בסדרה.
כיוון שרציתי למצוא את סכום המספרים המינימאלי, ידעתי שאני רוצה להתחיל לסכום מספרים כמה שיותר גדולים, ורק אז לחפש מספרים קטנים יותר. הרי, באופן תיאורטי, כל מספר N ניתן להרכיב מ-N פעמים 1, אבל אז זו לא תהיה הכמות המינמיאלית של מחברים.
התוכנית שלי הייתה למצוא את מספר הפיבונאצ’י הכי גדול שעדיין קטן יותר מ-N, לחסר אותו מ-N, ואז למצוא עוד מספרים שירכיבו את שאר הסכום.
לשם כך, בניתי לולאה שרצה על מספרי פיבונאצ’י מ-1 ועד שהיא מגיעה ל-N. המספר האחרון שהגעתי אליו לפני שהגעתי ל-N או עברתי אותו הוא מספר הפיבונאצ’י הכי גדול שקטן יותר מ-N.
הלולאה שלי נראתה כך –
previous = 0
current = 1
while current <= N:
tmp = current
current = current + previous
previous = tmp
כשיצאתי מהלולאה, המספר previous הכיל את מספר הפיבונאצ’י הכי גדול שמוכל בתוך ה-N שלי.
בשלב הבא, חיסרתי את previous מ-N והגעתי לשארית. כעת, הייתי צריכה להבין איך למצוא את שאר מספרי הפיבונאצ’י שהסכום שלהם מתאים לשארית.
התשובה הייתה פשוטה. איך אני בודקת כמה מספרי פיבונאצ’י צריך לסכום כדי להגיע למספר כלשהו – במקרה הזה, השארית שלי? אני משתמש באלגוריתם שזה עתה כתבתי.
בהתחלה חשבתי שיש טעם לשמור את מספרי הפיבונאצ’י שחישבתי כדי לעבור עליהם בשלב הזה. אבל שוב, אין דרך למצוא את המספרים הרלוונטיים, בלי לעבור על כל המספרים. כיוון שהמעבר על כל מספר בסדרה נעשה במהלך החישוב שלי ב-o(1), לא היה באמת טעם לשמור אותם בצד – זה רק היה מבזבז לי מקום, בלי לשפר את הסיבוכיות של החישובים שלי.
אז קראתי שוב לפונקציה שלי, הפעם עם השארית.
count = 0
remain = N
while remain >= previous:
count += 1
remain -= previous
return count + fibsum(remain)
הלולאת while שהוספתי כאן בודקת האם המספר previous שמצאתי מקודם נכנס ב-N יותר מפעם אחת. אם כן, אני רוצה לספור זאת כחלק מהסכום.
במבט ראשון, הקריאה הרקורסיבית לפונקציה יכולה להיראות קצת בזבזנית בסיבוכיות. אז בדקתי מה בעצם העלות של הקריאה הזו.
הסיבוכיות של הלולאה הבסיסית של היא o(M), כאשר M היא כמות המספרים בסדרת פיבונאצ’י שקטנים יותר מ-N.
***שימו לב, חישוב הסיבוכיות פה הוא לא נכון. אני משאירה פה את החישוב המקורי שלי, וההסבר על הטעות נמצא למטה ***
מה הסיבוכיות של הרקורסיה?כשאני קוראת ל-fibsum(remain) אני יכולה לדעת בוודאות ש-remain קטנה לפחות בחצי מהמספר המקורי שאיתו fibsum נקרא.
למה? כיוון שאם previous היה קטן יותר מ-N/2 אז הוא היה נכנס ב-N יותר מפעם אחת. במקרה כזה לולאת ה-while הייתה מחסרת אותו שוב ומגיעה ל-remain קטן יותר.
עכשיו שאנחנו יודעות את זה, אפשר לתאר את זמן הריצה של הרקורסיה שלנו בערך ככה –
M + M/2 + M/4 + M/8 + …
כלומר, בכל סיבוב זמן הריצה הוא לכל היותר חצי מזמן הריצה של הסיבוב הקודם.
הנוסחה המוכרת הזו מביאה אותנו לזמן ריצה o(MlogM).
האלגוריתם המלא נמצא בגיט שלי.
אם יש לכן רעיון לפתרון יותר טוב, או עם סיבוכיות יותר טובה, אני תמיד שמחה לשמוע!
תוספות אחרי עריכה:
האלגוריתם הספציפי הזה גרר הרבה דיונים בטוויטר, וגם בתגובות, ומהדיונים עלו כמה מסקנות שהרגישו לי מאוד חשובות לשיתוף:
שימוש באלגוריתם חמדן
האלגוריתם שהשתמשתי בו הוא מסוג אלגוריתם חמדן. זאת מכיוון שבכל שלב תמיד לקחתי את המספר הכי גדול שנתקלתי בו והתאים לתנאי שלי (קטן מ-N), בלי לבדוק אם יש מספרים קטנים יותר שיתנו תוצאה טובה יותר.
במקרה הנוכחי, של סדרת פיבונאצ’י, האלגוריתם הזה עבד, אבל אם הייתי עובדת עם סדרה אחרת הוא לאו דווקא היה עובד.
כשעבדתי על התרגיל במקור אכן שאלתי את עצמי אם האלגוריתם החמדן יעבוד פה. אני לא ידעתי להוכיח לכאן או לכאן, ולכן רק בדקתי כמה דוגמאות והמשכתי הלאה.
אם הייתי נתקלת במצב הזה בראיון (שאני רוצה להשתמש ברעיון שאני לא בטוחה אם הוא עובד מבחינה מתמטית) מה שהייתי עושה הוא לשתף את המראיין. הייתי אומרת שאני רוצה להשתמש באלגוריתם חמדן, אבל לא יודעת להוכיח אם הוא עובד. הייתי מציינת שבמקרה של בעיה “אמתית” (בעבודה) הייתי לוקחת את הזמן, ובודקת/מוכיחה, והייתי שואלת אם הוא רוצה שאני אנסה להוכיח, אשתמש בו בכל מקרה, או אלך לכיוון אחר.
התוצאה היא ש-
- המראיין היה יודע שעליתי על הבעייה בעצמי, ולא הנחתי שהאלגוריתם יעבוד. כמו כן, הוא יודע שזו בעיה מספיק חמורה כדי שבתנאי העולם האמיתי הייתי בודקת אותה לעומק.
- לא בזבזתי זמן על לנסות לפתור בעיה שהיא מתמטית, ולא תכנותית.
חישוב סיבוכיות
הסיבוכיות שחישבתי למעלה – o(mlogm) היא לא נכונה.
הטעות שלי הייתה שבלבלתי בין הגודל של המספר שאני מחפשת לגודל של הסדרה עצמה.
ההנחה שלי, שהשארית שלי תמיד תהיה קטנה מחצי מהמספר המקורי הייתה נכונה, אבל מכיוון שסדרת פיבונאצ’י מתקדמת בקפיצות זה לא אומר שכמות המספרים שאני צריכה לעבור עליה תהיה קטנה בחצי.
הדוגמא שניתנה לי בתגובות היא כזו –
בעבור המספר N=22, בריצה הראשונה נחסר את 13, ונישאר עם שארית 9.
בסדרת המקורית שלנו היו 8 מספרים –
1,1,2,3,5,8,13,21
בריצה הבאה שלנו אנחנו נתחיל מ-9 שהוא אכן קטן מ-N/2, אבל הסדרה שנרוץ עליה לא תהיה בגודל 4, אלא בגודל 6 –
1,1,2,3,5,8
לכן, סיבוכית האלגוריתם היא לא o(mlogm) אלא o(m2).
בהזדמנות זו אני רוצה להגיד תודה לקוראים שלי שעוברים על האלגוריתם והקוד, לוקחים את הזמן, ובצורה מכבדת לגמרי מציעים תיקונים ושלל פתרונות שונים לאלגוריתמים.
זו לגמרי פריווילגיה שאני זוכה לה בזכות הקהילה שנבנתה סביב הבלוג, ואני מקווה שהדיונים ונקודות המבט השונות עוזרות לקוראות שלי שלומדות עכשיו לראיונות.
בגלל שאת אוהבת רקורסיות, אז הנה רקורסיה (‘צטערת על ה-Javascript – כשאני בודק אלגוריתמים מהר, הקונסולת js היא הכלי הכי נגיש שיש לי):
function fibsum_int(n, previous, current) {
if (current > n) return { remain: n, count: 0 };
let { remain, count } = fibsum_int(n, current, current + previous);
while (current <= remain) { count++; remain -= current; }
return { remain, count };
};
function fibsum(n) { return fibsum_int(n, 0, 1).count; }
האסטרטגיה שלי: אפשר להסתכל על הבעיה כהליכה במורד המחסנית של סדרת פיבונאצ’י עד שנמצע את הגבול (המספר הכי נמוך שבטוח לא שימושי לפתרון כי הוא גדול מדי) ואז לחזור בחזרה ולאסוף את התוצאות בדרך חזרה.
היתרון, כל מספר פיבונאצ’י מחושב רק פעם אחת והאכסון היחיד הוא הארגומנטים ושני ערכי החזרה – שארית וספירה בשביל התוצאה הסופית (שאנחנו מאחסנים במסגרת במחסנית).
מוקדם מדי בבוקר בשבילי, אנסה לחשוב על פתרון שמחשב פעם אחת מבלי לשמור את התוצאות (גם לא במחסנית), אבל לולאה שמחסרת וסופרת היא בעצם פעולת חילוק.
count = 0
remain = N
while remain >= previous:
count += 1
remain -= previous
ניתן להחלפה ב:
remain = N / previous
לא בטוחה שאני מבינה את הכוונה פה.
ספרת כמה פעמים previous (מה הערך שלו, אגב?) נכנס ב-n.
סליחה, בכל זאת מוקדם בבוקר בשבילי.
אני מתייחס לקטע הקוד שכתבת עליו:
“הלולאת while שהוספתי כאן בודקת האם המספר previous שמצאתי מקודם נכנס ב-N יותר מפעם אחת. אם כן, אני רוצה לספור זאת כחלק מהסכום.”
במקום לחסר בלולאה, אפשר פשוט לחלק – זה נותן את אותה התוצאה, כך ש:
בהנתן הקוד שלך:
count = 0
remain = N
while remain >= previous:
count += 1
remain -= previous
return count + fibsum(remain)
אפשר לעשות משהו כמו count = N / previous
ואז remain = N % previous
ואז:
return count + fibsum(remain)
אני לא כותב בפייתון, אז אולי צריך להפוך משהו פה ל integer, אבל בגדול, אין צורך בלולאה כדי לחשב את count ו remain.
אה, עכשיו הבנתי.
אכן, אתה צודק, לא יודעת למה לא חשבתי על זה 😀
אני חושב שניתוח הסיבוכיות שלך שגוי, לדעתי זמן הריצה הגרוע הוא ריבועי, ולא n(logn), כי במקרה הגרוע עוברים בדיוק על חצי הסדרה
רוצה לתת חישוב סיבוכיות שונה?
השגיאה בהסבר למעלה, היא שאמנם remain קטן לפחות בחצי, אבל מספר המספרים בסדרה קטן רק באחד. כלומר נשארו חצי מהמספרים מישר המספרים, אבל רק אחד פחות ממספרי פיבונאצ’י. לדוגמא: 33. יש 8 מספרי פיבונאצ’י קטנים ממנו; אחרי שהוספנו את המספר הקרוב אליו ביותר, 21, נשאר לחשב את הפונקציה על 12. זה אמנם פחות מחצי מ – 33, אבל יש 6 מספרי פיבונאצ’י קטנים ממנו, ולא 4.
בדיוק מהשיקול שכתבת למעלה, אחרי שלקחנו את המספר הגדול ביותר, לא יתכן שניקח את המספר הבא בסדרה (אחרת מלכתחילה היינו בדיוק במספר פיבונאצ’י), אבל חייבים לחשב עבור על מספרי פיבונאצ’י שתחתיו.
כלומר מחשבים על n, n-2, n-4 וכו’.
זה יוצא n^2/2 כלומר O(n^2)
אתה אכן צודק, אני אתקן את הפוסט.
תודה על התיקון!
אפשר להציע פתרון הרבה יותר יעיל, o(log(n)), אם מותר “לרמות” ולהשתמש בגוגל. כי יש הרי נוסחה ישירה למספר ה – i בסדרה (בלי לחשב את אלו שלפניו), ונגזרת ממנה נוסחה שנותנת את מספר פיבונאצ’י הקרוב ביותר ל N נתון.
זו לא רמאות, אבל זה גם לא בדיוק o(logn) כי לא מספיק לך למצוא מספר אחד, אתה צריך לחזור על החיפוש כמה פעמים עד שתמצא את כל המחברים.
את צודקת, אם N הוא מספר מספרי פיבונאצ’י הקטנים מהקלט, אני חושב הסיבוכיות של מה שאני מציע היא O(N), כי במקרה הגרוע צריך למצוא N/2 מספרים מהסדרה.
תודה על הדיון הנחמד 🙂
איך שאני רואה את זה:
בפיבונצ׳י לא צריך יותר מדי בשביל לחשב ערך חדש, לשני הכיוונים
An == (An-1 + An-2) => An-2 == (An – An-1)
לצורך זה יצרתי גנרטור דו כיווני לפיבונצ׳י: Fibinerator(Fibonachi bidirectional iterator)
משם הדרך היתה קצרה לטיול במעלה ובמורד הסדרה ולחישוב ב-O(m) זמן וכן O(1) מקום נוסף:
קוד מלא:
https://gist.github.com/orens/ed0a822ef2f1e8405a48b27143670112
ובהזדמנות זו, תודה רבה על הפוסטים המעניינים והמלמדים! כיף לקרוא את שאת כותבת, ותודה גם על ערוץ הטלגרם, שעוזר לי לא לפספס 🙂
פתרון יפה ואלגנטי.
אגב, לגבי חישובי סיבוכיות, כיוון שעוצמת מספרי פיבונאצ׳י היא לוגריתמית (הולכת כמו log(n)):
O(M) = O(log(n))
ניטפיק קטן:
אחד הפיצ’רים הנחמדים בפייתון הוא היכולת להחזיר יותר מתוצאה אחת (שזה פשוט סוכר סינטקטי ללהחזיר tuple). אז במקום:
tmp = current
current = current + previous
previous = tmp
אפשר:
current, previous = current + previous, current
בעיה מעניינת ונחמדה.
שתי הערות:
1. אפשר לפתור ב-O(log(n)), במקום O(log^2(n)), ע״י:
א. לשמור את כל איברי פיבונצ׳י.
ב. במקום לקרוא רקורסיבית לכל החישוב, אפשר פשוט להמשיך ולסכום את המספרים הקטנים יותר בסדרה.
מימוש לדוגמה:
def fibsum(N):
if N == 0:
return 0
fibs=[0,1]while fibs[-1] < N:
fibs.append(fibs[-1]+fibs[-2])
count = 0
remain = N
for i in range(len(fibs)-1,0,-1):
if fibs[i] <= remain:
count += 1
remain -= fibs[i]
if remain == 0:
return count
הפתרון משתמש באלגוריתם חמדני, שמניח שתמיד קיים פתרון (קבוצת איברי פיבונצ׳י שסכומם כנדרש) מינימלי (קבוצה בעלת מספר מינימלי של איברים), שמכיל את האיבר האחרון (הגדול ביותר שקטן או שווה ל-N) בסדרה.
אם במקום פיבונצ׳י ניקח לדוגמה את הסדרה 1,7,11,17,… ונרצה למשל להגיע לסכום של N=14, אז אלגוריתם חמדני יגיד שדרושים ארבעה מספרים, 11+1+1+1, בזמן שלמעשה דרושים רק שניים: 7+7. כלומר אלגוריתם חמדני לא ימצא את המספר המינימלי במקרה הזה.
במקרה של סדרת פיבונצ׳י הטענה שקיים פתרון מינימלי שמכיל את האיבר האחרון דווקא נכונה. אנסה להוכיח אותה:
ראשית – אם שני איברים עוקבים a(n),a(n+1) מופיעים בפתרון, ניתן להחליפם באיבר העוקב a(n+2), שהרי הוא שווה לסכומם, ובכך לצמצמם את מספר האיברים בפתרון. כלומר – בכל פתרון מינימלי לא יופיעו שני איברים עוקבים.
שנית – אם איבר a(n) מופיע פעמיים, ניתן להחליפו באיבר העוקב a(n+1) ובאיבר ששניים לפניו a(n-2), שכן:
a(n-2)+a(n+1)=a(n-2)+a(n-1)+a(n)=a(n)+a(n)=2a(n)
כלומר קיים פתרון מינימלי שלא מכיל אף איבר פעמיים (או יותר).
מכאן קל לראות שהסכום המירבי שניתן לקבל ללא איברים עוקבים וללא חזרות על איברים יתקבל ע״י סכום לסירוגין של אחד מהשניים:
א. a(1),a(3),a(5),…
ב. a(2),a(4),a(6),…
אלא ש- a(1)+a(3)+…+a(2n-1)<=a(n)
וגם: a(2)+a(4)+…+a(2n)<=a(2n+1)
(אפשר להוכיח באינדוקציה)
כלומר – הסכום המירבי של איברים קודמים ללא עוקבים וללא חזרות לא יהיה גדול מהאיבר האחרון, ולכן בוודאות נזדקק לאיבר האחרון כדי לייצר סכום שגבוה ממנו, ולכן אלגוריתם חמדני שלוקח תמיד את האיבר האחרון (שקטן או שווה מהדרוש N) אכן מחזיר פתרון אפטימלי.
הערה לגבי המשפט הזה: “האם המספר previous שמצאתי מקודם נכנס ב-N יותר מפעם אחת.”: בסדרת פיבונאצ’י המספר הבא בסדרה הוא פחות מכפול מהמספר הנוכחי. אם המספר שמצאת נכנס פעמיים ב N, זה אומר שפספסת את המספר שביניהם.
הי,
ניסיתי להבין את הקוד שלך ולצערי לא הצלחתי להבין מדוע את משתמשת ב count.
הנה הפתרון שלי לבעיה שמבוסס על הפתרון שלך רק קצר יותר ולעניין. אשמח לדעת אם פספסתי משהו.
fibsum(int num) {
if(num == 0) {
return 0;
}
int previous = 1;int current = 2;
while(current <= num) {
int temp = current;
current += previous;
previous = temp;
}
return 1 + fibsum(num - previous);
}
ולגבי אלגוריתם חמדן – לא בדקתי את זה מתמטית אך נראה לי שבתרגיל הזה לא ייתכן מצב שבו גישה פחות חמדנית תניב שימוש בפחות אברים כדי להגיע לתוצאה הסופית.
ודרך אגב, תודה על בלוג נפלא!
הסיבה ל-count הוא שמותר להשתמש באותן המספר כמה פעמים.
באלגוריתם שלך, אם הבנתי אותו נכון (התנאי ב-while לא ברור) מספר לא יכול לחזור פעמיים.
תודה רבה 😊
התנאי ב while הוא בדיוק כמו שלך – כל עוד האיבר הנוכחי שנבדק קטן או שווה למספר שהפונקציה קיבלה.
בגלל המבנה של סדרת פיבונאצ’י (החל מ 3 – כל איבר הוא פחות מפעמיים האיבר הקודם) אף פעם לא יהיה מצב שבו איבר כלשהו ישתתף פעמיים בפתרון. לא הוכחתי את זה מתמטית – זה פשוט מסתדר לי הגיונית.
תודה רבה!
🙂
נראה לי על פניו – כפי ששאול מציין – שאפשר לטעון שאפשר להגיע לכל מספר שלם על ידי סיכום של מספרים נבחרים מסדרת פיבונאצ’י ללא כפילויות. זה נשמע לי ממש סביר שמישהו כבר אמר את זה קודם, אז הלכתי לבדוק – ואכן: זו תיאורית זקנדרוף: https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
זה נכון, אני לא בטוחה למה צוין בשאלה שאפשר לחזור על מספרים פעמיים. זה כנראה מתאים לאסטרטגיית פיתרון אחרת שלא תמיד מנסה להכניס את המספר הכי גדול, אני סקרנית מה היא
@guss77 – לא הכרתי את תיאורית זקנדרוף (ושקראתי אז לא הסתדרתי עם המתמטיקה שם – קצת מתקדם מידי עבורי) – בכל מקרה, תודה על השיתוף.
@Maya – לדעתי הם ציינו שאפשר לחזור על מספרים פעמיים בכדי לספק מידע נוסף שכל מטרתו היא לשלוח אותך לחפש פתרון בכיוון לא נכון. ישנן לא מעט שאלות שכאסטרטגיה מספקים מידע נוסף מיותר שכל מטרתו היא לשלוח אותך לחפש פתרון בכיוון לא נכון וכך הם מנסים לבדוק גם את היכולת לסנן “רעש” או מידע מיותר. זה קרה לי בעבר – מעצבן אך זה חלק מ”חוקי המשחק”
שאול – אני אוהב את האופטימיות שלך ואת האמון בבני אדם. אל תשתנה! 🤗😀👌😏
על אף שהתברר בסוף שניתוח הסיבוכיות לא נכון, לעניות דעתי הנוסחה
M + M/2 + M/4 + …
תיתן לנו סיבוכיות לינארית של o(m)
למעט ערכים קטנים של N (קטנים מ 21) סדרת פיבונצ’י היא סדרה הנדסית (בקירוב, אבל קירוב ממש טוב).
לכן ניתן להשתמש באלגוריתם הדומה לזה של מצאת יצוג בינארי של מספר, בידיעה שאכן כל איבר יופיע לכל היותר פעם אחת (וכשיורדים מתחת 20 ממשיכים כמו שהצעת).
הסיבוכיות היא O(logN)
ש לי רעיון קצת אחר.
מחשבים את כל המספרים של הסדרה שקטנים או שווים לN לתוך מערך פיבונאצי בזכרון.
לאחר מכן’ עוברים על המערך מהסוף (i=len(arr)-1) ובכל פעם נחסר את המספר שבמקום הi מN.
אם נקבל מספר שווה ל0: סיימנו ומצאנו את הפתרון.
אם גדול מ0: אז נוסhף לקאונטר של הפתרון 1, ונקטין את i ונמשיך לחפש.
אם קיבלנו מספר קטן מ0: זה אומר שחיסרנו יותר מדי ופשוט נמשיך לחפש להחסיר מספר קטן יותר.
הרעיון הוא להשתמש בסדרת פיבונאצי בשביל למנוע חיפוש מיותר.
הסדרה הזו היא בעצם מערך ממוין, תמיד עולה, עם מספרים יחודיים.
מה שאומר שניתן לחבר כל מספר חיובי, ממספרים יחודיים של הסדרה הזו.
כלומר, אין צורך לבדוק את המקרה שצריך להוסיף אינדקס מסוים פעמיים.
זתומרת N=4 זה בעצם 3+1 ולא 2+2.
ובדרך הזו, תמיד נקבל את התשובה המינימלית. ותמיד תהיה תשובה.
PS
אני מחפש עבודה כרגע ומתכונן לראיון מחר. הבלוג שלך עזר לי מאוד, תודה.
ואם מחפשים מתכנת בקאנד, מוזמנים ליצור קשר בשמחה 🙂
הנה הקוד לפתרון שכתבתי:
def fibsum(N):
fibArr = []
fibArr.append(1)
fibArr.append(1)
i=2
while(fibArr[i-1]+fibArr[i-2] <= N):fibArr.append(fibArr[i-1]+fibArr[i-2])
i+=1
length = len(fibArr)
nums=0
for i, val in enumerate(fibArr):
if( N - fibArr[length-i-1] == 0 ):
return nums+1;
elif(N - fibArr[length-i-1] > 0):
N = N - fibArr[length-i-1]
nums+=1
else:
i+=1
וסורי על הLTR הדפוק.
יש פיתרון בO(1) שמבוסס על זה שסדרות פיבונאצ’י הן מרחב ווקטורי ממימד 2 ואז אם יש לך 2 סדרות שקל לחשב אפשר לפרוס באמצעותן את כל המרחב.
https://medium.com/@andrew.chamberlain/the-linear-algebra-view-of-the-fibonacci-sequence-4e81f78935a3
הבעיה ההנדסית העיקרית כאן היא המרה מfloat לint