問題描述:
1000個蘋果放在10個箱子里, 10個箱子一模一樣且要
求每個箱子都放有蘋果, 問共有多少種放法?
參考:
呵呵,假設c(x,n)為x個apple放入n個箱子的所有放法(沒有至少一個的限制)
有這樣的遞推公式
c(x,
1
)
=
1
;
c(x,n)
=
c(x,n
-
1
)
+
c(x
-
n,n
-
1
)
+
c(x
-
2
*
n,n
-
1
)
+
...c(x
-
i
*
n,n
-
1
)
+
...
+
c(x
%
n,n
-
1
);
寫成程序就是
#include
<
iostream
>
using
namespace
std;
typedef
int
Type;
Typefun(
int
apple,
int
box)
{
Type
*
p,
*
q,
*
tmp;
int
i,j,k;
Typeresult;
//
本來我的fun(apple,box)是計算沒有"至少放1個apple"限制的所有方法的
apple
-=
box;
//
加上這句fun函數的功能就等價于每個box至少放一個apple了
p
=
new
Type[apple
+
1
];
q
=
new
Type[apple
+
1
];
for
(i
=
0
;i
<=
apple;i
++
)
p[i]
=
1
;
//
p[i]此時表示i個apple放1個box時的可能種類(沒限制)
for
(j
=
2
;j
<=
box;j
++
)
//
box數j從2遞增到box
{
for
(i
=
0
;i
<=
apple;i
++
)
//
計算i個apple放j個box時的可能種類,結果存放到q[i]
for
(q[i]
=
0
,k
=
i;k
>=
0
;k
-=
j)
q[i]
+=
p[k];
tmp
=
p;
//
交換數組p,q
p
=
q;
q
=
tmp;
}
result
=
p[apple];
delete[]p;
delete[]q;
return
result;
}
int
main()
{
int
sum,m;
cout
<<
"
請輸入蘋果數目:
"
;
cin
>>
sum;
cout
<<
"
請輸入箱子數:
"
;
cin
>>
m;
cout
<<
"
放法總數目為:
"
<<
fun(sum,m)
<<
endl;
system(
"
pause
"
);
return
0
;
}
上面的程序計算150個蘋果只有毫秒級,因為運算都是加法所以算1000或者更大也很簡單.
只要自己寫一個長整數的類并且重載+和=以及<<運算符,然后替換我的typedef就可以了.
1000個蘋果放在10個箱子里, 10個箱子一模一樣且要
求每個箱子都放有蘋果, 問共有多少種放法?
參考:




















































上面的程序計算150個蘋果只有毫秒級,因為運算都是加法所以算1000或者更大也很簡單.
只要自己寫一個長整數的類并且重載+和=以及<<運算符,然后替換我的typedef就可以了.
/////////////////////////////////////////////////////////////////////////////////////
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
