12004 - Bubble Sort

下列c語言程式為泡泡排序演算法(bubble sort)，注意程式碼count++;的地方，每次做資料交換，count的值即累加1。

int findSwaps( int n, int a[] )
{
    int count = 0, i, j, temp, b[100000];

    for( i = 0; i < n; i++ ) {
        b[i] = a[i];
    }
    for( i = 0; i < n; i++ ) {
        for( j = 0; j < n - 1; j++ ) {
            if( b[j] > b[j+1] ) {
                temp = b[j];
                b[j] = b[j+1];
                b[j+1] = temp;

                count++;
            }
        }
    }
    return count;
}

本題請你計算對於不同的陣列大小n，陣列元素交換次數的期望值為何(即count的期望值)？也就是說，當陣列大小為 n，且陣列元素a[]分別為1~n的值之隨機分佈時，若呼叫findSwaps()無限多次，則count的平均值應為多少？

Input 

輸入的第一個整數為T( <= 1000)表示測試資料的組數，接下來有T列，每列為一個整數 n (1 <= n <= 100000)。

Output 

請對每個 n 之值輸出count的期望值為何，若非整數請輸出最簡分數，輸出格式請參考範例資料。

Sample Input 

2
1
2

Sample Output 

Case 1: 0
Case 2: 1/2

---

原文出處