קומבינטוריקה

[littlerunaway]

למי בא לעזור לי עם שאלה?

 

http://i.imgur.com/xCC5RK8.jpg

[-ליאור]

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

[littlerunaway]

נראה לי שהבנתי. תודה. לגבי הצבעים, מדובר בעצם ב-3 אפשרויות לכל מרצפת כרגיל? 

[littlerunaway]

אוקיי, אני יכולה לעשות משהו כזה?

 

 

(T(n)=3*T(n-1)+(3^3)*T(n-3

 

3>n לכל T(n)=3^n תנאי התחלה

[אורח guest]

זאת בדיוק התשובה.

אם תרצי להרשים את המתרגלים תוכלי גם לפתור את הרקורסיה ולצרף את הנוסחא הסגורה: http://i.imgur.com/6pT5JtE.gif

[littlerunaway]

המממ... אני אשאיר למישהו אחר להרשים אותם. 

תנאי ההתחלה שרשמתי הוא קביל? כי אני קצת לא בטוחה לגביו. 

[אורח אורח]

הוא נכון, אם את רוצה להיות יותר מדויקת תצייני במקום n<3 משהו כמו n=0,1,2.

(אם את רוצה משהו שבטוח יקבלו, את יכולה לרשוםT(0),T(1),T(2)a ולפרט (בכמה מילים) למה כל אחד מהם שווה למה שהוא שווה.)

[littlerunaway]

התהייה שלי היא יותר עקרונית. הסברתי איך הגעתי ל n^3 . השאלה היא אם באופן עקרוני בשאלות כאלה זה קביל לתת נוסחה מפורשת בתור תנאי התחלה, כי בדרך כלל (לפחות בתירגולים) תנאי ההתחלה היה מספר קונקרטי ולא נוסחה. אם נגיד במקום 3 היה לי 10. היה יותר נכון לרשום את הערך המתקבל עבור כל N<10 או שנוסחה הייתה מספיקה?

[אורח אורח]

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

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

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

(שוב - משפט המפתח הוא שהעיקר שתדעי להסביר את תנאי ההתחלה.)

[littlerunaway]

אחלה. תודה