12-22-2009 12:10 PM
hello,I had a C++ exam which I did well except the last problem.
the last problem
Let m,n,and sum be positive integers.In this problem we are interested in length-n arrays whose entries are integers in the set{1,2,....,m} such that the sum of the enteries of the array is less than or equal to sum.
Write a recursive function,which given m,n,and sum,prints all such arrays.Your function should also compute the total number N of those arrys.
Examples:
For m=3,n=3,and sum =4,the function should print
1 1 1
1 2 1
2 1 1
thus N=4
For m=3,n=3,and sum=5,the function should print
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 3 1
2 1 1
2 1 2
2 2 1
3 1 1
thus N=10
Form=3,n=4,and sum=6, the function should print
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 3 1
1 2 1 1
1 2 1 2
1 2 2 1
1 3 1 1
2 1 1 1
2 1 2 1
2 2 1 1
3 1 1 1
thus N=15
The time of your function should be in the order of the output size N(and not m to power n).That is ,you are epected to avoid recursive branches which do not eventually lead to valid arrays.
"
Which way is the best way to solve this problem,I used a for loop,and placed inside it the same recursive function.What kinds of parameter should have I used(I used a pointer to an array,int,int ,itn)
I did not know the base case so I placed When I occurs final time.
Solved! Go to Solution.
12-29-2009 03:13 AM
Hey Frodo,
nice question 😄 However, the answer you are asking for would be better to discuss with your proffesor or on some general programming or algoritmization forums, instead of measurement focused one.
Regards,
Stefo
12-30-2009 11:30 AM
12-30-2009 11:56 AM