עבור לתוכן

שאלה קשה ברקורסיה c++

Featured Replies

פורסם

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

כתוב פונקציה המקבלת מספר שלם 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

פורסם
  • מחבר

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

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

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

פורסם

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

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים