2 שאלות בריקורסיה מתמטית.

[dandean]

שאלה 1

----------

נתונה קבוצה של n סימנים שונים זה מזה המשוכנים במעגל שגודלו n .

נניח f(n,k)ddd הוא מספר האפשרויות לבחירת k סימנים מקבוצת הסימנים הנותנה כך שלא יבחרו שני סימנים הנמצאים

במיקומים עוקבים. מהי הנוסחא הריקורסיבית המתאימה.

 

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

f(n-2,k-1)ddd וישנה אפשרות שבחרנו סימן מקצוות המערך f(n-1,k-1)ddd

אבל זה לא מסתדר לי לכלל תוצאה סופית.

 

 

שאלה 2

---------

נסמן את f(n,k)= c(n,k)ddd

ידוע ש- f(n.k) = f(n-1,k-1)+f(n-1,k)ddd

מהי הנוסחא המפורשת של נוסחת הנסיגה

A(n.k)=A(n-1,k-1)+A(n-1,k)+1

 

בסה"כ מוסיפים 1 לנוסחא הראשונה.

 

מבין כל האשפרויות (השאלון אמריקאי)

התשובה:

c(n.k)+n...ddd

נראית לי הכי נכונה מאחר וה-1 נצבר עד שמגיעים לתנאי העצירה. יש דרך יותר מתמטית לגשת לזה.

[stanly]

שאלה 1: השאלה אומרת שזה מעגל כלומר אין קצה ואמצע. בוחרים אחד ואז בוחרים K-1 מתוךN-3  שנותרו (הוא והשכנים שלו אסור לבחור)

 

שאלה 2: לא נראה שהאחדים מסתכמים ל-N אלא להרבה יותר.(כל A() משאיר שני A() שכל אחד מהם מוסיף 1. אז ס"כ NK או משהו כזה(עריכה: בעצם http://www.codecogs.com/gif.latex?O(nk%5E2) פלוס מינוס קבוע לא מעניין :] ))

[stanly]

שאלה 1 יותר מסובכת ממה שחשבתי, הפתרון לא נכון.

[dandean]

תודה על הנסיון.

תיקון לשאלה 1 האיברים נמצאים במערך ולא במעגל.

[ohad]

אם זה מערך זה כמעט כמו שאמרת:

f(n,k)=2*f(n-2,k-1)+(n-2)*f(n-3,k-1)

 

שים לב שצריך להוריד גם את מה שבחרת וגם את מה שלידו, לכן זה n-2 וn-3 בהתאמה.

תנאי העצירה:

f(n,1)=n

 

(הנוסחא הזו נותנת חשיבות לסדר הבחירה, האם יש אזכור של זה בשאלה?)

[stanly]

זאת הבעיה:

 

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

[ohad]

@@stanly, צודק.

נפתור את זה בצורה אחרת (והפעם נכונה!):

 

נסתכל על הסימן הראשון:

אפשר לבחור את הראשון או לא לבחור אותו,

אם בחרנו אותו נשאר לבחור סימן פחות, מבין 2 סימנים פחות.

אם לא בחרנו אותו נותר אותו מספר סימנים מבין סימן אחד פחות. 

כלומר:

f(n,k)=f(n-1,k)+f(n-2,k-1)

 

תנאי עצירה:

f(n,k)=0

אם n>k.

 

זה פותר גם את הבעיה של הסדר שהזכרתי קודם.

[dandean]

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

[ohad]

נ"ל שבאמת צריך להוסיף גם תנאי עצירה:

f(1,1)=1

וזה פותר גם את שאלתך.

 

אבל אני לא מספיק מרוכז כדי לוודא את זה.

[RealMadrid]

איזה מקצוע זה ?

[ohad]

קומבינטוריקה (כנראה "קומבינטוריקה למדמ"ח").

 

לפחות שם אני למדתי את זה...