整数划分问题

整数划分问题

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]

1
2
3
4
5
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个盘子上,允许盘子放空,问有几种放法。