נתונים לנו המיספרים 1 2 3 4

צריך למצוא כמה אפשרויות יש בסה"כ אם נשתמש רק במספרים אלו כדי לקבל סכום כולל של 10

מותר רק חיבור

כלומר:

442=10

2222=10

1234=10

1243=10

1111111111=10

1333=10

2222=10

3334=10

השאלה היא

כמה אפשרויות כאלו יש לנו בסה"כ ?

רקרוסיה למדתם?

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

נראה לי שהוא מתכוון לפתור את השאלה ללא שימוש בתכנית מחשב. (השאלה הופיעה באולימפיאדת מדעי המחשב)

סתם שאלה, למה הצעת רקורסיה ולא לולאה?

כי אתה יכול להסתכל על זה כעץ עם מקסימום של 4 עלים בכל שלב ועל מבנה כזה יותר קל לעבור ברקורסיה.

f calculates possibilities for sum of n using 1,2,3,4:

f(n) = f(n-1) + 1*(n mod 4 == 0) + 1*(n mod 3 == 0) + 1*(n mod 2 == 0) + 1*(10 mod 1 == 0)

base: f(1) = 1

then run f(10)

הכוונה ב-n mod x == 0, זה תוסיף עוד 1 אם n modulo x שווה לאפס.

בטח יש דרך יותר פשוטה לפתור את זה, אבל מהכפאת לי.

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

זה לא רקורסיה רגילה, לדעתי אפילו מדובר על backtracking.

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

מה backtracking?? למה זה נחוץ? הפתרון למעלה הוא ב-O(n^2), למה צריך יותר?

אלא אם אתה מוצא איזה חור שאני מפספס.

כוסאמאשך, אני יושב עכשיו חצי שעה מנסה להבין למה הקוד שלך עובד למרות שאין בו הגיון. ובסוף מסתבר שסתם במקרה זה נותן תוצאה נכונה עבור 4.

f(5)= f(4)+1+0+0+0 = 9

f(4)= f(3)+1+1+0+1 = 8

f(3)= f(2)+1+0+1+0 = 5

f(2)= f(1)+1+1+0+0 = 3

f(1)= 1

לעומת זאת הסכומים של הצירופים הבאים הבאים שווים 5:

14

41

23

32

113

131

311

221

212

122

1112

1121

1211

2111

11111

קצת יותר מ-9...

הדרך הנכונה לפתור את זה היא

f(int n)
{
 int sum = 0;
 for (int i=1;(i<=4)&&(n>i);i++)
 sum+=f(n-i);
 return sum+1;
}

אף אחד לא הגדיר שיש חשיבות לסדר

גם בלי חשיבות הקוד שלך לא נכון. עבור 2 יש 2 צירופים 11 ו-2 ולפי הקוד שלך יש 3 צירופים.