整数划分
题目：
"The problem is, given an positive integer N, we define an equation like this:
N=a[1]+a[2]+a[3]+...+a[m];
a[i]>0,1<=m<=N;
My question is how many different equations you can find for a given N.
For example, assume N is 4, we can find:
4 = 4;
4 = 3 + 1;
4 = 2 + 2;
4 = 2 + 1 + 1;
4 = 1 + 1 + 1 + 1;
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"
A.递归函数法
用函数f(n,m)表示：把数字n拆分所能得到的式子个数，其中所拆分得到的数中最大不超过数字m。故在原题中所求的即为f(n,n)。
在讨论f(n,m)时，可大体上分为四种情况讨论：
1.当n=1或m=1时，f(n,m)=1。//最基本的一点
1.当n=m时,f(n,m)=f(n,n-1)+1。
因为数字n要拆分成含n的几个数字之和，只有n=n这一个式子。
2.当n<m时，f(n,m)=f(n,n)。
3.当n>m时，f(n,m)=f(n,m-1)+f(n-m,m)。//难点，也是整个递归法的重点
此时还可分为两种情况讨论：
a.当划分中不包含m时：
因不包含m，故剩下的划分数都比m要小，其中最大的为m-1,因此，这种情况下的划分个数为f(n,m-1)；
b.当划分数包含m时：
即{m,(a1,a2,a3，...,ai)},其中（a1,a2,a3,...,ai）的和为n-m，此时m还有可能再次出现，故此种情况下的划分个数为f(n-m,m)；
综上f(n,m)=f(n,m-1)+f(n-m,m)。
代码如下：
1 #include<iostream> 2 using namespace std; 3 4 int f(int n,int m) 5 { 6 if(n<1 || m<1) return 0; 7 if(m==1 || n==1) return 1; 8 if(m>n) return f(n,n); 9 if(m==n) return (f(n,m-1)+1); 10 if(n>m) return (f(n,m-1)+f(n-m,m)); 11 } 12 13 int main() 14 { 15 int n; 16 while(cin>>n) 17 { 18 cout<<f(n,n)<<endl;; 19 } 20 return 0; 21 }
//递归函数虽然思路简单，但十分耗时，当数据较大时就不能用了！
B.母函数法. 母函数： 对于任意数列a0,a1,a2...an 即用如下方法与一个函数联系起来即： G(x) = a0 + a1x + a2x^2 + a3x^3 +....+ anx^n 则称G(x)是数列的生成函数(generating function)即母函数。 在上面题目中构造的母函数为g(x)=(1+x^1+x^2+x^3+...+x^i)(1+x^2+x^4+x^6+...+x^2i)(1+x^3+x^6+x^9+...+x^3i)...(1+x^n+x^2n+...+x^nj) 代码如下：1 #include<iostream> 2 using namespace std; 3 4 #define M 200 5 6 int c1[M],c2[M]; 7 8 int main() 9 { 10 int n; 11 while(cin>>n) 12 { 13 memset(c1,0,sizeof(c1)); 14 memset(c2,0,sizeof(c2)); 15 c1[0]=1; 16 int j,i,k; 17 for(i=1;i<=n;i++)//i代表的是第i个括号 18 { 19 for(j=0;j<=n;j++)//j代表的是第i个括号前i-1个括号全部相乘后,所得到的的一个新的大括号里的x的指数 20 for(k=0;k+j<=n;k+=i)//k代表的是第i个括号里的x的指数
21 { 22 c2[k+j]=c2[k+j]+c1[j]; 23 } 24 for(j=0;j<=n;j++) 25 c1[j]=c2[j]; 26 memset(c2,0,sizeof(c2)); 27 } 28 cout<<c1[n]<<endl; 29 } 30 return 0; 31 }
1、枚举的常用方法
2、C#设计模式之一：开篇
3、HTTP协议详解
4、什么是DTFT？（图）
5、类型系统的分类