אתגר התכנות 3: קוף על רשת!

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

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

יש מגבלה נוספת וחשובה מאד: הקוף אינו יכול לנוע לצומת שסכום הספרות של הקואורדינטות שלו גדול מ-19. לדוגמה, הוא לעולם לא יוכל להגיע לצומת 96,51 כי 9+6+5+1 יותר גדול מ-19. במקרה של קואורדינטה שלילית, אנחנו פשוט מתעלמים מהסימן ומחשבים את הסכום כאילו היא היתה חיובית.

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

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

להרשמה
הודע לי על
5 תגובות
מהכי חדשה
מהכי ישנה לפי הצבעות
Inline Feedbacks
הראה את כל התגובות

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

כמובן שאפשר לפתור את זה תכנותית 🙂
ואני ארשה לעצמי לכתוב אצ הפיתרון כי הוא לא באמת מעניין אלא הדרך אליו

n=19
[עריכה: הסרתי את הנוסחה. גם אם הדרך היא המעניינת, הפתרון עלול לתת רמזים לאופן שבו מגיעים אליו. -עידו]

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

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

תודה,
וסליחה על הספוילר