解法 通俗易懂)"/>
简单的整数划分问题 (不一样的解法 通俗易懂)
将正整数n 表示成一系列正整数之和,n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ,k>=1 。
正整数n 的这种表示称为正整数n 的划分。正整数n 的不同的划分个数称为正整数n 的划分数。
输入
标准的输入包含若干组测试数据。每组测试数据是一个整数N(0 < N <= 50)。
输出
对于每组测试数据,输出N的划分数。
样例输入
5
样例输出
7
提示
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
这道题相信很多人都看过一个特别好的解,虽然有点难懂,但认真看一看还是可以看懂的。在百度百科中也有介绍整数划分
那种方法我就不说了。今天我来讲一个不一样的解法。请耐心看到最后。
首先做法类似,我们记n的包含m划分的个数为f(n,m) ,但这里的m就是构成n的最大值。也就是说在一系列数之和为n中必须出现m.
例如f(5,4)=1,因为 只有 5=4+1,所以只有一种.
然后我们再进行分类讨论:
- 1 若m>n,那么f(n,m)=0,因为m不可能构成n
- 2 若m=n,那么f(n,m)=1,因为只有一种 m=n
- 3.若m<n,就比较复杂需要讨论一下了。开始我以为就是f(n-m,m),其实不是,因为当m>n-m,f(n-m,m)=0,这样就导致f(n,m)=0,这样很明显是不正确的。重理思路,我们再看,在构成n-m的一串数字中它的最大值是m吗?不一定吧,可以是1-m的任意一个。那么f(n-m,m)就应该是这些情况的和。也就是:
f(n-m,m)= ( ∑ k = 1 m f ( n − m , k ) ) \displaystyle \left( \sum_{k=1}^m f(n-m,k) \right) (k=1∑mf(n−m,k));
最后的结果肯定是:
ans= ( ∑ m = 1 n f ( n , m ) ) \displaystyle \left( \sum_{m=1}^n f(n,m) \right) (m=1∑nf(n,m));
然后就直接计算就好了,贴代码吧
#include<cstdio>
#include<cmath>
using namespace std;
int f[55][55] = {0};
int ans[55]= {0};
//分类讨论并计算,把m看成构成n的一系列数中最大的一个
int F(int n,int m)
{int res = 0;if(n<m)ans = 0;if(m==n)ans= 1;else if(m<n)//这里for(int i = 1; i<=m; ++i)ans += f[n-m][i];return ans;
}
void Caculate()
{
// 计算f[n][m]for(int n = 1; n<=50; ++n)for(int m = 1; m<=50; ++m)f[n][m] = F(n,m);//保存结果for(int n = 1; n<=50; ++n)for(int i = 1; i<=n; ++i)ans[n] += f[n][i];
}
int main()
{
// freopen("out.txt","w",stdout);Caculate();int n;while(~scanf("%d",&n))printf("%d\n",ans[n]);return 0;
}
虽然以前学过这个问题的解法,但是刚好忘记了m的意义,又不想百度,然后误打误撞想出了这个解法。欢迎交流。
更多推荐
简单的整数划分问题 (不一样的解法 通俗易懂)
发布评论