本文主要是介绍算法设计与分析——期末1h，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
第一章
算法的定义
算法的三要素
算法的基本性质
算法的时间复杂度数量级：
第二章
兔子繁殖问题（递推法）
猴子吃桃问题（递推法）
穿越沙漠问题（递推法（倒推））
百钱百鸡问题（蛮力法）
数字谜问题（蛮力法）
第三章
递归算法的设计步骤及其优缺点 设计步骤：
二分查找算法执行过程？
分治算法的基本步骤？
残缺棋盘问题（分治法）
最大子段和（动态规划）
金块问题（分治法）
求第二小元素问题（分治法）
第四章
贪心算法的设计思想
贪心算法设计思想与动态规划算法设计思想，以及他们之间的区别？
👌删除数字问题（贪心算法）
数列极差问题（贪心算法）
币种问题（贪心算法）
取数游戏（贪心算法）
第五章
动态规划基本思想
两个基本要素
四个步骤
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;
}
这篇关于算法设计与分析——期末1h的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
