1. 什么是算法，算法有哪些特征，算法设计的基本步骤，算法的时间复杂度的确定

什么是算法？
算法：求解问题的一系列计算步骤，用来将输入数据转换成输出结果。

算法的特征：

• 有穷性：算法必须在有限步骤内结束。
• 确定性：每一步骤都有明确的定义，不会产生歧义。
• 输入：算法有零个或多个输入。
• 输出：算法有一个或多个输出。
• 可行性：算法中的每一步骤都可以通过基本操作实现。

算法设计的基本步骤：

1. 理解问题。
2. 确定输入和输出。
3. 设计解决问题的步骤。
4. 验证算法的正确性。
5. 分析算法的时间和空间复杂度。
6. 优化算法（如果需要）。

算法的时间复杂度的确定：
时间复杂度是算法运行时间的增长率，通常用大O符号表示。它反映了算法执行时间随输入规模增长的变化趋势。例如：

• 常数时间：O(1)
• 线性时间：O(n)
• 对数时间：O(log n)
• 平方时间：O(n²)

---

2. 什么是算法分析，算法分析的主要内容是什么？怎么确定算法的时间复杂度？

什么是算法分析？
算法分析是对算法的时间复杂度、空间复杂度以及正确性进行评估的过程。

算法分析的主要内容：

1. 时间复杂度：算法执行所需的时间。
2. 空间复杂度：算法执行所需的内存空间。
3. 正确性：算法是否能正确解决问题。
4. 优化性：算法是否高效。

怎么确定算法的时间复杂度？

1. 分析算法中每一步的基本操作次数。
2. 找出最坏情况下的操作次数。
3. 用大O符号表示时间复杂度。

例如，对于一个简单的循环：

for (int i = 0; i < n; i++) {cout << i << endl;
}

时间复杂度为O(n)。

---

3. 什么是分治算法，分治算法通常用哪些步骤来实现？常用什么数据结构和对应的算法

什么是分治算法？
分治算法是一种将问题分解为若干个子问题，分别解决后再合并结果的算法。

分治算法的步骤：

1. 分解：将问题分解为若干个子问题。
2. 解决：递归地解决子问题。
3. 合并：将子问题的解合并为原问题的解。

常用的数据结构和算法：

• 归并排序：将数组分成两部分，分别排序后再合并。
• 快速排序：选择一个基准元素，将数组分为两部分，分别排序。
• 二分查找：在有序数组中查找元素。

---

4. 什么是蛮力法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是蛮力法？
蛮力法是一种直接解决问题的方法，通常通过穷举所有可能的解来找到答案。

应用：

• 排序（如选择排序、冒泡排序）。
• 查找（如线性查找）。
• 字符串匹配（如朴素字符串匹配算法）。

能解决的问题：

• 简单问题或规模较小的问题。
• 需要找到所有可能解的问题。

策略和算法：

• 选择排序：

void selection_sort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {int min_idx = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}swap(arr[i], arr[min_idx]);}
}

---

5. 什么是回溯法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是回溯法？
回溯法是一种通过尝试所有可能的解来解决问题的算法，当发现当前解不可行时，回退并尝试其他路径。

应用：

• 八皇后问题。
• 数独问题。
• 图的遍历。

能解决的问题：

• 组合优化问题。
• 路径搜索问题。

策略和算法：

• 八皇后问题：

#include <vector>
#include <string>
using namespace std;class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> result;vector<string> board(n, string(n, '.'));backtrack(result, board, 0, n);return result;}void backtrack(vector<vector<string>>& result, vector<string>& board, int row, int n) {if (row == n) {result.push_back(board);return;}for (int col = 0; col < n; col++) {if (is_safe(board, row, col, n)) {board[row][col] = 'Q';backtrack(result, board, row + 1, n);board[row][col] = '.';}}}bool is_safe(vector<string>& board, int row, int col, int n) {for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') {return false;}}return true;}
};

---

6. 什么是分枝限界法，有哪些应用，能解决什么问题，要写出对应策略、算法

什么是分枝限界法？
分枝限界法是一种通过剪枝来减少搜索空间的算法，通常用于解决组合优化问题。

应用：

• 旅行商问题。
• 0/1背包问题。
• 图的最短路径问题。

能解决的问题：

• 需要找到最优解的问题。
• 组合优化问题。

策略和算法：

• 0/1背包问题：

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;struct Node {int level;int profit;int weight;
};struct Item {int value;int weight;
};int bound(Node node, int capacity, vector<Item>& items) {if (node.weight >= capacity) {return 0;}int profit_bound = node.profit;int j = node.level + 1;int totweight = node.weight;while (j < items.size() && totweight + items[j].weight <= capacity) {totweight += items[j].weight;profit_bound += items[j].value;j++;}if (j < items.size()) {profit_bound += (capacity - totweight) * items[j].value / items[j].weight;}return profit_bound;
}int branch_and_bound(vector<Item>& items, int capacity) {queue<Node> q;Node root = {-1, 0, 0};q.push(root);int max_profit = 0;while (!q.empty()) {Node node = q.front();q.pop();if (node.level == items.size() - 1) {continue;}Node next_node = {node.level + 1, node.profit + items[node.level + 1].value, node.weight + items[node.level + 1].weight};if (next_node.weight <= capacity && next_node.profit > max_profit) {max_profit = next_node.profit;}if (bound(next_node, capacity, items) > max_profit) {q.push(next_node);}next_node = {node.level + 1, node.profit, node.weight};if (bound(next_node, capacity, items) > max_profit) {q.push(next_node);}}return max_profit;
}

---

7. 分枝限界法和回溯的区别？

• 回溯法：通过尝试所有可能的解来解决问题，当发现当前解不可行时，回退并尝试其他路径。
• 分枝限界法：通过剪枝来减少搜索空间，通常用于解决需要找到最优解的问题。

---

8. 01背包问题的各种解决方案

• 蛮力法：穷举所有可能的组合。
• 动态规划：

#include <vector>
#include <algorithm>
using namespace std;int knapsack(vector<int>& weights, vector<int>& values, int capacity) {int n = weights.size();vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));for (int i = 1; i <= n; i++) {for (int w = 1; w <= capacity; w++) {if (weights[i - 1] <= w) {dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][capacity];
}

---

9. 最优装载问题方案及相关算法

• 贪心算法：

#include <vector>
#include <algorithm>
using namespace std;int optimal_loading(vector<int>& weights, int capacity) {sort(weights.begin(), weights.end());int total_weight = 0;int count = 0;for (int weight : weights) {if (total_weight + weight <= capacity) {total_weight += weight;count++;}}return count;
}

---

10. 最优活动安排方案及相关算法

• 贪心算法：

#include <vector>
#include <algorithm>
using namespace std;vector<pair<int, int>> activity_selection(vector<int>& start, vector<int>& finish) {vector<pair<int, int>> activities;for (int i = 0; i < start.size(); i++) {activities.push_back({start[i], finish[i]});}sort(activities.begin(), activities.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second < b.second;});vector<pair<int, int>> selected = {activities[0]};for (int i = 1; i < activities.size(); i++) {if (activities[i].first >= selected.back().second) {selected.push_back(activities[i]);}}return selected;
}

---

11. 动态规划问题的完成最短路径及路径长度

• Floyd-Warshall算法：

#include <vector>
#include <algorithm>
using namespace std;vector<vector<int>> floyd_warshall(vector<vector<int>>& graph) {int n = graph.size();vector<vector<int>> dist = graph;for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}return dist;
}

---

12. 什么是概率算法、有哪些分类

什么是概率算法？
概率算法是一种利用随机性来解决问题的算法。

分类：

1. 蒙特卡洛算法：可能得到错误解，但错误概率可控。
2. 拉斯维加斯算法：不会得到错误解，但可能无法在有限时间内完成。
3. 舍伍德算法：通过随机化来消除算法的确定性。

---