1.1 题目描述

完成二项式公式计算，即C(n, k) = C(n-1, k-1)+ C(n-1, k)式解释:为了从n个不同元素中抓取k个元素(C(n, k)),可以这样考虑，如果第一个元素一定在结果中，那么就需要从剩下的n-1个元素中抓取k-1个元素(C(n-1, k-1))；如果第一个元素不在结果中，就需要从剩下的n-1个元素中抓取k个元素(C(n-1, k))。
要求分别采用以下方法计算，并进行三种方法所需时间的经验分析。
1. 直接采用递归算法
2. 采用备忘录方法
3. 采用迭代算法
要有性能数据。最好是T(n, k)的曲线或者曲面图。如果是曲线，t = T(n, k),可以固定不同的n值，分别考察t ~ t(k)的变化情况。迭代算法要和递归思路相关。另外，Excel其实可以帮你完成函数拟合（回归），就是帮你猜时间复杂度。

1.2 程序使用说明

1： 输入n值；
2： 等待k从1增加到n/2为止。

1.3 分析和设计

  1. 思路
    根据递推公式(C(n, k) = C(n-1, k-1)+ C(n-1, k))，在递归中，计算C(n, k)需要计算C(n-1, k-1)和C(n-1, k))的值，所以需要在递归调用函数来求解这两个的值。在备忘录方法中，需要将计算到的二项式的值记录到备忘录中，在需要时可以直接读取，读取失败，即未计算过此二项式，才需要计算，这大大减少了重复计算。在迭代算法中，计算下标n的二项式需要计算下标n-1的二项式，以此类推，需要最先计算下标为1的二项式，然后迭代到n。
    2. 伪代码
    A. 递归算法
    1. Recurrence(n, k)
    2. // 输入：二项式下标上标n、k
    3. // 输出：二项式的值
    4. if n = 1 or n = k
    5.  return 1
    6. else if k = 1
    7.  return n
    8. else
    9.  return Recurrence(n-1, k-1) + Recurrence(n-1, k)
    B. 备忘录
    1. Notebook(n, k, note)
    2. // 输入：二项式下标上标n、k，一个默认为-1的矩阵note[1...n, 1...k]
    3. // 输出：二项式的值
    4. if note[n, k] = -1
    5.  if n = 1 or n = k
    6.      note[n, k] <- 1
    7.  else if k = 1
    8.      note[n, k] <- n
    9.  else
    10.      note[n, k] <- Notebook(n-1, k-1, note) + Notebook(n-1, k, note)    
    11. return note[n, k]
    C. 迭代
    1. Iteration(n, k)
    2. // 输入：二项式下标上标n、k
    3. // 输出：二项式的值
    4. // 存储二项式下标为i的计算结果
    5. preRow[1...k]， curRow[1...k]
    6. preRow <- 1
    7. // 计算下标为i的二项式的值
    8. for i <- 2 to n do
    9.  curRow[1] <- i
    10.  // 计算上标为j的二项式的值
    11.  for j <- 2 to min(k, i-1) do
    12.      curRow[j] <- preRow[j] + preRow[j-1]
    13.  if i <= k
    14.      curRow[i] <- 1
    15.  temp <- curRow
    16.  curRow <- preRow
    17.  preRow <- temp 
    18. return preRow[k]

    3. 时间复杂度
    在递归算法中，计算一个二项式的值需要计算另外两个二项式的值，这会形成一个二叉树，二叉树的高度为n，所以时间复杂度为O(2n)；在备忘录算法中，二项式的值是从备忘录中查找的，需要计算的二项式的值计算一次即可，无需重复计算，所以时间复杂度为O(nk)，而迭代算法中，需要依次计算出下标从1到n，上标从1到k的所有值，它的时间复杂度也为O(nk)。

    1.4 测试用例

    | | | | | | | —- | —- | —- | —- | —- | | 1 | n = 10 k=1 | 10 10 10 | 10 10 10 | 通过 | | 2 | n = 10 k = 3 | 120 120 120 | 120 120 120 | 通过 | | 3 | n = 10 k = 4 | 210 210 210 | 210 210 210 | 通过 |

1.5 源代码（含注释）

import java.time.Instant;
import java.time.temporal.ChronoUnit;
import java.util.Scanner;
public class Binomial {
    public static long[][] note;
    public static void main(String[] args) {
        int n = 100;
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入n值：");
        n = scanner.nextInt();
        System.out.println("k\t递归\t备忘录\t迭代");
        for (int i = 1; i < n / 2; i += 1) {
            System.out.print(i + "\t");
            System.out.print(recurrence(n, i) + "\t");
            note = initNotebook(n, i);
            System.out.print(notebook(n, i) + "\t");
            System.out.print(iteration(n, i));
            System.out.println();
        }
        System.out.println("k\t递归\t备忘录\t迭代");
        for (int i = 1; i < n / 2; i += 1) {
            System.out.print(i + "\t");
            Instant start = Instant.now();
            recurrence(n, i);
            Instant end = Instant.now();
            System.out.print(ChronoUnit.MILLIS.between(start, end) + "\t");
            start = Instant.now();
            note = initNotebook(n, i);
            notebook(n, i);
            end = Instant.now();
            System.out.print(ChronoUnit.MILLIS.between(start, end) + "\t");
            start = Instant.now();
            iteration(n, i);
            end = Instant.now();
            System.out.print(ChronoUnit.MILLIS.between(start, end));
            System.out.println();
        }
    }
    /**
     * 递归方法
     *
     * @param n 元素个数
     * @param k 选择个数
     * @return 二项式的值
     */
    public static int recurrence(int n, int k) {
        if (n == 1 || n == k) {
            return 1;
        } else if (k == 1) {
            return n;
        } else {
            return recurrence(n - 1, k - 1) + recurrence(n - 1, k);
        }
    }
    /**
     * 初始化备忘录，即赋默认值-1
     *
     * @param n 元素个数
     * @param k 选择个数
     * @return 备忘录
     */
    public static long[][] initNotebook(int n, int k) {
        // 为了让数组下标与二项式下标一致，需要多加一圈
        long[][] note = new long[n + 1][k + 1];
        for (int i = 0; i < n + 1; i++) {
            for (int j = 0; j < k + 1; j++) {
                // 默认-1
                note[i][j] = -1;
                if (i == 1 || i == j) {
                    // 只有一个元素或者元素个数与需要选择的个数相同
                    note[i][j] = 1;
                } else if (j == 1) {
                    // 只选择一个元素
                    note[i][j] = i;
                }
            }
        }
        return note;
    }
    /**
     * 备忘录
     *
     * @param n 元素个数
     * @param k 选择个数
     * @return 二项式的值
     */
    public static long notebook(int n, int k) {
        if (note[n][k] == -1) {
            // 当前二项式未计算过时
            note[n][k] = notebook(n - 1, k - 1) + notebook(n - 1, k);
        }
        return note[n][k];
    }
    /**
     * 迭代
     *
     * @param n 元素个数
     * @param k 选择个数
     * @return 二项式的值
     */
    public static long iteration(int n, int k) {
        // 最多一行只有k个元素，preRow已经计算的结果，curRow表示当前正在计算的行
        long[] preRow = new long[k + 1];
        long[] curRow = new long[k + 1];
        for (int i = 1; i < k + 1; i++) {
            preRow[i] = 0;
            curRow[i] = 0;
        }
        // C(1, 1) = 1
        preRow[1] = 1;
        for (int i = 2; i <= n; i++) {
            // C(i, 1) = i;
            curRow[1] = i;
            for (int j = 2; j <= k && j < i; j++) {
                // C(i, j) = C(i-1, j) + C(i-1, j-1)
                curRow[j] = preRow[j] + preRow[j - 1];
            }
            // C(i, i) = 1
            if (i <= k) {
                // 避免数组下标越界
                curRow[i] = 1;
            }
            long[] temp = curRow;
            curRow = preRow;
            preRow = temp;
        }
        return preRow[k];
    }
}