1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
#include <iostream> using namespace std; // Author: Tanky Woo // www.wutianqi.com const int _max = 10001; // c1是保存各項質量砝碼可以組合的數目 // c2是中間量，保存沒一次的情況 int c1[_max], c2[_max]; int main() { //int n,i,j,k; int nNum; // int i, j, k; while(cin >> nNum) { for(i=0; i<=nNum; ++i) // ---- ① { c1[i] = 1; c2[i] = 0; } for(i=2; i<=nNum; ++i) // ----- ② { for(j=0; j<=nNum; ++j) // ----- ③ for(k=0; k+j<=nNum; k+=i) // ---- ④ { c2[j+k] += c1[j]; } for(j=0; j<=nNum; ++j) // ---- ⑤ { c1[j] = c2[j]; c2[j] = 0; } } cout << c1[n] << endl; } return 0; }
我們來解釋下上面標志的各個地方：
① 、首先對c1初始化，由第一個表達式(1+x+x2+..xn)初始化，把質量從0到n的所有砝碼都初始化為1.
② 、 i從2到n遍歷，這里i就是指第i個表達式，上面給出的第二種母函數關系式里，每一個括號括起來的就是一個表達式。
③、j 從0到n遍歷，這里j就是只一個表達式里第j個變量，比如在第二個表達式里：(1+x2+x4….)里，第j個就是x2*j.
③ k表示的是第j個指數，所以k每次增i（因為第i個表達式的增量是i）。
④ 、把c2的值賦給c1,而把c2初始化為0，因為c2每次是從一個表達式中開始的