I am given this problem:
We are going over recursion in my class and I do not quite understand it, I was wondering if someone can help me with this problem
let c(n) be the number of different group integers that can be chosen from the integers 1 through n-1, so that the integers in each group add up to n (for example, n=4=[1+1+1+1]=[1+1+2]=[2+2]). Write a recursive definition for c(n) under the following variations:
a) You count permutations. For example, 1,2,1 and 1,1,2 are two groups that each add up to 4
b)you ignore permutations
I know permutations is how many ways you can arrange a set of numbers, so is my code below correct? I get an answer of 7? Here is my code for part a:
int recurse (int n);
int main(){
int a=4;
int sum_perm;
sum_perm=recurse(a);
cout<<sum_perm-1<<endl;
//Can I do -1 here because it should be from a group of integers from 1 to n-1?
return 0;
}
int recurse(int n)
{
int sum = 1;
if (n == 1){
return 1;
}
for(int i = 1; i < n; i++){
sum += recurse(n - i);
}
return sum;
}
For part B, if I am not counting permutations, what am I counting? Here is my code for part b:
int without (int n, int max);
int main(){
int a=4, b =3;
int sum_without;
sum_without=without(a,b);
cout<<sum_without<<endl;
system("Pause");
return 0;
}
int without(int n, int max)
{
if(n == 1 || max == 1){
return 1;
}
else if (n == max){
return 1 + without(n, n-1);
}
else{
return without(n,max-1) + without(n-max, max);
}
}
Aucun commentaire:
Enregistrer un commentaire