חידה במחשבים

טיקטי

New member
חידה במחשבים

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

טיקטי

New member
אני לא צריך את התשובה הצגתי את

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

טיקטי

New member
בעצם אני חושב שאי אפשר

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

טיקטי

New member
בעצם אני לא חושב שצריך בכלל תוכנית

מחשב בשביל לפתור את זה אבל סביר להניח שאני טועה: נגיד שהנקודה היא A(m,n אז בעצם צריך למצוא מה מספר האפשרויות שנוכל למקם n תוך m+n צעדים כי הרי כדי להגיע מהנקודה A לנקודת מפגש הצירים צריך m+n צעדים בטוח כלומר כל מה שצריך זה רק למקם את n הצעדים ואז לפתור עפ"י נוסחה של קומבינטוריקה למרות שאפשר לפתור עים תוכנית מחשב
 

Fingertip

New member
תשובה מדוייקת../images/Emo70.gif

והנוסחה היא:
(n+m)!/(n!*m!)​
אהד.
 

hitchkok

New member
אגב, עבור המקרה הפרטי

שבו m=n יש סדרת מספרים הנקראת סידרת קטלן (catalan) שהאיבר הn (או m) שלה יתן את הפתרון. (ותודה לyak141)
 
למעלה