歸并排序

/**
*  合并兩個有序子數(shù)組
**/
void merge(int array[], int p, int q, int r){
    int leftLength = q - p + 1;
    int rightLength = r - q;
    int leftArray[leftLength];
    int rightArray[rightLength];
    int i = 0, j = 0, k = 0;

    //復(fù)制數(shù)組元素
    for (i = 0; i < leftLength; ++i){
        leftArray[i] = array[p + i];
    }

    for (j = 0; j < rightLength; ++j){
        rightArray[j] = array[q + j + 1];
    }
    
    //將兩個有序子數(shù)組合并
    for (i = 0, j = 0, k = p; k <= r; ++k){

        if (i < leftLength && j < rightLength){
            if (leftArray[i] > rightArray[j]){
                array[k] = rightArray[j];
                ++j;
            }else {
                array[k] = leftArray[i];
                ++i;
            }
        }else if (i < leftLength){
            array[k] = leftArray[i];
            ++i;
        }else if (j < rightLength){
            array[k] = rightArray[j];
            ++j;
        }

    }
}

/**
*  歸并排序 array 中的元素，元素索引從 p 到 r
**/
void mergeSort(int array[], int p, int r){
    int q = 0;
    if (p < r){
        q = (p + r) / 2; 
        mergeSort(array, p, q);
        //索引為 q 的元素已經(jīng)包含在前一部分，這里要 q + 1
        mergeSort(array, q + 1, r); 
        merge(array, p, q, r); //合并兩個有序的數(shù)組
    }
}

二分查找

int binarySearch(int array[], int p, int r, int find){
    int q = 0;
    /*
    這里之所以用 <= 而不是 < 是因為當來到數(shù)組第一個或者最后一個元素時要讓這個元素進入到下面的比較環(huán)節(jié)。分步考慮在只有三個元素的數(shù)組里查找就清楚了。
    */
    if (p <= r){
        q = (p + r) / 2;
        if (array[q] == find){
            return q;
        }else if (array[q] > find){
            return binarySearch(array, 0, q - 1, find);
        }else {
            return binarySearch(array, q + 1, r, find);
        }
    }

    return -1;
}

乘方問題

/**
 * 計算 x 的 n 次方，遞歸的計算 x 的 n / 2 次方
 */
long long mathPowerQuestion(int x, int n){
    if (n == 0){
        return 1;
    }
    if (n == 1){
        return x;
    }
    if (n % 2 == 1){
        return mathPowerQuestion(x, n / 2) * mathPowerQuestion(x, n / 2) * x;
    }else {
        return mathPowerQuestion(x, n / 2) * mathPowerQuestion(x, n / 2);
    }
}

Fibonacci 數(shù)

樸素算法

/**
 * 由 Fibonacci 數(shù)的定義得到的算法
 */
int fibonacciBasic(int n){
    if (n > 1){
        return fibonacciBasic(n - 1) + fibonacciBasic(n - 2);
    }else if (n == 1){
        return 1;
    }else {
        return 0;
    }
}

其它解法（利用緩存）

在上面那個樸素算法中，當計算 F(n) 時，要計算 F(n - 1) 和 F(n - 2)，而計算 F(n - 1) 時 F(n - 2) 已經(jīng)被計算過了，這樣會有重復(fù)計算的情況，把已經(jīng)計算過的值存起來，如果有已經(jīng)計算過的就直接用，沒有再計算。這樣可以省下一些重復(fù)計算的開銷。

/**
 * 計算 F(n)，如果數(shù)組中已經(jīng)有值就直接返回，如果沒有就遞歸的計算
 */
int fibonacciMemoryCalculate(int *fibonacciNumberArray, int n){
    int result = -1;
    if (fibonacciNumberArray[n] == -1){
        result = fibonacciMemoryCalculate(fibonacciNumberArray, n - 1) + fibonacciMemoryCalculate(fibonacciNumberArray, n - 2);
        fibonacciNumberArray[n] = result;
        return result;
    }else {
        return fibonacciNumberArray[n];
    }
}

/**
 *計算 F(n) 的驅(qū)動函數(shù)
 */
int fibonacciMemory(int n){
    int i = 0;
    //申請一個 n 維數(shù)組，用來儲存計算過的 F(n) ，并初始化，將除前兩個元素之外的元素都置 -1
    int *fibonacciNumber = malloc(sizeof(int) * (n + 1));
    for (i = 0; i <= n; ++i){
        if (i == 0){
            fibonacciNumber[i] = 0;
        }else if (i == 1){
            fibonacciNumber[i] = 1;
        }else {
            fibonacciNumber[i] = -1;
        }
    }

    int result = fibonacciMemoryCalculate(fibonacciNumber, n);
    free(fibonacciNumber);
    return result;

}

一個理論解法

F(n) 是 4^n / sort(5) 距離最近的那個整數(shù)，但是由于浮點數(shù)精度問題這個算法無法實現(xiàn)。

矩陣解法（分治法）

有公式(證明用數(shù)學歸納法)：

Fibonacci.png

根據(jù)這個公式，可以用平方遞歸解決計算 Fibonacci 問題。

/**
 * 一個并不優(yōu)雅的 2 X 2 矩陣乘法
 */
void matrixTimes(int resultMatrix[][2], int leftMatrix[][2], int rightMatrix[][2]){
    resultMatrix[0][0] = leftMatrix[0][0] * rightMatrix[0][0] + leftMatrix[0][1] * rightMatrix[1][0];
    resultMatrix[0][1] = leftMatrix[0][0] * rightMatrix[0][1] + leftMatrix[0][1] * rightMatrix[1][1];
    resultMatrix[1][0] = leftMatrix[1][0] * rightMatrix[0][0] + leftMatrix[1][1] * rightMatrix[1][0];
    resultMatrix[1][1] = leftMatrix[1][0] * rightMatrix[0][1] + leftMatrix[1][1] * rightMatrix[1][1];
}

/**
 *遞歸的計算一個矩陣的 n 次方
 */
void matrixPower(int resultMatrix[][2], int matrix[][2], int n){
    if (n == 0){
        resultMatrix[0][0] = 1;
        resultMatrix[0][1] = 0;
        resultMatrix[1][0] = 0;
        resultMatrix[1][1] = 1;
        return;
    }else if (n == 1){
        resultMatrix[0][0] = matrix[0][0];
        resultMatrix[0][1] = matrix[0][1];
        resultMatrix[1][0] = matrix[1][0];
        resultMatrix[1][1] = matrix[1][1];
        return;
    }else if (n % 2 == 1){
        int leftMatrix[2][2];
        int rightMatrix[2][2];
        int resultTemp[2][2];
        matrixPower(leftMatrix, matrix, n / 2);
        matrixPower(rightMatrix, matrix, n / 2);
        matrixTimes(resultTemp, leftMatrix, rightMatrix);
        matrixTimes(resultMatrix, resultTemp, matrix);
        return;
    }else {
        int leftMatrix[2][2];
        int rightMatrix[2][2];
        matrixPower(leftMatrix, matrix, n / 2);
        matrixPower(rightMatrix, matrix, n / 2);
        matrixTimes(resultMatrix, leftMatrix, rightMatrix);
        return;
    }
}

/**
 * 求F(n) （只需要計算那個矩陣的 n - 1 次方）
 */
int fibonacciMatrix(int n){
    if (n == 0){
        return 0;
    }

    int resultMatrix[2][2];
    int matrix[2][2] = {{1, 1}, {1, 0}};
    matrixPower(resultMatrix, matrix, n - 1);

    return resultMatrix[0][0];
}