דרכים

[Javali]

דרכים

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

 

[guysoffer]

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

81

 

[Javali]

../images/Emo127.gif

כן - זה מעצבן, אבל יש פתרון...

 

[כלמנ]

יש !!!

סידרת פיבונצ'י עם שלושה איברים n= n-1+n-2+n-3 הסבר:מאיבר ההתחלה(איבר n) ניתן להמשיך בשלוש צורות: 1 . לאיבר שלפניו (n-1) אפשרויות 2. לאיבר ש2 לפניו (n-2) ולהמשיך שמאלה כמו שחושב ב n-2 3. או לאיבר ש 2 לפניו ולחזור ל n-1 ומשם חייב לעבור ל n-3 ולכן n-3 אפשרויות. סדרת פיבונצ'י הזאת יוצאת: 1,2,4,7,13,24,44,81,149 ...

 

[כלמנ]

טעות ../images/Emo9.gif

הגבתי במקום הלא נכון

 

[כלמנ]

34?

אם כן אז יש לי תפתרון מגניב

 

[Javali]

../images/Emo128.gif

34 היא התשובה רק כשאסור ללכת אחורה.

 

[כלמנ]

אם אי אפשר ללכת אחורה

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

 

[guysoffer]

כנראה שכן

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

 

[yoavj1]

ניסיון

לכל תא יש שני מספרים - x ו y. המשמעות של x היא מספר האפשרויות להגיע לסוף אם מתחילים מהתא והוא התא הראשון (כלומר, ממנו אי אפשר ללכת אחורה, אבל אחר כך כן). y הוא מספר האפשרויות להגיע לסוף מהתא (כולל אחורה*). נמספר את התאים כך שהתא העליון מימין הוא 1, התחתון מימין הוא 2 וכן הלאה (כל פעם עולים למעלה שמאלה/יורדים למטה שמאלה). נשים לב כי: - x1 = 1, y1 = 2, x2 = 2, y2 = 3. - נתבונן בתא ה i+2. x(i+2) = x(i+1) + yj x(i+2) = 2x(i+1) + yj קל לראות את הנוסחאות הנ"ל בסרטוט. הוספתי קובץ אקסל פשוט שמראה את מספר האפשרויות עד 30 תאים. *מכיוון שאין משמעות להליכה אחורה באותו גובה (כלומר, אחורה ממש ולא אחורה למעלה/אחורה למטה), לא התחשבתי שאפשרות הזאת.

 

[yoavj1]

בפעם השניה זה כמובן y של i+2 ולא x

וגם ה j אמור להיות i. בכל מקרה, משתי הנוסחאות האלה אפשר להגיע לנוסחה: x(i+3) = x(i+2) + x(i+1) + xi

 

[כלמנ]

יש !!!

סידרת פיבונצ'י עם שלושה איברים n= n-1+n-2+n-3 הסבר:מאיבר ההתחלה(איבר n) ניתן להמשיך בשלוש צורות: 1 . לאיבר שלפניו (n-1) אפשרויות 2. לאיבר ש2 לפניו (n-2) ולהמשיך שמאלה כמו שחושב ב n-2 3. או לאיבר ש 2 לפניו ולחזור ל n-1 ומשם חייב לעבור ל n-3 ולכן n-3 אפשרויות. סדרת פיבונצ'י הזאת יוצאת: 1,2,4,7,13,24,44,81,149 ...

 

[בסג]

../images/Emo9.gif