Problem 2.1 3n/2次比较寻找两最值

Write an algorithm that, given a list of n numbers, returns the largest and smallest numbers in the list. Estimate the running time of the algorithm. Can you design an algorithm that performs only 3n/2 comparisons to find the smallest and largest numbers in the list?

#include <stdio.h>
int min(int *nums, int numsSize) {
    int minx = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] < minx) minx = nums[i];
    }
    return minx;
}
int max(int *nums, int numsSize) {
    int maxx = nums[0];
    for (int i = 1; i < numsSize; ++i) {
        if (nums[i] > maxx) maxx = nums[i];
    }
    return maxx;
}
int main() {
    int nums[] = {3, 2, 0, -1, 2, 9};
    printf("largest numbers: %d\n", max(nums, sizeof(nums) / sizeof(int)));
    printf("smallest numbers: %d\n", min(nums, sizeof(nums) / sizeof(int)));
    return 0;
}

从严格意义上讲，max, min函数总的比较次数为2N - 1次，外层循环比较i < numSize共N次（最后一次是相等停止），然后前N - 1次循环内进行一次比较。即使我们将两个函数合并为一个，其总的比较次数为3N - 2
在 programming pearls 论文里面提到一种能够减少max, min函数比较次数为 次。

但是即使如此，我们也只能分别编码实现max, min函数，总的比较次数也是 远远达不到题目要求 的比较次数！

#include <stdio.h>
int min(int *nums, int numsSize) {
    // 假设数组后面预留一个空间
    nums[numsSize] = nums[0];
    for (int i = 1; i <= numsSize; ) {
        while (nums[i] > nums[numsSize]) ++i;  // 不会越界！
        // nums[i] <= nums[numsSize]，其中上面条件一定不能 =，会超界
        // 那么 i <= numsSize
        nums[numsSize] = nums[i];
        ++i;
    }
    return nums[numsSize];
}
int max(int *nums, int numsSize) {
    // 假设数组后面预留一个空间
    nums[numsSize] = nums[0];
    for (int i = 1; i <= numsSize; ) {
        while (nums[i] < nums[numsSize]) ++i;  // 不会越界！
        // nums[i] >= nums[numsSize]，其中上面条件一定不能 =，会超界
        // 那么 i <= numsSize
        nums[numsSize] = nums[i];
        ++i;
    }
    return nums[numsSize];
}
int main() {
    int nums[7] = {3, 2, 0, -1, 2, 9};
    printf("largest numbers: %d\n", max(nums, 6));
    printf("smallest numbers: %d\n", min(nums, 6));
    return 0;
}

我们简要分析下为什么比较次数变少了。

1. 使用哨兵原因：内层循环防止数组越界！
2. 内层循环判断较小值将减少外层循环次数（即比较次数），所以为防止判断数组越界i < numsSize && nums[i] < nums[numsSize]每次需要i < numsSize判断很麻烦。

因此该算法就是使用最值的判断同时减少外层循环次数，也就是利用元素之间的关系进行加速。

:::info 一篇来自搜索引擎给出的答案，但此答案未包含 for 循环的比较。
Let be the list to sort. Assume for simplicity that n is even. Create two initially empty lists and . For i = 0 up to n/2, compare to and put the smaller into and the larger into . Finally, do a linear search through to find the smallest element, and through to find the largest element. This algorithm requires n/2 comparisons to split the pairs of L into and , n/2 − 1 comparisons to find the smallest element in , and n/2 − 1 comparisons to find the largest element in . Therefore the total number of steps is 3n/2 − 2 ::: 基于上面内层循环判断可以直接减少索引比较，我们有如下启示：
Hint #1: if you organize the numbers into pairs, sorting each pair costs n/2 comparisons.
Hint #2: if you’re given a pair of numbers (x, y) such that x <= y, you only need to check x for the min and y for the max.
Hint #3: 如果有奇数个，那么多余那个值就算第一组内（假设两人）的比较结果，也就是用于初始化maxv, minv。

#include <stdio.h>
void maxAndMin(int *nums, int numsSize, int *maxv, int *minv) {
    *maxv = *minv = nums[0];
    // 判断是否为奇数长度，是则第一组已经决出胜负
    // 使用位运算可以减少一次判断
    for (int i = numsSize & 1; i + 1 < numsSize; i += 2) {
        if (nums[i] < nums[i+1]) {
            if (*minv > nums[i]) *minv = nums[i];
            if (*maxv < nums[i+1]) *maxv = nums[i+1];
        } else {
            if (*minv > nums[i+1]) *minv = nums[i+1];
            if (*maxv < nums[i]) *maxv = nums[i];
        }
    }
}
int main() {
    int maxv, minv;
    int nums1[] = {3, 2, 0, -1, 2, 9}, nums2[] = {2, 98, -1, 5, 23, -8, 55};
    maxAndMin(nums1, sizeof(nums1) / sizeof(int), &maxv, &minv);
    printf("largest numbers: %d smallest numbers: %d\n", maxv, minv);
    maxAndMin(nums2, sizeof(nums2) / sizeof(int), &maxv, &minv);
    printf("largest numbers: %d smallest numbers: %d\n", maxv, minv);
    return 0;
}

外层循环共进行 次比较，一次进行三次比较操作，因此总的比较次数为 ，比上面两轮遍历 和优化哨兵法 强太多。
原因：两数比较之后结果可以直接区分较大值和较小值，因此与之前两轮最值判断快在部分信息的复用，即较大/小者不可能为最终较小/大者。

Problem 2.2 穷举算法

Write two algorithms that iterate over every index from(0,0, . . . ,0)to(n1, n2, . . . , nd). Make one algorithm recursive, and the other iterative.
递归方式：以a = [0, 0, 0], b = [1, 2, 3]为例，从根到叶子的路径就是组合。

b = [1, 2, 3]
a = [0] * len(b)
def fn(idx: int) -> None:
    if idx == len(b):
        print(a)
        return
    for j in range(b[idx]+1):
        a[idx] = j
        fn(idx + 1)
fn(0)

迭代其实非常难写，因为要n重循环，但是这里n又是不确定的，所以将递归用栈实现将会非常麻烦。我们需要记录fn(idx + 1)执行的时刻并修改a[idx] = j，然后就到该层另一个递归函数执行。因此我们将每次call fn的参数都记录下，等到其执行的时候再对数组a进行赋值。

def iterate() -> None:
    stk = [(0, 0)]  # （idx, k) 元组
    while stk:
        # 出栈就修改原值
        idx, k = stk.pop()  # idx - 1 是上一次 call
        a[idx-1] = k  # 上一次 a[idx-1] = k 赋值
        if idx == len(b):  # 到头了
            print(a)
            continue
        for k in range(b[idx] + 1):  # 新一层递归（即第 idx 层递归子函数）
            stk.append((idx + 1, k))
iterate()

这里for k in range(b[idx] + 1)为虽然顺序遍历但是最终结果是上面从右往左的路径值，也就是栈后进先出的特性，逆序压入栈就得到上面递归结果。

Problem 2.3 时间复杂度概念

Is logn = O(n)? Is logn = Ω(n)? Is logn = Θ(n)?
：对数函数的上限是线性函数，：对数函数的下限不是线性函数，应该大于 ，但 。

Problem 2.4 原地哈希

You are given an unsorted list of n−1 distinct integers from the range 1 to n. Write a linear-time algorithm to find the missing integer.
原地哈希

Problem 2.5 斐波那契状态压缩

Though FIBONACCI(n) is fast, it uses a fair amount of space to store the array F. How much storage will it require to calculate the nth Fibonacci number? Modify the algorithm to require a constant amount of storage, regardless of the value of n.
依据状态转移方程进行空间压缩：
斐波那契数列问题

Problem 2.6 斐波那契数列黄金比例证明

Prove that . where Fn is the nth Fibonacci number, and 。
Hint1：是黄金分割率，而 是它的“共轭”，也就是 。
Hin2：虽然让直接证明这个等式，但是斐波那契数列递推式我们还是知道的
Hint3：

Problem 2.7 快速幂

Design an algorithm for computing the n-th Fibonacci number that requires less than O(n) time. Hint: You probably want to use the result from problem 2.6. However, computing naively still requiresO(n) time because each multiplication is a single operation.
Pow(x, n)

Problem 2.8 Fibonacci K生存时间

Propose a more realistic model of rabbit life (and death) that limits the life span of rab-bits by k years. For example, if k = 2.5, then the corresponding sequence 1,1,2,3,4 grows more slowly than the Fibonacci seqence. Write a recurrence relation and pseudocode to compute the number of rabbits under this model. Will the number of rabbits ever exceed the number of atoms in the universe (under these assumptions)?
Mortal Fibonacci Rabbits

Problem 2.9 汉诺塔迭代形式

Write an iterative (i.e., nonrecursive) algorithm to solve the Hanoi Tower problem.
汉诺塔

Problem 2.10 等差数列前N项和/高斯公式

Prove that
等差数列通项公式 ，定义等差数列前N项和为

Problem 2.11 等比数列前N项和

Prove that 和
等比数列通项公式 ，定义等比数列前N项和为

综上所述

• 将 带入公式得
• 将 带入公式得

  Problem 2.12

  We saw that BETTERCHANGE is an incorrect algorithm for the set of denominations (25,20,10,5,1). Add a new denomination to this set such that BETTERCHANGE will return the correct change combination for any value of M.

根据出现问题的测试用例，那么加面值为15的硬币可以解决任意M兑换，贪心算法都能够在此输入下给出正确解。
但是如何证明？

Problem 2.13 计算概率

Design an algorithm that computes the average number of coins returned by the program USCHANGE(M) as M varies from 1 to 100.

Problem 2.14 零钱兑换什么时候贪心可行？

Given a set of arbitrary denominations c = (c1, c2, . . . , cd), write an algorithm that can decide whether BETTERCHANGEis a correct algorithm when run on c.

我在一篇笔记中看到要求 ，其中 表示恰好整除。

Problem 2.15 博弈DP

A king stands on the upper left square of the chessboard. Two players make turns moving the king either one square to the right or one square downward or one square along a diagonal in the southeast direction. The player who can place the king on the lower right square of the chessboard wins. Who will win? Describe the winning strategy.

同石子问题一样，我们从最简单的状态开始推导。假设方阵大小为n * n，谁能在最后一步到达(n, n)，那么它将获得胜利。题意说明每次可以向右，下，右下方向移动一个单位，因此最后一步就能获胜的点为(n-1, n-1), (n, n-1), (n-1, n)，同理倒数第二步谁能到达这三个方向之一就能获胜，以此类推直到第一步走何处能获胜。
状态定义： 表示当前玩家在点时进行最佳选择的输赢情况。（注意此处状态定义不关心具体谁先手，而是关注两者都是最佳策略下的输赢情况。）
状态转移方程：，即只要右，下，右下方向中任意一个为False，那么该玩家有可能赢。
状态初始化：根据状态转移法可知需要预处理第n列和第n行，并且有 ，因此初始化为

def solve(m: int, n: int) -> bool:
    dp = [[False] * n for _ in range(m)]
    # 状态初始化
    dp[m-1][n-1] = False
    for i in range(m - 2, -1, -1):
        dp[i][n-1] = not dp[i+1][n-1]
    for j in range(n - 2, -1, -1):
        dp[m-1][j] = not dp[m-1][j+1]
    # 状态转移
    for i in range(m - 2, -1, -1):
        for j in range(n - 2, -1, -1):
            dp[i][j] = not (dp[i+1][j] and dp[i][j+1] and dp[i+1][j+1])  # 任一为False就行
    print(dp)
    return dp[0][0]
print(solve(8, 8))

我们将整个 dp 表格打印出来，我们发现结果是对称的，也就是说先手玩家在奇数行的情况下一定会赢！

Problem 2.16 石子分堆

Bob and Alice are bored one Saturday afternoon so they invent the following game. Initially, there are n rocks in a single pile. At each turn, one of the two players can split any pile of rocks that has more than 1 rock into two piles of arbitrary size such that the size of each of the two new piles must add up to the size of the original big pile. No player can split a pile that has only a single rock, and the last person to move wins. Does one of the two players, first or second, have an advantage? Explain which player will win for each value of n.
找规律：

• 当n = 1时，Alice无法分堆，因此输了比赛。
• 当n = 2时，Alice直接分为两堆，每堆各一个石头，因此赢得比赛。
• 当n = 3时，Alice只能分为(1, 2)（不必考虑顺序，结果都是一样的），即一堆一个石头，一堆两个石头，那么Bob回到n = 2状态，因此Alice输了比赛。
• 当n = 4时，Alice有分为(1, 3)或(2, 2)两种策略。
  • Alice选择(1, 3)，Bob面临n = 3必定失败，因此Alice赢得比赛。
  • Alice选择(2, 2)，Bob只能将其中一堆n = 2分为两堆(1, 1)，然后剩下一堆n=2，因此Alice赢得比赛。
• 当n = 5时，Alice有分为(1, 4)或(2, 3)两种策略。
  • Alice选择(1, 4)，Bob面临n = 4必定胜利，因此先手玩家输了比赛。
  • Alice选择(2, 3)，Bob有对n = 2的堆和对n = 3的堆进行划分共两种选择。（#1，应该是最佳）
    • Bob选择对n = 2堆划分，那么Alice 回到n = 3 状态输了比赛。（#2）
    • Bob选择对n = 3堆划分为(1, 2)，那么Alice 面临(2, 2) 状态一定会输了比赛。

从结果逆推：游戏最终将会得到形如(1,1,1,1,1,...,1)的石子序列，总共有 N 堆石子。玩家的每次操作，都会使得当前的石子堆数 +1，所以 n 颗石子时，总共经过 n-1 轮游戏结束。因此当石子个数为偶数时，Alice必胜，否则Bob获胜

作者：zaozhe 链接：https://leetcode-cn.com/circle/discuss/581jTG/view/iBUnFI/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

某一局面具体分析：最终局面是每堆石子均为1(0个偶数堆), 此时先手必败。

• 必败态: 偶数个偶数堆的局面
  • 当局面是偶数个偶数堆的时候:
    • 如果选择操作偶数堆，无论将该堆分成两个奇数堆还是两个偶数堆，对手的局面均是奇数个偶数堆
    • 如果选择操作奇数堆，必然增加一个偶数堆，对手的局面依然是奇数个偶数堆
• 必胜态: 奇数个偶数堆的局面
  • 当先手遇到奇数个偶数堆的局面的情况下：
    • 选择任一偶数堆，将其分成两个偶数堆，则对手的局面是偶数个偶数堆，即后手必败。

结论:

• 当初始n为偶数时，有奇数个偶数堆，则先手必胜。
• 当初始n为奇数时，有偶数个偶数堆，则先手必败。

  作者：Acvving_Js` 链接：https://leetcode-cn.com/circle/discuss/581jTG/view/SHt2vK/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Problem 2.17 病毒2^n增长，时间复杂度比较

There arenbacteria and 1 virus in a Petri dish. Within the first minute, the virus kills one bacterium and produces another copy of itself, and all of the remaining bacteria reproduce, making 2 viruses and 2 · (n − 1) bacteria. In the second minute, each of the viruses kills a bacterium and produces a new copy of itself (resulting in 4 viruses and 2(2(n−1) −2) = 4n−8 bacteria; again, the remaining bacteria reproduce. This process continues every minute. Will the viruses eventually kill all the bacteria? If so, design an algorithm that computes how many steps it will take. How does the running time of your algorithm depend on n?

• 细菌每代（按照时间t >= 0计算）的公式
• 病毒每代（按照时间t >= 0计算）的公式

实际上细菌每代个数公式为 ，推导过程如下

• 当 时两边同除 得 ，现令则有等差数列，那么
• 当 时代入 得 成立。

病毒个数大于或等于细菌个数时，病毒全部杀死细菌则有 ，解得 。

Problem 2.18 骑士和间谍：找出不诚实的人

A very large bioinformatics department at a prominent university has a mix of 100 professors: some are honest and hard-working, while others are deceitful([dɪ’sitfəl], 欺诈的) and do not like students. The honest professors always tell the truth, but the deceitful ones sometimes tell the truth and sometimes lie. You can ask any professors the following question about any other professor: “Professor Y, is Professor X honest?” Professor Y will answer with either “yes” or “no.” Design an algorithm that, with no more than 198 questions, would allow you to figure out which of the 100 professors are honest (thus identifying possible research advisors). It is known that there are more honest than dishonest professors.
KNIGHTS, SPIES, GAMES AND BALLOT SEQUENCES.pdf

Problem 2.19 矩阵置零（暴力）

You are given an 8 × 8 table of natural numbers（非负整数）. In any one step, you can either double each of the numbers in any one row, or subtract 1 from each of the numbers in any one column. Devise an algorithm that transforms the original table into a table of all zeros. What is the running time of your algorithm?
最暴力的方式是从右往左（从左往右）寻找一列的最小公倍数lcd，将该列上所有数值变为lcd后，统一进行lcd次减操作变为0。
复杂度分析：假设求解每列最小公倍数平均时间为 ，总的时间复杂度为

We reduce the columns to zero one at a time, by iteratively applying the following process:

• If there are any entries equal to 1, double their rows.
• Subtract 1 from each number in the column until there are entries equal to 1 again.

Until all the entries in the column are equal to 1, this process decreases the total, so eventually we will reduce to the all-ones case. At that point, subtracting one from each entry reduces each element of the column to 0.

Problem 2.20

There are n black, m green, and k brown chameleons（变色龙） on a deserted island. When two chameleons of different colors meet they both change their color to the third one (e.g., black and green chameleons become brown). For each choice of n, m, and k decide whether it is possible that after some time all the chameleons on the island are the same color (if you think that it is always possible, check the case n = 1, m = 3, and k = 5).

Problem2.9
Writeaniterative(i.e.,nonrecursive)algorithmtosolvetheHanoiTowerproblem.