【解題】序列長度問題 - Sequence

台北市96學年度高中資訊學科能力競賽 - 序列長度問題 (Sequence)


問題描述

　　傑倫與伊林非常喜歡上高中生物課，而生物老師孔智慧有一個「序列長度」問題，希望兩位同學幫忙計算。孔老師觀察出昆蟲體內存有許多過去從未被發現的奇特結構序列，這些結構序列是由一組元素組成，而且每一個元素在每一個結構序列中最多僅會出現一次。例如，當有{A, B} 2個不同組成元素時，則可以組成A、B、A-B、B-A等4 種結構序列，這4種結構序列的長度總和為6。而當有{A, B, C} 3個不同組成元素時，則可以組成A、B、C、A-B、B-A、A-C、C-A、B-C、C-B、A-B-C，A-C-B、B-A-C、B-C-A、C-A-B、C-B-A等15種結構序列，而這15種結構序列的長度總和為33。由於預期陸續會有含新組成元素的結構序列被發現，孔老師因此希望傑倫與伊林幫忙計算看看當不同組成元素有n個時，所有可能的不同結構序列長度總和為何？聰明的你(妳)請寫一個程式幫傑倫與伊林來回答這個問題。


輸入檔格式(C:\sequence\input.txt)

　　輸入一行只有一個正整數n(1≦n≦1000)，代表不同組成元素。


輸出檔格式 (C:\sequence\output.txt)

　　輸出一個整數，即所有可能結構序列的總長度。

註：第二組輸出範例為一個122位的正整數，在本範例中因列印問題已自動更改格式為四行輸出，但在您的輸出檔中，仍應輸出至同一行中。


輸入檔範例1

5


輸出檔範例1

1305


輸入檔範例2

80


輸出檔範例2

1536913041036158631879990235799326108728
2487463803004967244454894616548299221460
1682328139903912967663080782140497997968
80


解題思考

　　又是一篇落落長，看得霧煞煞？沒關係，讓我們先將題目做個分析，一步一步來。

　　首先，我們把結構序列依照長度做個區分。運用排列組合的知識，在有n種組成元素的情況下：長度為1的序列，有P n取1種可能，也就是C n取1 * n!；長度為2的序列，有P n取2種可能；長度為3的序列，有P n取3種可能......。

　　以此類推，我們可以得出，題目要求的序列總長度能夠以一條公式表示：



　　當然，只是這樣這題還不算解完。在題目輸出格式的附註中，有提到結果會出現一個122位的正整數。因此，我們還需要使用超長整數來做運算(這就是我之前提到的怨念)。

　　請恕我在參考解答中，直接引括之前曾貼出的作品 - 大數運算來使用。之後，我會特別獨立一篇，將大數運算的四則運算原理作個解釋。在這裡我們先略過不談。


參考解答(C++)

#include <iostream>
#include <fstream>

#include "large.h"

using namespace std;

int main(void)
{
    ifstream in("C:/sequence/input.txt");
    ofstream out("C:/sequence/output.txt", ios_base::trunc);

    int n;
    large sum = 0;

    cout << "讀入資料 . . ." << endl;
    in >> n;
    in.close();

    cout << n << endl;

    for (int i = 1; i <= n; i++)
    {
        large t = 1;
        for (int j = n; j > n - i; j--) { t *= j; }

        sum += t * i;
    }

    out << sum << endl;
    out.close();

    cout << "總長度為 " << sum << endl;
    cout << "輸出資料在 ouput.txt" << endl;

    system("pause");
}