אבן דומינו מכסה שתי משבצות אופקיות סמוכות או שתי משבצות אנכיות סמוכות במטריצה של משבצות.

א. כתוב תכנית שהקלט שלה הוא מספר שלם חיובי N, 2£ N £100 , והפלט שלה הוא מספר הדרכים השונות לכיסוי באמצעות אבני דומינו של מטריצה בגודל 2XN.

ב. ענה על סעיף א' עבור N זוגי ומטריצה בגודל 3XN.

למשל, ישנן 3 דרכים שונות לכיסוי מטריצה בגודל 2X3:

וישנן 11 דרכים שונות לכיסוי מטריצה בגודל 3X4:
אני ניסיתי לעשות את א, וגיליתי ש כדי למלות מטריצה בגודל 2*2 צריך 2 דרכים.
3*2=3 דרכים
4*2= 5 דרכים
6*2= 8 דרכים

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

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

תניח נכונות המקרה עבור n, ותראה שזה נכון גם עבור n+1 => מכאן נכון לכל n.

[ זיו ]
[ fat fish ]

מה זאת אומרת N ?
לדוגמא אני מניח נכונות של 2X3 ואם זה נכון גם ב 2X4 אז זה נכון לכל מספר?

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

[ זיו ]
[ fat fish ]

אוקיי,הבעיה שלנו היא לכסות לחלוטין מטרציה בגודל של n על 2 בקוביות דומינו שגודלן 1 על 2.
האלגוריתם שאני חושבת עליו הוא כזה :
1. תאתחל את המטריצה כך שכל המשבצות יהיו ריקות (למשל,מערך דו מימדי שכל איבר בו מכיל 0)
2. קרא לפונקציה המרכזית. הפונקציה מקבלת שני פרמטרים : מערך שמייצג את המטריצה,ומספר הקוביה שאנחנו מנסים להניח על המטריצה כעת.
3. רוץ בלולאה על כל המשבצות שבמטריצה,עד שתמצא משבצת ריקה.
4. לא מצאת משבצת ריקה בשלב 3? מזל טוב! המטריצה מכוסה לחלוטין ואפשר להדפיס אותה בתור פתרון.
5. מצאת משבצת ריקה בשלב 3? בדוק האם המשבצת מימין לה (אם קיימת) ריקה והאם המשבצת מתחתיה (אם קיימת) ריקה.
6. אם המשבצת מימין ריקה,אתה יכול להניח קובית דומינו לרוחב. מלא את שתי המשבצות בערך של הקוביה העכשווית,וקרא לרקורסיה תוך כדי שאתה מעלה את מספר הקוביה העכשווית.
7. אם המשבצת מתחת ריקה,אתה יכול להניח קובית דומינו לאורך. מלא את שתי המשבצות בערך של הקוביה העכשווית,וקרא לרקורסיה תוך כדי שאתה מעלה את מספר הקוביה העכשווית.

אחרי שתפתור את סעיף א',יהיה יותר קל לעשות את סעיף ב'.