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

與上一篇整數(shù)劃分相似

只不過規(guī)定了盤子的數(shù)量 即可以劃分?jǐn)?shù)字的個數(shù)

法1：回溯

回溯的關(guān)鍵是后面每一個盤子蘋果的數(shù)量要大于前面一個盤子蘋果的數(shù)量? 這樣才不會重復(fù)

#include<iostream> using namespace std; int num[20]; int M,N,count; void dfs(int n,int step) //n表示剩余蘋果數(shù)量 {if(step>N||n<0)return ;if(n==0&&step==N) //step==N表示前面 N個盤子都已經(jīng)放好了蘋果 {count++;return ; } for(int i=0;i<=M;i++){if(i>=num[step-1]){num[step]=i;dfs(n-i,step+1);num[step]=0;}} } int main(void) {cin>>M>>N;for(int i=0;i<=M;i++){num[0]=i; //第一個盤子數(shù)量的情況依次枚舉dfs(M-i,1); }cout<<count<<endl;return 0; }

2.遞歸遞推求解

#include<iostream> using namespace std;// 解題分析： // 設(shè)f(m,n) 為m個蘋果，n個盤子的放法數(shù)目，則先對n作討論， // 當(dāng)n>m：必定有n-m個盤子永遠(yuǎn)空著，去掉它們對擺放蘋果方法數(shù)目不產(chǎn)生影響。即if(n>m) f(m,n) = f(m,m)　　 // 當(dāng)n<=m：不同的放法可以分成兩類： // 1、有至少一個盤子空著，即相當(dāng)于f(m,n) = f(m,n-1); // 2、所有盤子都有蘋果，相當(dāng)于可以從每個盤子中拿掉一個蘋果，不影響不同放法的數(shù)目，即f(m,n) = f(m-n,n). // 而總的放蘋果的放法數(shù)目等于兩者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) // 遞歸出口條件說明： // 當(dāng)n=1時，所有蘋果都必須放在一個盤子里，所以返回１； // 當(dāng)沒有蘋果可放時，定義為１種放法。因為： 遞歸的兩條路，第一條n會逐漸減少，終會到達(dá)出口n==1; 第二條m會逐漸減少，因為n>m時，我們會return f(m,m)　所以終會到達(dá)出口m==0．int count(int m,int n) {if(m==0||n==1) //因為我們總是讓m>=n來求解的，所以m-n>=0,所以讓m=0時候結(jié)束，如果改為m=1，return 1; //則可能出現(xiàn)m-n=0的情況從而不能得到正確解 if(n>m) return count(m,m); //蘋果的數(shù)量小于盤子的數(shù)量 這時候那么該問題就和m個蘋果m個盤子的問題一樣return count(m-n,n)+count(m,n-1);//蘋果的數(shù)量大于盤子的數(shù)量 }int main(void) {int m,n;cin>>m>>n;cout<<count(m,n);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的放苹果(回溯解法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。