קבלתי לכתוב תוכנית

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

דוגמא:

לדוגמה, עבור n=5 ו-k=3 הפונקציה תדפיס את הפלט הבא:

5 0 0

4 1 0

3 2 0

3 1 1

2 2 1

עבור n=5 ו-k=2 יודפס הפלט הבא:

5 0

4 1

3 2


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

הקוד הנ"ל עובר קומפיציה בC, ועובד נכון. עבור n=8 ו k=3 הוא מדפיס :
242
152
062
503
413
323
233
143
053
404
314
224
134
044
305
215
125
035
206
116
026
107
017
008

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

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

קוד:

 
#define LEVEL 3
#include "iostream.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
void f(int n,int k,int s[50])
{
 
if (k==0 && n==0)
{
// cout<<"solution"<<endl;
for(int i=1;i<=LEVEL;++i)
cout<<s[i];
cout<<endl;
}
else if (k==0 && n!=0)
{ 
//cout<<"no solution"<<endl;
// cout<<s<<endl;
// cout<< k<<n<< endl;
}
else 
{
for (int i=0;i<=n;++i)
{
//cout<<"f:"<<endl;
//cout<<s<<endl;
//cout<<k<<n<<i<<endl;
s[k]=i;
f(n-i,k-1,s);
}
}
}
 
void main()
{
int s[50];
for(int i=0;i<=49;++i)
s[i]=0;
f(8,LEVEL,s);
}

קודם כל תודה

עכשיו מה המשמעות של LEVEL?
ולמה הגדרת את המערך בגודל 50?
עכשיו חשבתי כדי להתגבר על על ההדפסות הכפולות צריך פשוט ללכת עד חצי המספר או שורש המספר לפי הדוגמא של n=5 k=2 אז תמיד הראשון זה המספר +כמה אפסים אחר כך אחד פחות עד ההחצי כי אחרי החצי זה יתחיל לחזור על עצמו

המערך ששומר את מחרוזת הפתרון נקבל שרירותית ל50.
וכן, גם אני בדיוק חשבתי ללכת עד חצי המרחק. החלפתי את n בn/2-1. לא עבד לי.

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

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

קוד:

 
#define LEVEL 4
#include "iostream.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
void f(int n,int k,int s[50])
{
if (k==0 && n==0)
{
for(int i=0;i<=LEVEL-1;++i)
cout<<s[i];
cout<<endl;
}
else if (k==0 && n!=0)
{ }
else 
{
for (int i=0;i<=n;++i)
{
 
//cout<<"k="<<k<<"i="<<i<<"test="<<s[LEVEL-k]<<endl;
if (s[LEVEL-k-1]<=i)
{
	s[LEVEL-k]=i;
	f(n-i,k-1,s);
}
}
}
}
 
void main()
{
int s[50];
for(int i=0;i<=49;++i)
s[i]=0;
f(8,LEVEL,s+1);
}

למה שוב פעם הגדרת את s בגודל 50?
ומה זאת הקריאה הזאת של S+1?
ולמה צריך את הlevel שהוא ה k המקסימלי?

אפשר להסתמך קצת על המתמטיקה בשביל לחסוך כאן בזכרון:
נניח עבור הקלט n=5, k=3, בטור הראשון יהיו את המספרים 0 ו1, בעוד בתור השני יהיו את המספרים 0, 1 ו2.
בעצם, בכל טור (מלבד האחרון) המספר הכי נמוך יכול להיות 0, והמספר הכי גבוה יכול להיות שורש K של N.
עבור טור שלישי: שורש 3 של 5
עבור טור שני: שורש 2 של 5
וכך הלאה.

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

ה"כיעור" בדוגמת הקוד שאני אביא נובע בגלל ההדפסה הדרושה, לכן רשמתי גם בpython וגם בC++ (דווקא C++ ולא C, כי יש שם את std::string)

הקוד בpython:

קוד:

from math import ceil

def f(n, k, prev = "", caller = 0):
	if k == 1:
		if n >= caller:
			return n
		return None
	root = int(ceil(n**(1.0 / k))); # n**(1.0/k) = root K of N
	for x in xrange(caller, root + 1):
		l = str(prev) + str(x) + " "
		res = f(n-x, k-1, l, x)
		if res is not None:
			print l + str(res)
	return None

ובC++:

קוד:

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int f(int n, int k, string previous, int caller) {
		if (k == 1) {
				if (n >= caller) {
						return n;
				}
		} else {
				int root = (int)pow(n, 1.00 / k);
				root = (int)ceil(root);
				for (int i = caller;
						i <= root + 1;
						i++) {
						string newPrev(previous);
						char *buffer = new char[255];
						sprintf(buffer, &quot;%d &quot;, i);
						newPrev += buffer;
						int result = f(n - i, k - 1, newPrev, i);
						if (result != -1) { // Not failing result
								cout << newPrev << result << endl;
						}
				}
		}
		return -1;
};

int main() {
		int n, k;
		cout << &quot;Enter n: &quot;;
		cin >> n;
		cout << &quot;Enter k: &quot;;
		cin >> k;
		f(n,k, &quot;&quot;, 0);
		return -1;
}

אתה יכול אולי לרשום את זה ב C גיא אני אמור לעשות את זה בC
אני גם חשבתי לכיוון הזה אבל אחרי כמה זמן לא היה לי כבר עצבים למצוא את הסדר המתמטי

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

python זו שפה מאוד קריאה, ואתה יכול להבין לפיה איך לממש.