欧美在线一二三四区,99热在线精品观看,中文在线一区

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個同樣的蘋果放在N個同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。
Input
第一行是測試數(shù)據(jù)的數(shù)目t（0 <= t <= 20）。以下每行均包含二個整數(shù)M和N，以空格分開。1<=M，N<=10。
Output
對輸入的每組數(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的不
同劃分個數(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的劃分個數(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

重點在n>m>1的情況。
呵呵，當(dāng)時我還花了好些功夫才理解到哦，真是精妙。有了這一點經(jīng)驗，放蘋果的問題就容易了，我們也有遞歸式
將在m個盤中放n個蘋果記作fun(m,n)，且不能有空盤。（題目中的可以有空盤不方便遞歸，我們循環(huán)累加）
對于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ù)劃分問題的n>m>1時很像呢？呵呵

于是我們得到代碼

#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 流牛ζ木馬閱讀(2753) 評論(9) 編輯收藏引用

#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ù) 更多評論

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

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

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

非遞歸算法
n<kk時出錯

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

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

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

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

錯的回復(fù) 更多評論

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

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

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

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

刷新評論列表

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



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

2007年11月

日

一

二

三

四

五

六

導(dǎo)航

統(tǒng)計

隨筆 - 63
文章 - 0
評論 - 154
引用 - 0

公告

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

常用鏈接

留言簿(6)

隨筆檔案

相冊

撒旦

搜索

閱讀排行榜

評論排行榜

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

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

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

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

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

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

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

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

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

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

評論

導(dǎo)航

統(tǒng)計

公告

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

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

評論

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

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

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

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

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

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

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

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

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

導(dǎo)航

統(tǒng)計

公告

常用鏈接

留言簿(6)

隨筆檔案

相冊

搜索

最新隨筆

最新評論

閱讀排行榜

評論排行榜

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

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

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

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

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

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

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

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

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

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