归并排序

/**
*  合并两个有序子数组
**/
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;

    //复制数组元素
    for (i = 0; i < leftLength; ++i){
        leftArray[i] = array[p + i];
    }

    for (j = 0; j < rightLength; ++j){
        rightArray[j] = array[q + j + 1];
    }
    
    //将两个有序子数组合并
    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 的元素已经包含在前一部分，这里要 q + 1
        mergeSort(array, q + 1, r); 
        merge(array, p, q, r); //合并两个有序的数组
    }
}

二分查找

int binarySearch(int array[], int p, int r, int find){
    int q = 0;
    /*
    这里之所以用 <= 而不是 < 是因为当来到数组第一个或者最后一个元素时要让这个元素进入到下面的比较环节。分步考虑在只有三个元素的数组里查找就清楚了。
    */
    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 数

朴素算法

/**
 * 由 Fibonacci 数的定义得到的算法
 */
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) 已经被计算过了，这样会有重复计算的情况，把已经计算过的值存起来，如果有已经计算过的就直接用，没有再计算。这样可以省下一些重复计算的开销。

/**
 * 计算 F(n)，如果数组中已经有值就直接返回，如果没有就递归的计算
 */
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) 的驱动函数
 */
int fibonacciMemory(int n){
    int i = 0;
    //申请一个 n 维数组，用来储存计算过的 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) 距离最近的那个整数，但是由于浮点数精度问题这个算法无法实现。

矩阵解法（分治法）

有公式(证明用数学归纳法)：

Fibonacci.png

根据这个公式，可以用平方递归解决计算 Fibonacci 问题。

/**
 * 一个并不优雅的 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];
}