目录
第一章
算法的定义
算法的三要素
算法的基本性质
算法的时间复杂度数量级:
第二章
兔子繁殖问题(递推法)
猴子吃桃问题(递推法)
穿越沙漠问题(递推法(倒推))
百钱百鸡问题(蛮力法)
数字谜问题(蛮力法)
第三章
递归算法的设计步骤及其优缺点 设计步骤:
二分查找算法执行过程?
分治算法的基本步骤?
残缺棋盘问题(分治法)
最大子段和(动态规划)
金块问题(分治法)
求第二小元素问题(分治法)
第四章
贪心算法的设计思想
贪心算法设计思想与动态规划算法设计思想,以及他们之间的区别?
👌删除数字问题(贪心算法)
数列极差问题(贪心算法)
币种问题(贪心算法)
取数游戏(贪心算法)
第五章
动态规划基本思想
两个基本要素
四个步骤
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到20for (int hen = 0; hen <= 33; ++hen) { // 鸡母数量范围为0到33int 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;
}