面试题之苹果问题

呵呵,假设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就可以了.