递归函数-counting置换与忽略置换

Question

我被问到这个问题：

我们在课上复习递归，我不太明白，我想知道是否有人能帮我解决这个问题。

设c(n)是可以从整数1到n-1中选择的不同组整数的数目，这样每个组中的整数加起来就等于n(例如，n=4=1+1+1+1=1+1+2=2+2)。在以下变体下为c(n)编写递归定义：

( a)排列数。例如，1,2,1和1,1,2是两个组，每个组加起来有4个

(B)你忽略排列

我知道排列是有多少种方法可以安排一组数字，那么我下面的代码是正确的吗？我得到的答案是7？这是我的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;
}

对于B部分，如果我没有计算排列，我在计算什么？以下是我为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);
        }
}

Answer 1

您不显示生成产生和的数字组合的任何代码。链接到关于隔断的wiki文章。

在这种情况下，目标是计数组合和/或排列的数量，这可能是可能的，而不实际生成一组组合。这里不确定递归是否有帮助，但如果您传递足够的变量，则可以将任何循环转换为递归。

示例“分区”

1合计为1：

1

2个总和为2的组合：

1 1
2

3项总和为3的组合：

1 1 1
1 2
3

5个总和为4的组合：

1 1 1 1
1 1 2
1 3
2 2
4

7个总和为5的组合：

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
1 4
2 3
5

11个总和为6的数字组合：

1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
2 2 2
1 5
2 4
3 3
6

Answer 2

我建议直接考虑组合。虽然这似乎是比较困难的情况，但一条简单的规则使它变得微不足道。

计算的数字是递减的。

这要求您跟踪最后一个数字，但确保不计算1 5和5 1，因为前者是不可能的。