當前位置:編程學習大全網 - 編程語言 - 數字200的全拆分問題(如有解法將追加最高200分)

數字200的全拆分問題(如有解法將追加最高200分)

(1)

事先為了把這個問題說明的清楚壹點,我打算用壹個比喻,而且另外壹個原因是我參考的資料裏面也是用的這個比喻來說明這個問題的。

那麽可以先看成是將200個蘋果要放在25個盤子裏。

我們用f(m,n)來表示要把m個蘋果放在n個盤子裏的種數(不同的是盤子可以為空,不可以為空的時候我們只需要將討論作壹個很小的改動,這個會在後面說到)。現在來看壹下壹個遞歸算法:

先對n作討論,如果n>m,必定有n-m個盤子永遠空著,去

掉它們對擺放蘋果方法數目不產生影響;即

if(n>m) f(m,n) = f(m,m)

當n<=m時,不同的放法可以分成兩類:即有至少壹個

盤子空著或者所有盤子都有蘋果,前壹種情況相當於

f(m,n) = f(m,n-1);

後壹種情況可以從每個盤子中拿掉壹個蘋果,不影響

不同放法的數目,即

f(m,n) = f(m-n,n). 而總的放蘋果的放法數目等於兩

者的和,即

f(m,n) =f(m,n-1)+f(m-n,n)

這個遞歸的出口就在於:

當n=1時,所有蘋果都必須放在

壹個盤子裏,所以返回1;當沒有蘋果可放時,

定義為1種放法;遞歸的兩條路,第壹條n會逐

漸減少,終會到達出口n==1; 第二條m會逐漸減

少,因為n>m時,我們會return f(m,m) 所以終

會到達出口m==0.

但是由於所要解決的問題中不能出現空盤子,就必須先在每個盤子上放壹個蘋果,於是最後的結論就是只需要計算f(175,25)的值。

遞歸的算法對於很大的數字的時候進行人工計算會有很大的計算量,如果用C語言寫成程序的話,源程序為:

/**********************************/

//(由於電腦上沒有裝編譯軟件,可能會有BUG)

#include<stdio.h>

int f(int m, int n){

if(n==1 || m==0) return 1;

if(n>m) return f(m,m);

return f(m,n-1)+f(m-n,n);

}

void main(){

int re;

re=f(175,25);

printf("%d\n",re);

}

//註:參考資料下載/cpp2007/lecture/7.pdf

/**********************************/

(2)

這個問題就是壹個簡單的組合問題,如壹樓所述,只要將200個蘋果中間的199個空隙中隨機插入24個分隔。最後就是要求C(199,24)

/**********************************/

//(由於電腦上沒有裝編譯軟件,可能會有BUG)

#include<stdio.h>

int c(int m, int n){//組合的算法,為從m中隨機選取n個

if(n==0 || n==m) return 1;

return c(m-1,n)+c(m-1,n-1);

}

void main(){

int re;

re=c(199,24);

printf("%d\n",re);

}

/**********************************/

(3)

先在每個盤子中放4個。現在就剩下100個蘋果和25個盤子,並且這裏的盤子裏都是可以隨便放蘋果,就形成了這樣壹種模型:100個蘋果和25個盤子形成了125個位置,盤子要在其中占據25個位置,便是要求C(125,25)

/**********************************/

//(由於電腦上沒有裝編譯軟件,可能會有BUG)

#include<stdio.h>

int c(int m, int n){//組合的算法,為從m中隨機選取n個

if(n==0 || n==m) return 1;

return c(m-1,n)+c(m-1,n-1);

}

void main(){

int re;

re=c(125,25);

printf("%d\n",re);

}

/**********************************/

  • 上一篇:c語言數據類型有高有低。
  • 下一篇:山東教育衛視學校疫情防控專家報告視頻會觀看方法
  • copyright 2024編程學習大全網