目录

第一章

算法的定义

算法的三要素

算法的基本性质

算法的时间复杂度数量级：

第二章

兔子繁殖问题（递推法）

猴子吃桃问题（递推法）

 穿越沙漠问题（递推法（倒推））

百钱百鸡问题（蛮力法）

数字谜问题（蛮力法） 

第三章

递归算法的设计步骤及其优缺点 设计步骤：

二分查找算法执行过程？

分治算法的基本步骤？

残缺棋盘问题（分治法）

最大子段和（动态规划）

金块问题（分治法）

求第二小元素问题（分治法）

第四章

贪心算法的设计思想

贪心算法设计思想与动态规划算法设计思想，以及他们之间的区别？

👌删除数字问题（贪心算法）

数列极差问题（贪心算法）

币种问题（贪心算法）

取数游戏（贪心算法）

第五章

动态规划基本思想

两个基本要素

四个步骤

0－1背包问题（动态规划）

最大子段和（动态规划）

数字三角形（动态规划） 

第六章

回溯法的定义

回溯法两大特性

回溯法的基本思想

子集树与排列树

八皇后问题（回溯）

---

第一章

算法的定义

算法（algorithm）是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。

算法的三要素

算法由操作、控制结构、数据结构3要素组成。

算法的基本性质

目的性、分步性、有序性、有限性、操作性

算法的时间复杂度数量级：

常数，对数，幂函数，指数，阶乘

---

第二章

兔子繁殖问题（递推法）

一对兔子从出生后第三个月开始，每月生一对小兔子。小兔子到第三个月又开始生下一代小兔子。假若兔子只生不死，一月份抱来一对刚出生的小兔子，问1年中每个月各有多少对兔子。

#include <iostream>

int main() {
    int adult = 0; // 成年兔子对数
    int young = 1; // 未成年兔子对数

    // 计算每个月的兔子对数
    for (int month = 1; month <= 12; ++month) {
        std::cout << "第 " << month << " 个月：" << adult + young << " 对兔子" << std::endl;
        
        int new_adult = young; // 本月成年兔子来自上个月的未成年兔子
        int new_young = adult; // 本月未成年兔子来自上个月的成年兔子
        
        adult = new_adult; // 更新成年兔子对数
        young = new_young + young; // 更新未成年兔子对数
    }

    return 0;
}

猴子吃桃问题（递推法）

一只小猴子摘了若干桃子，每天吃现有桃的一半多一个，到第10天时就只有一个桃子了，求原有多少个桃？ 

#include <iostream>

int main() {
    int peaches = 1; // 第10天剩下的桃子数
    
    // 逆推每天的桃子数
    for (int day = 9; day >= 1; --day) {
        peaches = (peaches + 1) * 2;
    }
    
    std::cout << "原有桃子数：" << peaches << std::endl;

    return 0;
}

 穿越沙漠问题（递推法（倒推））

用一辆吉普车穿越1000公里的沙漠。吉普车的总装油量为500加仑，耗油率为1加仑/公里。由于沙漠中没有油库，必须先用这辆车在沙漠中建立临时油库。该吉普车以最少的耗油量穿越沙漠，应在什么地方建油库，以及各处的贮油量。

#include <iostream>

int main() {
    const int total_distance = 1000; // 总距离
    const int total_gas = 500; // 总装油量

    int min_gas = total_gas; // 最少耗油量
    int gas_station = 0; // 油库位置

    // 从终点开始逆向计算
    for (int i = total_distance; i >= 0; --i) {
        int remaining_gas = total_gas - i; // 到达位置 i 后的剩余油量
        int current_gas = remaining_gas + (total_distance - i) * 2; // 当前位置建库的耗油量

        if (current_gas < min_gas) {
            min_gas = current_gas;
            gas_station = i;
        }
    }

    std::cout << "在距离出发点 " << gas_station << " 公里处建立临时油库，存储 " << total_gas - gas_station << " 加仑的油。" << std::endl;

    return 0;
}

百钱百鸡问题（蛮力法）

 鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？

#include <iostream>

int main() {
    for (int cock = 0; cock <= 20; ++cock) { // 鸡翁数量范围为0到20
        for (int hen = 0; hen <= 33; ++hen) { // 鸡母数量范围为0到33
            int chick = 100 - cock - hen; // 鸡雏数量为100减去鸡翁和鸡母数量

            // 计算总价值
            int total_value = cock * 5 + hen * 3 + chick / 3;

            // 检查是否符合条件
            if (total_value == 100 && chick % 3 == 0) {
                std::cout << "鸡翁：" << cock << " 只，鸡母：" << hen << " 只，鸡雏：" << chick << " 只。" << std::endl;
            }
        }
    }

    return 0;
}

数字谜问题（蛮力法） 

编写算法解如下数字迷。                  

  A  B  C  A  B              

                    ×              

                    A        

————————             

D  D  D  D  D  D

---

第三章

递归算法的设计步骤及其优缺点 设计步骤：

（1）分析并划分问题：将问题分解成若干个规模较小、相互独立，但类型相同的子问题。需 要注意的是各子问题的解必须能够组合成原始问题的一个完整答案。

（2）设计递归函数：根据步骤（1）问题分解的过程，设计出相应的递归函数。设计递归函数 时需要注意两个要素：边界条件和递归方程，递归函数只有具备了这两个要素，才能在有限次 计算后得出结果。

（3）设计程序：根据递归函数设计出解决问题的程序。 优缺点： 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、 调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 

二分查找算法执行过程？

（1）将待查找的数据与非降序数组中的中间元素进行比较，若二者相等则表示查到；

（2）若该数据小于中间元素的值，则下次在数组的前半部分中继续找；              

（3）否则，在数组的后半部分中查找;

（4）即每次查找将与待查数据的比较次数减半,如此继续进行下去，直到查到该值的元素或不存在所查找的数据。

分治算法的基本步骤？

将整个问题分解成若干个小问题后再分而治之。

（1）分解：将原问题分解为若干个规模较小，相互独立，与原问 题形式相同的子问题。

（2）解决：若子问题规模较小而容易被解决则直接解，否则再继 续分解为更小的子问题，直到容易解决。

（3）合并：将已求解的各个子问题的解，逐步合并为原问题的解。

残缺棋盘问题（分治法）

残缺棋盘是一个有2k×2k （k≥1）个方格的棋盘，其中恰有一个方格残缺。图3-1给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。这样的棋盘我们称作“三格板”。 残缺棋盘问题就是要用三格板覆盖更大的残缺棋盘。在此覆盖中要求： 1）两个三格板不能重叠； 2）三格板不能覆盖残缺方格，但必须覆盖其他所有的方格

最大子段和（动态规划）

最大子段和问题：给定由n个数组成的序列a1，a2，……，an，序列中可能有负数，要在这n个数中选取相邻的一段ai， ai+1，……，aj（1≤i≤j≤n）使其和最大，并输出最大和。当所有的数均为负数时，定义最大子段和为0。其中数据个数n和n个数据都通过键盘输入（动态规划算法实现）。

金块问题（分治法）

#include <iostream>
#include <vector>

// 比较两个金块的重量
int compare(int a, int b) {
    if (a > b) return 1;
    if (a < b) return -1;
    return 0;
}

// 在给定范围内找到最重的金块
int find_heaviest(const std::vector<int>& gold, int low, int high) {
    if (low == high) return gold[low]; // 只有一个金块，直接返回

    int mid = (low + high) / 2;
    int left_heaviest = find_heaviest(gold, low, mid); // 左半部分的最重金块
    int right_heaviest = find_heaviest(gold, mid + 1, high); // 右半部分的最重金块

    // 比较左右两部分的最重金块
    return compare(left_heaviest, right_heaviest) > 0 ? left_heaviest : right_heaviest;
}

int main() {
    std::vector<int> gold = {3, 7, 2, 10, 5, 8}; // 金块重量列表
    int n = gold.size();

    int heaviest_gold = find_heaviest(gold, 0, n - 1);
    std::cout << "最重的金块重量为：" << heaviest_gold << std::endl;

    return 0;
}

求第二小元素问题（分治法）

求一组数的第二小的数。

#include <iostream>
#include <vector>
#include <limits>

// 函数：找到一组数的第二小的数
int find_second_min(const std::vector<int>& nums) {
    // 初始化第一小的数和第二小的数为无穷大
    int first_min = std::numeric_limits<int>::max();
    int second_min = std::numeric_limits<int>::max();

    // 遍历数组，更新第一小和第二小的数
    for (int num : nums) {
        if (num < first_min) { // 如果当前数字小于第一小的数，则更新第二小的数为第一小的数，更新第一小的数为当前数字
            second_min = first_min;
            first_min = num;
        } else if (num < second_min && num != first_min) { // 如果当前数字大于第一小的数但小于第二小的数，则更新第二小的数为当前数字
            second_min = num;
        }
    }

    return second_min; // 返回第二小的数
}

int main() {
    // 提示用户输入一组数
    std::cout << "请输入一组数（以空格分隔）: ";

    // 读取用户输入的一组数
    std::vector<int> nums;
    int num;
    while (std::cin >> num) {
        nums.push_back(num);
    }

    // 找到第二小的数并输出
    int second_min = find_second_min(nums);
    std::cout << "第二小的数是：" << second_min << std::endl;

    return 0;
}

---

第四章

贪心算法的设计思想

贪心算法的基本思想是找出整体当中每个小的局部的最优解，并且将所有的这些局部最优解合起来形成整体上的一个最优解。                                          

 因此能够使用贪心算法的问题必须满足下面的两个性质：

（1）整体的最优解可以通过局部的最优解来求出；                      

（2）一个整体能够被分为多个局部，并且这些局部都能够求出最优解。

贪心算法设计思想与动态规划算法设计思想，以及他们之间的区别？

贪心算法的设计思想是每一步选择当前状态下的最优解，期望通过一系列局部最优解得到全局最优解。动态规划算法的设计思想是将问题分解为相互重叠的子问题，并通过求解这些子问题，最终得到原问题的解。贪心算法通常更简单高效，但可能无法得到全局最优解；动态规划算法可以解决一些贪心算法无法解决的问题，但实现更复杂，需要额外空间来存储中间结果。贪心算法是自顶向下，动态规划是自底向上方式求解各个子问题。

👌删除数字问题（贪心算法）

键盘输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

#include <iostream>
#include <string>

std::string removeDigits(const std::string& n, int s) {
    std::string result;
    for (char digit : n) {
        while (s > 0 && !result.empty() && result.back() > digit) {
            result.pop_back();
            --s;
        }
        result.push_back(digit);
    }

    // 删除剩余的 s 个数字
    result.resize(result.size() - s);

    // 去除前导零
    int pos = 0;
    while (pos < result.size() && result[pos] == '0') {
        ++pos;
    }
    result = result.substr(pos);

    return result.empty() ? "0" : result;
}

int main() {
    std::string n;
    int s;
    std::cout << "请输入一个正整数 n 和需要删除的数字个数 s：" << std::endl;
    std::cin >> n >> s;

    std::string newNumber = removeDigits(n, s);
    std::cout << "去掉 " << s << " 个数字后剩下的数字组成的新数是：" << newNumber << std::endl;

    return 0;
}

数列极差问题（贪心算法）

在黑板上写了N个正整数作成的一个数列，进行如下操作:每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的记作max，最小的记作min，则该数列的极差定义为M=max-min。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

// 计算数列的极差
int calculateRange(const std::vector<int>& nums) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap(nums.begin(), nums.end());
    std::priority_queue<int, std::vector<int>, std::less<int>> max_heap(nums.begin(), nums.end());

    while (min_heap.size() > 1) {
        int a = min_heap.top();
        min_heap.pop();
        int b = min_heap.top();
        min_heap.pop();

        min_heap.push(a * b + 1);
    }

    while (max_heap.size() > 1) {
        int a = max_heap.top();
        max_heap.pop();
        int b = max_heap.top();
        max_heap.pop();

        max_heap.push(a * b + 1);
    }

    int min = min_heap.top();
    int max = max_heap.top();

    return max - min;
}

int main() {
    int n;
    std::cout << "请输入数列的长度 n：" << std::endl;
    std::cin >> n;

    std::vector<int> nums(n);
    std::cout << "请输入 " << n << " 个正整数：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }

    int range = calculateRange(nums);
    std::cout << "数列的极差为：" << range << std::endl;

    return 0;
}

币种问题（贪心算法）

某单位给每个职工发工资（精确到元）。为了保证不要临时兑换零钱, 且取款的张数最少，取工资前要统计出所有职工的工资所需各种币值(100,50,20,10,5,2,1元共七种)的张数。请编程完成。

#include <iostream>
#include <vector>

// 计算每个职工工资所需各种面额的张数
std::vector<std::vector<int>> calculateSalaryBills(const std::vector<int>& salaries) {
    // 定义面额数组
    std::vector<int> denominations = {100, 50, 20, 10, 5, 2, 1};
    std::vector<std::vector<int>> bills(salaries.size(), std::vector<int>(denominations.size(), 0));

    // 对每个职工的工资进行处理
    for (int i = 0; i < salaries.size(); ++i) {
        int salary = salaries[i];
        // 遍历面额数组
        for (int j = 0; j < denominations.size(); ++j) {
            int denomination = denominations[j];
            // 计算当前面额需要的张数
            int count = salary / denomination;
            // 更新剩余工资
            salary -= count * denomination;
            // 记录当前面额的张数
            bills[i][j] = count;
        }
    }

    return bills;
}

int main() {
    // 输入每个职工的工资
    int n;
    std::cout << "请输入职工人数：";
    std::cin >> n;
    std::vector<int> salaries(n);
    std::cout << "请输入每个职工的工资（以空格分隔）：";
    for (int i = 0; i < n; ++i) {
        std::cin >> salaries[i];
    }

    // 计算各种面额的张数
    std::vector<std::vector<int>> bills = calculateSalaryBills(salaries);

    // 输出结果
    std::cout << "各个职工工资所需各种币值的张数：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cout << "第 " << i + 1 << " 个职工：" << std::endl;
        for (int j = 0; j < bills[i].size(); ++j) {
            std::cout << bills[i][j] << " 张 " << (j == 0 ? "100" : std::to_string(bills[i][j])) << " 元；";
        }
        std::cout << std::endl;
    }

    return 0;
}

取数游戏（贪心算法）

有2个人轮流取2n个数中的n个数，取数之和大者为胜。请编写算法，让先取数者胜，模拟取数过程。 游戏规则：这个游戏规定取数者只能看到2n个数中两端的数。

#include <iostream>
#include <vector>

// 模拟游戏过程
int playGame(const std::vector<int>& nums) {
    int n = nums.size() / 2; // 总数的一半
    int first_player_score = 0;
    int second_player_score = 0;

    for (int i = 0; i < n; ++i) {
        // 先取数者选择较大的数
        if (nums[i] > nums[nums.size() - i - 1]) {
            first_player_score += nums[i];
        } else {
            second_player_score += nums[nums.size() - i - 1];
        }
    }

    // 返回先取数者的得分
    return first_player_score;
}

int main() {
    // 输入2n个数
    int n;
    std::cout << "请输入2n个数：" << std::endl;
    std::cin >> n;
    std::vector<int> nums(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        std::cin >> nums[i];
    }

    // 模拟游戏过程并输出结果
    int first_player_score = playGame(nums);
    std::cout << "先取数者的得分为：" << first_player_score << std::endl;

    return 0;
}

---

第五章

动态规划基本思想

基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解

两个基本要素

最优子结构性质和子问题重叠性质。

四个步骤

（1）分析最优子结构性质 是基础，也是关键。子问题的分解和对应的的子问题描述是关键。 （2）递归地定义最优值 是动态规划算法的核心，它是最优解的规划过程。

（3）以自底向上的方式计算出最优值 体现了动态规划算法的执行过程。

（4）构造最优解 是可选步骤，只有问题要求构造最优解时才需要

0－1背包问题（动态规划）

给定一个物品集合s＝｛1，2，3，…，n｝，物品i的重量是wi，其价值是vi，背包的容量为W，即最大载重量不超过W。在限定的总重量W内，我们如何选择物品，才能使得物品的总价值最大。

#include <iostream>
#include <vector>
#include <algorithm>

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= W; ++j) {
            if (weights[i - 1] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][W];
}

int main() {
    int n, W;
    std::cout << "请输入物品个数 n 和背包容量 W：" << std::endl;
    std::cin >> n >> W;

    std::vector<int> weights(n);
    std::vector<int> values(n);
    std::cout << "请输入每个物品的重量和价值：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cin >> weights[i] >> values[i];
    }

    int max_value = knapsack(W, weights, values);
    std::cout << "在背包容量为 " << W << " 的情况下，可以获得的最大总价值为：" << max_value << std::endl;

    return 0;
}

最大子段和（动态规划）

最大子段和问题：给定由n个数组成的序列a1，a2，……，an，序列中可能有负数，要在这n个数中选取相邻的一段ai， ai+1，……，aj（1≤i≤j≤n）使其和最大，并输出最大和。当所有的数均为负数时，定义最大子段和为0。其中数据个数n和n个数据都通过键盘输入（动态规划算法实现）。

#include <iostream>
#include <vector>

int maxSubArray(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    int max_sum = nums[0]; // 最大子段和
    int current_sum = nums[0]; // 当前子段和

    for (int i = 1; i < n; ++i) {
        // 更新当前子段和
        current_sum = std::max(current_sum + nums[i], nums[i]);
        // 更新最大子段和
        max_sum = std::max(max_sum, current_sum);
    }

    return max_sum;
}

int main() {
    int n;
    std::cout << "请输入数据个数 n：" << std::endl;
    std::cin >> n;

    std::vector<int> nums(n);
    std::cout << "请输入 " << n << " 个数据：" << std::endl;
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }

    int max_sum = maxSubArray(nums);
    std::cout << "最大子段和为：" << max_sum << std::endl;

    return 0;
}

数字三角形（动态规划） 

数字三角形问题：如下图是一个数字三角形，从顶部出发在每一个节点可以选择向左或者向右走，一直走到底层，要求找出一条路径，使得路径上的数字之和最大。（动态规划算法设计）

---

第六章

回溯法的定义

以深度优先的方式系统地搜索问题的解的方法称为回溯法。

回溯法两大特性

系统性 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

跳跃性 算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本思想

回溯法的基本步骤

(1)针对所给问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

子集树与排列树

子集树 从n个元素的集合S中找出S满足某种性质的子集，相应的解空间称为子集树。通常有2n个叶结点，结点总数为2n+1-1。需Ω(2n)计算时间。 如n个物品的0-1背包问题的解空间是一棵子集树。

排列树 当所给问题的确定n个元素满足某种性质的排列时，相应的解空间树称为排列树。排列树通常有n!个叶结点。因此遍历排列树需要Ω(n!)计算时间。 TSP(旅行售货员问题)的解空间是一棵排列树。

八皇后问题（回溯）

八皇后问题：在8×8的国际象棋盘上，放置8个皇后，使任何一个皇后都不能吃掉其他皇后,要使任何一个皇后都不能吃掉其他皇后需满足的条件是：同一行、同一列、同一对角线上只能有一个皇后，求放置方法。 （回溯法设计）

#include <iostream>
#include <vector>

bool isValid(const std::vector<int>& queens, int row, int col) {
    // 检查当前列是否已经有皇后
    for (int i = 0; i < row; ++i) {
        if (queens[i] == col || std::abs(i - row) == std::abs(queens[i] - col)) {
            return false;
        }
    }
    return true;
}

void solveNQueens(std::vector<std::vector<int>>& solutions, std::vector<int>& queens, int row, int n) {
    if (row == n) {
        solutions.push_back(queens);
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isValid(queens, row, col)) {
            queens[row] = col;
            solveNQueens(solutions, queens, row + 1, n);
        }
    }
}

void printSolution(const std::vector<int>& queens) {
    int n = queens.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cout << (queens[i] == j ? "Q" : ".");
            std::cout << " ";
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    int n = 8; // 8×8 的棋盘
    std::vector<std::vector<int>> solutions;
    std::vector<int> queens(n, 0); // queens[i] 表示第 i 行皇后所在的列

    solveNQueens(solutions, queens, 0, n);

    // 输出所有解
    std::cout << "八皇后问题的所有解：" << std::endl;
    for (const auto& solution : solutions) {
        printSolution(solution);
    }

    return 0;
}