欧美性一二三区,在线免费观看日韩欧美,欧美午夜国产

ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸

http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=1664

放蘋果
Time Limit:1000MS  Memory Limit:10000K
Total Submit:6074 Accepted:3764 Description
把M個(gè)同樣的蘋果放在N個(gè)同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。
Input
第一行是測(cè)試數(shù)據(jù)的數(shù)目t（0 <= t <= 20）。以下每行均包含二個(gè)整數(shù)M和N，以空格分開。1<=M，N<=10。
Output
對(duì)輸入的每組數(shù)據(jù)M和N，用一行輸出相應(yīng)的K。
Sample Input
17 3

Sample Output
8

Source
lwx@POJ

看到這道題立即想到了遞歸的經(jīng)典案例：整數(shù)劃分問題。

將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk，
其中n1≥n2≥…≥nk≥1，k≥1。
正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不
同劃分個(gè)數(shù)。
例如正整數(shù)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。

  將最大加數(shù)x不大于m的劃分個(gè)數(shù)記作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

重點(diǎn)在n>m>1的情況。
呵呵，當(dāng)時(shí)我還花了好些功夫才理解到哦，真是精妙。有了這一點(diǎn)經(jīng)驗(yàn)，放蘋果的問題就容易了，我們也有遞歸式
將在m個(gè)盤中放n個(gè)蘋果記作fun(m,n)，且不能有空盤。（題目中的可以有空盤不方便遞歸，我們循環(huán)累加）
對(duì)于fun(m,n)
                      1                                 n=1||m=n
resulut   =       0                                 n<m
                     ∑ fun(n-m,i)                   n>=m   , i=1..n

當(dāng)n>=m時(shí)，是不是方法和整數(shù)劃分問題的n>m>1時(shí)很像呢？呵呵

于是我們得到代碼

#include "stdio.h"
2

int fun(int m,int n)
3

{
4

int i,result;
5

if(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

}
15

void main()
16

{
17

int T,m,n,k,i;
18

int result=0;
19

scanf("%d",&T);
20

while(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

}
28

posted on 2007-09-14 02:05 流牛ζ木馬閱讀(2760) 評(píng)論(9) 編輯收藏引用

評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2007-11-20 20:57 ban

e....你把m和n的含義都交換了。。。害我想了半天回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2007-11-27 11:40 maliang

盤子可以為空，那m==n的時(shí)候可以return 1 嗎？
maleungxp@gmail.com 回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2008-05-04 03:12 haha

#include <stdio.h>
int main ()
{
int i,j,k,n,ii,t,kk,z;
int a[100][100];
scanf("%d",&t);

for (ii=1; ii <=t; ii++)
{
scanf("%d%d", &n,&kk);
z=0;
for (k=1; k<kk+1; k++)
{
for (i=0 ; i <n-k+1; i++)
for (j=0; j <k+1; j++)
a[i][j]=0;

for (i=0; i <=n-k; i++)
a[i][1]=1;

for (i=0; i <=n-k;i++)
for (j=2; j<=k; j++)
if (i>=j) a[i][j]=a[i-j][j]+a[i][j-1] ;
else a[i][j]=a[i][j-1];

z=z+a[n-k][k];
}
printf("%d\n",z);
}
return 0;
}
回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2008-05-06 11:24 traveler

謝謝啦，我終于也明白了。。。回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2008-06-18 20:37 Gill

非遞歸算法
n<kk時(shí)出錯(cuò)

@haha
回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸[未登錄] 2008-08-23 21:46 李

厲害呀，這都能聯(lián)想到整數(shù)劃分回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2009-04-17 09:54 dream

錯(cuò)的回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2011-02-28 19:33 stufever

到底是m=1還是m=0遞歸結(jié)束都有道理，看你怎么理解了，我這里有解題報(bào)告http://stufever.com/?p=80 回復(fù) 更多評(píng)論

# re: ACM PKU 1664 放蘋果類似整數(shù)劃分問題的遞歸 2013-10-27 16:23 unkown

"呵呵，當(dāng)時(shí)我還花了好些功夫才理解到哦，真是精妙" 精妙在哪里? 最關(guān)鍵的地方樓主一筆帶過啦~~ 回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2007年11月

日

一

二

三

四

五

六

導(dǎo)航

統(tǒng)計(jì)

隨筆 - 63
文章 - 0
評(píng)論 - 154
引用 - 0

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木馬

常用鏈接

留言簿(6)

隨筆檔案

相冊(cè)

撒旦

搜索

閱讀排行榜

評(píng)論排行榜