N個小球放入M個盒子共有多少種方法，并輸出的算法設(shè)計：

算法思路1 ：暴力填充盒子

每個小球都可能放入M個盒子的任意一個，所以直接根據(jù)小球個數(shù)做遞歸即可,然后將存儲放入hash中排重

//TODO

算法思路2 ：遞歸填充盒子

即，每層遞歸僅考慮一個盒子放幾個球，剩下的球交給下一個遞歸。

比如第一個盒子里放N個球，則剩下的都是0個；第一個盒子放n-1個球，問題就變成了1個球與M-1個盒子的問題...直到第一個盒子放0個球，問題變成了N個球與M個盒子的問題。

遞歸的入口是第1個盒子，那么遞歸的出口在哪？自然是最后一個盒子。當(dāng)盒子只剩一個時候便不向下遞歸，還剩多少小球就全放進盒子里。

遞歸偽代碼如下：

public void everyBox(int boxes , int balls ,String oneResult?){

if (boxes ==1){? ? ? ? ? ? ? ? ? ? ? ?//遞歸出口

thisResult = oneResult+balls

return

}

for( i=balls ; i >=0 ; i --?){

thisResult ?= oneResult + (String) i

everyBox(boxes-1 , balls-i , thisResult) ?//遞歸

}

}

算法2優(yōu)化：

上述遞歸只有一個出口，就是只剩一個box時候。不過這個程序還有一個可以優(yōu)化的出口：在balls等于0的時候。假設(shè)還剩余X個盒子沒有進行遞歸，而這時候剩余ball是0，便不用遞歸了，直接輸出X個0即可。當(dāng)盒子數(shù)>>小球數(shù)時候，可以極大減少遞歸的層次，提高代碼效率。

優(yōu)化后的java示例代碼如下，由于要輸出就直接systemout了：

public class NballMbox {

public static void main(String[] args) {

NballMbox nm = new NballMbox();

nm.iterator(4, 2, "");

}

public void iterator(int balls , int boxes , String s){

//ball =0 直接結(jié)算

if(balls == 0){

for(int i = 0 ;i< boxes ;i++)

s = s+ 0;

System.out.println(s.toString());

return;

}

for(int i =balls;i >=0;i--){

String s1 = s+i;

if(boxes == 1){

System.out.println(s1.toString());

return;

}

else

this.iterator(balls-i, boxes-1, s1);

}

}

}

總結(jié)

以上是生活随笔為你收集整理的小球进盒子C语言,N个小球放进M个盒子算法-Go语言中文社区的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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