jeudi 5 mars 2015

Recursion function -counting permuation and ignoring permutation


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