קיבלנו שאלה דיי מסובכת (לטעמי) לעבודת בית ואני לא מצליח להתקדם איתה לשום מקום:

כתוב פונקציה המקבלת מספר שלם n חיובי ומספר נוסף k. הפונקציה תדפיס את כל הקומבינציות (עם חזרות) האפשרויות לקבלת n על ידי חיבור של k מספר גדולים מ 0.

לדוגמא עבור k=3 n=5 יודפסו שש השורות הבאות:

1+1+3

1+2+2

1+3+1

2+1+1

2+2+1

3+1+1

הערה: אין חשיבות לסדר הדפסת השורות

חתימת הפונקציה חייבת להיות

void sum (int n, ink k);

אסור שימוש בלולאות for או while. רק בעזרת פונקציות רקורסיביות ועזר.

אשמח לשמוע רעיונות או הצעות איך להתקדם...

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

שים לב לאבחנה הבאה:

נניח שהחלטת לשים X בתור המספר הראשון.

אזי אתה יכול לקחת את כל הדרכים לכתוב את n-X כסכום k-1 מספרים, ולהוסיף "+X" למחרוזות.

function GetListForX(n , k, X):
1. list_for_x <- empty list
2. tmp_list <- f(n-X, k-1)
3. for each string S in tmp_list:
  3.1 newS <- concat( "X +" , S )
  3.2 append newS to list_for_x
4. return list_for_x

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

עוד לא למדנו רשימות ככה שקשה לי קצת להבין את הקוד שכתבת

גם שמתי לב שיש לך בקוד שימוש ב for ואסור לנו להשתמש בלולאות בשאלה

אני מנסה לחשוב מה המקרה בסיס ולא מצליח למצוא אותו

לא התקדמתי עדיין לשום כיוון עם השאלה הזאתי

אי אפשר לפתור את השאלה בלי רשימות או מערכים.

מקרה בסיס, כמו בכל רקורסיה, הוא כש-k=1.

במערכים מותר להשתמש

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

אני אשמח לדעת אם מישהו עולה על דרך לפתור את זה

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

אפשר לפתור ללא רשימות או מערכים, ע"י העברת prefix של מחרוזת אל הפונקציה.

function PrintListForX(n, k, prefix, X):
1. newPrefix = concat( prefix, "X + ")
2. PrintList(n-X, k-1, newPrefix)

תוכל קצת לפשט את מה שרשמת?

מה בדיוק התפקיד של המשתנים prefix ו x, ומה אמורה לעשות הפונ' concat?

concat מדביקה שתי מחרוזות.

concat("abc", "xyz") מחריזה את המחרוזת "abcxyz".

prefix היא מחרוזת שמכילה את הקידומת לכל המחרוזות שהפונקציה תדפיס או תייצר. הרעיון הוא לייצר את המספרים אחד אחד, וכל פעם להוסיף את המספר הנוכחי (X) כקידומת ("+X") לכל המחרוזות שיודפסו עבור בניית המספר N-X על ידי K-1 מספרים.

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

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

קודם כל היא מנסה שהמספר הראשון יהיה 1. אז הפונקציה קוראת לעצמה על n=9 ו-k=3 (הקריאה לפונקציה מחזירה רשימה של מחרוזות מהצורה "a+b+c" כש-a,b,c הם מספרים שסכומם 9), ומוסיפה לכל אחת מהתוצאות את המחרוזת "+1".

אח"כ הפונקציה מנסה שהמספר הראשון יהיה 2, ואז היא קוראת לעצמה עם n=8 ו-k=3, ומוסיפה לכל אחת מהתוצאות את המחרוזת "+2".

וכן הלאה וכן הלאה.

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

אגב, לגרום לסטודנטים לפתור את התרגיל הזה בלי שימוש בvector זה פשוט התעללות (לפחות ב-string אתם משתמשים?)

לא נתתי לך את כל הפתרון, רק חלק אחד.

אני אוסיף עוד רמז:

איך מתרגמים לולאת for פשוטה לפורנקציה רקורסיבית? ככה:

 for i = 1 to N:
   print i

can be written as:

 function printNums(i):
 if i > 1:
   printNums(i-1)
   print i

טוב האמת קצת נוצר לי בלאגן בראש. אני לא מצליח להבין איך הרקורסיה עובדת ואת הקשר למחרוזות

אני אנסה לשבת על מאוחר יותר להבין איך זה עובד

ואגב מותר לנו מחרוזות

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