呵呵,假設(shè)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函數(shù)的功能就等價于每個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數(shù)j從2遞增到box
... {
for (i = 0 ;i <= apple;i ++ ) // 計算i個apple放j個box時的可能種類,結(jié)果存放到q[i]
for (q[i] = 0 ,k = i;k >= 0 ;k -= j)
q[i] += p[k];
tmp = p; // 交換數(shù)組p,q
p = q;
q = tmp;
}
result = p[apple];
delete[]p;
delete[]q;
return result;
}

int main()
... {
int sum,m;
cout << " 請輸入蘋果數(shù)目: " ;
cin >> sum;
cout << " 請輸入箱子數(shù): " ;
cin >> m;
cout << " 放法總數(shù)目為: " << fun(sum,m) << endl;
system( " pause " );
return 0 ;
}


上面的程序計算150個蘋果只有毫秒級,因為運算都是加法所以算1000或者更大也很簡單.
只要自己寫一個長整數(shù)的類并且重載+和=以及<<運算符,然后替換我的typedef就可以了.