算法设计期末复习

embedded/2024/12/24 4:14:30/

文章目录

      • 1. 什么是算法，算法有哪些特征，算法设计的基本步骤，算法的时间复杂度的确定
      • 2. 什么是算法分析，算法分析的主要内容是什么？怎么确定算法的时间复杂度？
      • 3. 什么是分治算法，分治算法通常用哪些步骤来实现？常用什么数据结构和对应的算法
      • 4. 什么是蛮力法，有哪些应用，能解决什么问题，要写出对应策略、算法
      • 5. 什么是回溯法，有哪些应用，能解决什么问题，要写出对应策略、算法
      • 6. 什么是分枝限界法，有哪些应用，能解决什么问题，要写出对应策略、算法
      • 7. 分枝限界法和回溯的区别？
      • 8. 01背包问题的各种解决方案
      • 9. 最优装载问题方案及相关算法
      • 10. 最优活动安排方案及相关算法
      • 11. 动态规划问题的完成最短路径及路径长度
      • 12. 什么是概率算法、有哪些分类

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. 动态规划问题的完成最短路径及路径长度

#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. 舍伍德算法：通过随机化来消除算法的确定性。

http://www.ppmy.cn/embedded/148244.html

相关文章

ACL-2024 | MapGPT：基于地图引导提示和自适应路径规划机制的视觉语言导航

ACL-2024 | MapGPT：基于地图引导提示和自适应路径规划机制的视觉语言导航

作者&#xff1a; Jiaqi Chen, Bingqian Lin, Ran Xu, Zhenhua Chai, Xiaodan Liang, Kwan-Yee K. Wong, 单位&#xff1a; 香港大学&#xff0c;中山大学深圳校区&#xff0c;美团 原文链接&#xff1a;MapGPT: Map-Guided Prompting with Adaptive Path Planning for Visio…
阅读更多...
armsom产品Debian系统开发

armsom产品Debian系统开发

第一章 构建 Debian Linux 系统 我们需要按【armsom产品编译&烧录Linux固件】全自动编译一次&#xff0c;默认是编译 Buildroot 系统&#xff0c;也会编 译 uboot 和内核&#xff0c;buildroot 某些软件包依赖内核&#xff0c;所以我们必须编译内核再编译 Buildroot。同 理…
阅读更多...
什么？Flutter 可能会被 SwiftUI/ArkUI 化？全新的 Flutter Roadmap

什么？Flutter 可能会被 SwiftUI/ArkUI 化？全新的 Flutter Roadmap

在刚刚过去的 FlutterInProduction 活动里&#xff0c;Flutter 官方除了介绍「历史进程」和「用户案例」之外&#xff0c;也着重提及了未来相关的 roadmap &#xff0c;其中就有 3.27 里的 Swift Package Manager 、 Widget 实时预览 和 Dart 与 native 平台原生语言直接互操作…
阅读更多...
学习ASP.NET Core的身份认证（基于JwtBearer的身份认证2）

学习ASP.NET Core的身份认证（基于JwtBearer的身份认证2）

根据参考文献8中的介绍&#xff0c;JWT Token主要分为3个部分&#xff1a;   1&#xff09;标题&#xff08;Header&#xff09;&#xff1a;主要记录令牌类型、签名算法&#xff08;加密算法&#xff09;类型&#xff0c;格式为Json字符串&#xff0c;然后使用Base64编码字符…
阅读更多...
探索Linux中的Zombie僵死进程

探索Linux中的Zombie僵死进程

文章目录 探索Linux中的Zombie僵死进程什么是Zombie僵死进程&#xff1f;僵死进程的产生原因如何识别僵死进程&#xff1f;如何清理僵死进程&#xff1f;僵死进程对系统的影响总结 探索Linux中的Zombie僵死进程 在Linux系统中&#xff0c;进程管理是一个非常重要的主题&#x…
阅读更多...
Python发送带key的kafka消息

Python发送带key的kafka消息

在Python中发送带有键&#xff08;key&#xff09;的Kafka消息&#xff0c;通常会使用confluent-kafka或kafka-python这样的库。这里我将分别展示如何使用这两个库来实现这个功能。 ### 使用 confluent-kafka 首先&#xff0c;确保你已经安装了confluent-kafka库。如果没有安装…
阅读更多...
陪诊小程序搭建，打造一站式陪诊服务

陪诊小程序搭建，打造一站式陪诊服务

当下&#xff0c;陪诊市场正在持续火热发展&#xff0c;在全国医疗行业中&#xff0c;陪诊师成为了一个重要的就医方式。陪诊师的出现在快节奏生活下显得尤为重要&#xff0c;为不少没有时间陪老人去医院的家庭以及对医院不熟悉的提供了便利&#xff0c;满足了众多患者及其家属…
阅读更多...
梳理你的思路(从OOP到架构设计)_介绍GoF设计模式

梳理你的思路(从OOP到架构设计)_介绍GoF设计模式

目录 GoF的由来 GoF的种类 GoF的由来 裁缝有样式、围棋有棋谱、烹饪有食谱、武功有招式、战争有兵法&#xff0c; ..... 皆是专家和高手的经验心得&#xff0c;通称为&#xff1a;模式(Pattern)。模式告诉您理想的方案像什么、有那些特性﹔ 同时也告诉您些规则&#xff0c;让…
阅读更多...
最新文章

Copyright @ 2022~2023