整数划分问题

2015-09-13

问题描述

将正整数n表示成一系列正整数之和，n=n1+n2+...+nk，其中有n1>=n2>=...>=nk>=1, k>=1，这种表示成为正整数n的划分。如果限定k则称为n的k划分。

基本思路

考虑n的划分。

记F[n,k]为n的1划分+2划分+…+k划分的数目，则n的划分即为F[n,n]。

则n的k划分为F[n,k]-F[n,k-1]。

考虑以下5种情况：

1. n=1，显然只能有一个情况，F[1,]=1
2. k=1，只有一个划分，F[,1]=1
3. n=k，如果划分中有n，则只有一种情况；如果没有n，则最大的数为n-1，此时划分数为F[n,n-1]。因此加起来就是F[n,n]=1+F[n,n-1]
4. n<k，显然k不能超过n，因此等价于n=k，F[n,k]=F[n,n]
5. n>k，如果有k划分，则等价于F[n-k,k]；否则没有k划分，等价于F[n,k-1]；加起来就是F[n-k,k]+F[n,k-1]。

因此得到伪代码1：

[CODE]

int fun(int n, int k){
	if (n == 1 || k == 1) return 1;
	if (n <= k) return 1 + fun(n, n - 1);
	else return fun(n - k, k) + fun(n, k - 1);
}

伪代码2：放苹果

[CODE]

int fun(int n, int k){
    if (k == 1) return 1;
    if (n == 0) return 1;
    if (n < 0) return 0;
    return fun(n - k, k) + fun(n, k - 1);
}

题目

简单的整数划分问题

描述

将正整数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个盘子上，允许盘子放空，问有几种放法。