את אתגר התכנות השלישי אני מביא, שלא כרגיל, עוד לפני שפתרתי אותו בעצמי. למה? כדי שיהיה לכם על מה לחשוב בחג. זיכרו: לא לפרסם פתרונות, רעיונות או כיוונים לפיתרון בתגובות! הדיונים ה"רשמיים" על האתגרים יתחילו בפוסט הבא בסדרה, בו אתן את הפתרון שלי לשאלה של המרת המספרים מייצוג רומי לעשרוני ולהיפך.
אז יש לנו קוף שמטפס על רשת שתי-וערב של חבלים. כל צומת (מפגש בין שני חבלים) מסומן על ידי שני מספרים שלמים – קואורדינטות X ו-Y. הקוף מתחיל בצומת 0,0 ויכול לנוע בכל פעם צעד אחד בלבד לכיוון אחד בלבד – כלומר לעבור לצומת עם X גדול ב-1 מהקודם, או עם X קטן ב-1 מהקודם, או עם Y גדול ב-1 מהקודם, או עם Y קטן ב-1 מהקודם (גם מספרים שליליים מותרים). לא ניתן לנוע באלכסון.
יש מגבלה נוספת וחשובה מאד: הקוף אינו יכול לנוע לצומת שסכום הספרות של הקואורדינטות שלו גדול מ-19. לדוגמה, הוא לעולם לא יוכל להגיע לצומת 96,51 כי 9+6+5+1 יותר גדול מ-19. במקרה של קואורדינטה שלילית, אנחנו פשוט מתעלמים מהסימן ומחשבים את הסכום כאילו היא היתה חיובית.
והנה השאלה: כאמור, הקוף מתחיל בצומת 0,0. לכמה צמתים שונים, כולל זה ההתחלתי, הוא יכול להגיע בסך הכל?
החידה הזו מעניינת כי יש כמה אפשרויות למיטוב של האלגוריתם, מכיוונים שונים לגמרי, ואפשר בעיקרון לפתור חלק נכבד ממנה (אולי אפילו את כולה?) על הנייר. שנה טובה ובהצלחה!
זה מרגיש לי יותר כמו שאלה במבחן על סדרות חשבוניות ולא כמו שאלת תכנות.
לטוב ולרע, יש קשר עמוק מאד בין תכנות – והכוונה לתכנות אמתי, לא העתקת קוד מהרשת וקריאה לפונקציות שמישהו אחר כתב – לבין מתמטיקה, וקצת חשיבה מראש יכולה לשפר להפליא ביצועים של תוכנות (היית בהרצאה שלי בכנס המייקרים האחרון? 🙂 ).
יחד עם זאת, אפשר לפתור את שאלת הקוף גם בתכנות נטו, בלי שום טריק מתמטי – ובהתחשב בזה שאני עצמי לא אלוף העולם במתמטיקה (בלשון המעטה), אתה יכול להיות בטוח שהחידות שאני אביא לא מחייבות פיתוחים מתקדמים…
כמובן שאפשר לפתור את זה תכנותית 🙂
ואני ארשה לעצמי לכתוב אצ הפיתרון כי הוא לא באמת מעניין אלא הדרך אליו
n=19
[עריכה: הסרתי את הנוסחה. גם אם הדרך היא המעניינת, הפתרון עלול לתת רמזים לאופן שבו מגיעים אליו. -עידו]
אין צורך בפיתוחים מתקדמים אגב בשביל להגיע לנוסחה המתמטית.
זה ברמה של חטיבת ביניים אם אני זוכר נכון מתי למדתי סדרות חשבוניות פשוטות.
ערכתי את התגובה. בבקשה להתחשב באחרים ולא לתת רמזים משום כיוון. חוץ מזה, אני לא יכול לומר בוודאות כי עדיין לא פתרתי בעצמי ואין לי אפשרות להתעמק בזה ממש עכשיו – אבל נדמה לי שהפתרון שלך שגוי. קרא שוב בתשומת לב את כל התנאים בשאלה.
אני מקווה שלא פיספסתי משהו 🙂
אני אשמח אם אחרי שתפתור את זה תשווה את התוצאה שקיבלת לנוסחה שלי ותעדכן אותי.
תודה,
וסליחה על הספוילר