pku 1664 分苹果(整数划分)

偏执的太偏执、 2022-08-13 00:50 107阅读 0赞

\#include <iostream> using namespace std; int f(int m, int n) \{ if(m < 0) return 0; if(m == 0 || n == 1) return 1; return f(m, n-1) + f(m-n, n); \} int main() \{ int n; scanf("%d", &n); int M, N; while(n--) \{ scanf("%d%d", &M, &N); printf("%d/n", f(M,N)); \} return 0; \} //本题是很简单的递推: //①最少的盘子放了一个，这样每个盘子至少一个，n个盘子先放上n个，剩下的m-n个可以随便放 //②最少的盘子没有放，这样剩下的n-1个盘子还是随便放m个 /\* 引用大牛的话: 看到这道题立即想到了递归的经典案例：整数划分问题。 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。 将最大加数x不大于m的划分个数记作q(n,m) 有 1 n=1 || m=1 q(n,m) = \{ q(n,n) n<m 1+q(n,n-1) n=m q(n,m-1)+q(n-m,m) n>m>1 重点在n>m>1的情况。 呵呵，当时我还花了好些功夫才理解到哦，真是精妙。有了这一点经验，放苹果的问题就容易了，我们也有递归式 将在m个盘中放n个苹果记作fun(m,n)，且不能有空盘。（题目中的可以有空盘 不方便递归，我们循环累加） 对于fun(m,n) 1 n=1||m=n resulut = 0 n<m ∑ fun(n-m,i) n>=m , i=1..n 当n>=m时，是不是方法和整数划分问题的n>m>1时很像呢？呵呵 于是我们得到代码 1\#include "stdio.h" 2int fun(int m,int n) 3\{ 4int i,result; 5if(n==1||m==n) return 1; 6 else if(n<m) return 0; 7 else 8 \{ 9 result=0; 10 for(i=1;i<=n;i++) 11 result+=fun(n-m,i); 12 return result; 13 \} 14\} 15void main() 16\{ 17int T,m,n,k,i; 18int result=0; 19scanf("%d",&T); 20while(T--) 21\{ 22 scanf("%d %d",&m,&n); 23 for(i=1;i<=n;i++) 24 result=result+fun(m,i); 25 printf("%d/n",result); 26\} 27\} \*/