自然数划分

试题描述

输入任意一个大于1的自然数总可以表示为若干个小于n的正整数之和，求拆分的方案数。

（1+2与2+1为一种方法）

输入

第一行为一个正整数n。

输出

输出可以拆分的方案数。

输入示例

输出示例

其他说明

2<=n<=100.

思路：递！推！
y=f(k,n); //把n拆成y份，其中最大的是k
y`=g(k,n); //把n分成y`份，其中最大的数小于等于k
↓
g(k,n)=f(1,n)+f(2,n)+f(3,n)+...+f(k,n) //第二行函数定义的数学表达式
g(k-1,n)=f(1,n)+f(2,n)+f(3,n)+...+f(k-1,n)
由此得出：
g(k,n)=g(k-1,n)+f(k,n)
↓
f(k,n)=g(k,n-k) //减掉一个最大的（参照上面数学表达式）
g(k,n)=g(k-1,n)+g(k,n-k); //***递推公式***
↓【分类讨论】
k=1时， g(1,n)=1
k>n时，无意义
k<n时， g(k,n)=g(k-1,n)+f(k,n);

 1 #include <iostream>
 2 
 3 using namespace std;
 4 int ans,x;
 5 int ways(int n,int k)
 6 {
 7     if(n<k) return 0;
 8     if(n==k || k==1) return 1;
 9     return ways(n-k,k)+ways(n-1,k-1);
10 }
11 int main()
12 {
13     scanf("%d",&x);
14     for(int i=2;i<=x;i++) ans+=ways(x,i);
15     printf("%d",ans);
16     //system("pause");
17     return 0;
18 }

自然数划分