下载文档原格式
实验报告（2013/2014学年第一学期）课程名称算法分析与设计实验名称密码算法实验时间2014 年 5 月23 日指导单位计算机学院软件工程系指导教师张怡婷学生姓名班级学号B******** 学院(系) 软件工程专业软件工程实验报告三、实验原理及内容（包括操作过程、结果分析等）实验步骤1、RSA 算法是由麻省理工学院的Ron Rivest,Adi Shamir 和Len Adleman 于1977 年研制并于1978 年首次发表的一种算法，是第一个能同时用于加密和数字签名的算法，且易于理解和操作，因此作为一种通用公开密钥加密方式而受到推崇。
RSA 是一种分组密码，其中明文和密文都是小于某个n 的从0 到n-1 的整数，则分组的二进制值长度必须小于或等于log2n。
若以M 表示明文分组，而C 表示密文分组，则加密和解密的过程如下：C=Me mod nM=Cd mod n=(Me)d mod n=Med mod n发送方和接受方都必须知道n 的值。
发送方知道 e 的值，而只有接受方知道d 的值。
因此这是一种公开密钥为{e,n}，且私有密钥为{d,n}的公开密钥加密算法。
此时算法要能够满足公开密钥加密的要求，则必须满足以下条件：（1）有可能找到e、d、n 的值，使得对所有M<n 有Med=M mod n。
（2）对于所有M<n 的值，要计算Me和Cd 相对来说是简单的。
（3）在给定e 和n 时，判断出 d 是不可行的。
2、重点考虑第一个条件：由Euler 定理的一个推论：给定两个素数p和q以及两个整数n 和m，使得n=pq 而且0<m<n，并且对于任意整数k，下列关系成立：mkΦ(n)+1=mk(p-1)(q-1)+1≡m mod n其中Φ(n)是欧拉函数，也就是不超过n 且与n 互素的整数个数。
对于素数p 和q，有Φ(pq)=(p-1)(q-1)。
因此得到需要的关系：ed=kΦ(n)+1，等价于: ed≡1 mod Φ(n)d≡e-1 mod Φ(n)也就是说：d 和 e 是以Φ(n)为模的乘法逆元。
第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。
算法分析与设计实验报告：合并排序与快速排序一、引言算法是计算机科学中非常重要的一部分，它涉及到解决问题的方法和步骤。
合并排序和快速排序是两种经典而常用的排序算法。
本文将对这两种排序算法进行分析和设计实验，通过对比它们的性能和效率，以期得出最优算法。
二、合并排序合并排序是一种分治算法，它将原始数组不断分解为更小的数组，直到最后细分为单个元素。
然后，再将这些单个元素两两合并，形成一个有序数组。
合并排序的核心操作是合并两个有序的数组。
1. 算法步骤（1）将原始数组分解为更小的子数组，直到每个子数组只有一个元素；（2）两两合并相邻的子数组，同时进行排序，生成新的有序数组；（3）重复步骤（2），直到生成最终的有序数组。
2. 算法性能合并排序的最优时间复杂度为O(nlogn)，其中n为待排序数组的长度。
无论最好情况还是最坏情况，合并排序的复杂度都相同。
合并排序需要额外的存储空间来存储临时数组，所以空间复杂度为O(n)。
三、快速排序快速排序也是一种分治算法，它将原始数组根据一个主元（pivot）分成两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元。
然后，递归地对这两个子数组进行排序，最后得到有序数组。
快速排序的核心操作是划分。
1. 算法步骤（1）选择一个主元（pivot），可以是随机选择或者固定选择第一个元素；（2）将原始数组根据主元划分为两个子数组，一个子数组的元素都小于主元，另一个子数组的元素都大于主元；（3）递归地对这两个子数组进行快速排序；（4）重复步骤（2）和（3），直到每个子数组只有一个元素，即得到最终的有序数组。
2. 算法性能快速排序的平均时间复杂度为O(nlogn)，其中n为待排序数组的长度。
最坏情况下，当每次选择的主元都是最小或最大元素时，时间复杂度为O(n^2)。
快速排序是原地排序，不需要额外的存储空间，所以空间复杂度为O(1)。
四、实验设计为了验证合并排序和快速排序的性能和效率，我们设计以下实验：1. 实验目的：比较合并排序和快速排序的时间复杂度和空间复杂度。
第1篇一、实验背景随着信息技术的飞速发展，模型网络算法在各个领域都得到了广泛应用。
为了深入了解模型网络算法的原理和应用，我们设计并完成了一次模型网络算法实验。
本次实验旨在通过构建一个简单的模型网络，学习并验证模型网络算法在数据处理和模式识别等方面的性能。
二、实验目的1. 理解模型网络算法的基本原理；2. 掌握模型网络算法的实现方法；3. 评估模型网络算法在不同数据集上的性能；4. 分析模型网络算法的优缺点。
三、实验环境1. 操作系统：Windows 102. 编程语言：Python3. 库：NumPy、Scikit-learn、Matplotlib4. 数据集：Iris数据集、MNIST数据集四、实验内容1. 模型网络算法概述模型网络算法是一种基于图论的算法，通过构建模型网络来模拟真实世界中的复杂关系。
模型网络由节点和边组成，节点代表实体，边代表实体之间的关系。
模型网络算法可以用于数据分析、模式识别、知识图谱构建等领域。
2. 模型网络算法实现本次实验采用Python编程语言实现模型网络算法。
具体步骤如下：（1）加载数据集：从Iris数据集和MNIST数据集中获取数据。
（2）构建模型网络：根据数据集的特征，构建模型网络。
例如，在Iris数据集中，可以按照花种类型构建节点，按照特征值构建边。
（3）模型网络算法：使用模型网络算法对数据进行处理。
例如，使用PageRank算法计算节点的权重，使用链接预测算法预测节点之间的关系。
（4）性能评估：使用准确率、召回率、F1值等指标评估模型网络算法在不同数据集上的性能。
3. 实验结果与分析（1）Iris数据集在Iris数据集上，我们使用PageRank算法计算节点的权重，并使用链接预测算法预测节点之间的关系。
实验结果显示，模型网络算法在Iris数据集上的准确率达到80%以上。
（2）MNIST数据集在MNIST数据集上，我们使用模型网络算法对图像进行分类。
实验结果显示，模型网络算法在MNIST数据集上的准确率达到90%以上。
实验报告院部：计算机信息与科学专业班级：计科1703学号：学生姓名：学期： 2019-2020-2}printf("\n\n");bubble(a, n);printf("冒泡递增排列为：\n");for (i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");printf("\n");printf("99乘法表如下:\n");chengfa(1, 1);system("pause");return 0;}图1-1 运行结果printf("您输入的字符串超过最大长度,请重新输入!");scanf("%s", X);}printf("请输入字符串Y:");scanf("%s", Y);while (strlen(Y) > 200){printf("您输入的字符串超过最大长度,请重新输入!");scanf("%s", Y);}s = LCS(X, Y);printf("X和Y的LCS数: %d \n", s);printf("----------------分割线----------------\n"); printf("投资最大利润问题：\n");profit();}图2-1 运行结果图3-1 运行结果五实验小节通过本次实验，充分理解了动态规划的基本思想和程序的执行过程，并且能熟练编写相应的程序；同时，在编程的过程中，进一步加深理解动态规划算法的两个基本要素最优子结构性质和子问题的重叠性质，对上一次实验所学到的知识进行了进一步的巩固加强，学会了规避一些逻辑上的错误；熟练地掌握了典型的动态规划问题，能够运用动态规划思想分析问题的一般方法，对较简单的问题能够正确分析，设计出动态规划算法，并且能快速编程实现。
题目: a算法求解八数码问题实验报告目录1. 实验目的2. 实验设计3. 实验过程4. 实验结果5. 实验分析6. 实验总结1. 实验目的本实验旨在通过实验验证a算法在求解八数码问题时的效果，并对其进行分析和总结。
2. 实验设计a算法是一种启发式搜索算法，主要用于在图形搜索和有向图中找到最短路径。
在本实验中，我们将使用a算法来解决八数码问题，即在3x3的九宫格中，给定一个初始状态和一个目标状态，通过移动数字的方式将初始状态转变为目标状态。
具体的实验设计如下：1) 实验工具：我们将使用编程语言来实现a算法，并结合九宫格的数据结构来解决八数码问题。
2) 实验流程：我们将设计一个初始状态和一个目标状态，然后通过a 算法来求解初始状态到目标状态的最短路径。
在求解的过程中，我们将记录下每一步的状态变化和移动路径。
3. 实验过程我们在编程语言中实现了a算法，并用于求解八数码问题。
具体的实验过程如下：1) 初始状态和目标状态的设计：我们设计了一个初始状态和一个目标状态，分别为：初始状态：1 2 34 5 67 8 0目标状态：1 2 38 0 42) a算法求解：我们通过a算法来求解初始状态到目标状态的最短路径，并记录下每一步的状态变化和移动路径。
3) 实验结果在实验中，我们成功求解出了初始状态到目标状态的最短路径，并记录下了每一步的状态变化和移动路径。
具体的实验结果如下：初始状态：1 2 34 5 67 8 0目标状态：1 2 38 0 47 6 5求解路径：1. 上移1 2 37 8 62. 左移1 2 3 4 0 5 7 8 63. 下移1 2 3 4 8 5 7 0 64. 右移1 2 3 4 8 5 0 7 65. 上移1 2 3 0 8 5 4 7 61 2 38 0 54 7 67. 下移1 2 38 7 54 0 68. 右移1 2 38 7 54 6 0共计8步，成功从初始状态到目标状态的最短路径。
第1篇一、实验目的通过本次实验，掌握常见算法的设计原理、实现方法以及性能分析。
通过实际编程，加深对算法的理解，提高编程能力，并学会运用算法解决实际问题。
二、实验内容本次实验选择了以下常见算法进行设计和实现：1. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。
2. 查找算法：顺序查找、二分查找。
3. 图算法：深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）。
4. 动态规划算法：0-1背包问题。
三、实验原理1. 排序算法：排序算法的主要目的是将一组数据按照一定的顺序排列。
常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序等。
2. 查找算法：查找算法用于在数据集中查找特定的元素。
常见的查找算法包括顺序查找和二分查找。
3. 图算法：图算法用于处理图结构的数据。
常见的图算法包括深度优先搜索（DFS）、广度优先搜索（BFS）、最小生成树（Prim算法、Kruskal算法）等。
4. 动态规划算法：动态规划算法是一种将复杂问题分解为子问题，通过求解子问题来求解原问题的算法。
常见的动态规划算法包括0-1背包问题。
四、实验过程1. 排序算法（1）冒泡排序：通过比较相邻元素，如果顺序错误则交换，重复此过程，直到没有需要交换的元素。
（2）选择排序：每次从剩余元素中选取最小（或最大）的元素，放到已排序序列的末尾。
（3）插入排序：将未排序的数据插入到已排序序列中适当的位置。
（4）快速排序：选择一个枢纽元素，将序列分为两部分，使左侧不大于枢纽，右侧不小于枢纽，然后递归地对两部分进行快速排序。
（5）归并排序：将序列分为两半，分别对两半进行归并排序，然后将排序好的两半合并。
（6）堆排序：将序列构建成最大堆，然后重复取出堆顶元素，并调整剩余元素，使剩余元素仍满足最大堆的性质。
2. 查找算法（1）顺序查找：从序列的第一个元素开始，依次比较，直到找到目标元素或遍历完整个序列。
排序算法设计实验报告总结1. 引言排序算法是计算机科学中最基础的算法之一，它的作用是将一组数据按照特定的顺序进行排列。
在现实生活中，我们经常需要对一些数据进行排序，比如学生成绩的排名、图书按照标题首字母进行排序等等。
因此，了解不同的排序算法的性能特点以及如何选择合适的排序算法对于解决实际问题非常重要。
本次实验旨在设计和实现几种经典的排序算法，并对其进行比较和总结。
2. 实验方法本次实验设计了四种排序算法，分别为冒泡排序、插入排序、选择排序和快速排序。
实验采用Python语言进行实现，并通过编写测试函数对算法进行验证。
测试函数会生成一定数量的随机数，并对这些随机数进行排序，统计算法的执行时间和比较次数，最后将结果进行记录和分析。
3. 测试结果及分析3.1 冒泡排序冒泡排序是一种简单且常用的排序算法，其基本思想是从待排序的数据中依次比较相邻的两个元素，如果它们的顺序不符合要求，则交换它们的位置。
经过多轮的比较和交换，最小值会逐渐冒泡到前面。
测试结果显示，冒泡排序在排序1000个随机数时，平均执行时间为0.981秒，比较次数为499500次。
从执行时间和比较次数来看，冒泡排序的性能较差，对于大规模数据的排序不适用。
3.2 插入排序插入排序是一种简单但有效的排序算法，其基本思想是将一个待排序的元素插入到已排序的子数组中的正确位置。
通过不断将元素插入到正确的位置，最终得到排序好的数组。
测试结果显示，插入排序在排序1000个随机数时，平均执行时间为0.892秒，比较次数为249500次。
插入排序的性能较好，因为其内层循环的比较次数与待排序数组的有序程度相关，对于近乎有序的数组排序效果更好。
3.3 选择排序选择排序是一种简单但低效的排序算法，其基本思想是在待排序的数组中选择最小的元素，将其放到已排序数组的末尾。
通过多次选择和交换操作，最终得到排序好的数组。
测试结果显示，选择排序在排序1000个随机数时，平均执行时间为4.512秒，比较次数为499500次。
第1篇一、实验目的1. 理解快速排序算法的基本原理和实现方法。
2. 掌握快速排序算法的时间复杂度和空间复杂度分析。
3. 通过实验验证快速排序算法的效率。
4. 提高编程能力和算法设计能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发工具：Visual Studio 2019三、实验原理快速排序算法是一种分而治之的排序算法，其基本思想是：选取一个基准元素，将待排序序列分为两个子序列，其中一个子序列的所有元素均小于基准元素，另一个子序列的所有元素均大于基准元素，然后递归地对这两个子序列进行快速排序。
快速排序算法的时间复杂度主要取决于基准元素的选取和划分过程。
在平均情况下，快速排序的时间复杂度为O(nlogn)，但在最坏情况下，时间复杂度会退化到O(n^2)。
四、实验内容1. 快速排序算法的代码实现2. 快速排序算法的时间复杂度分析3. 快速排序算法的效率验证五、实验步骤1. 设计快速排序算法的C++代码实现，包括以下功能：- 选取基准元素- 划分序列- 递归排序2. 编写主函数，用于生成随机数组和测试快速排序算法。
3. 分析快速排序算法的时间复杂度。
4. 对不同规模的数据集进行测试，验证快速排序算法的效率。
六、实验结果与分析1. 快速排序算法的代码实现```cppinclude <iostream>include <vector>include <cstdlib>include <ctime>using namespace std;// 生成随机数组void generateRandomArray(vector<int>& arr, int n) {srand((unsigned)time(0));for (int i = 0; i < n; ++i) {arr.push_back(rand() % 1000);}}// 快速排序void quickSort(vector<int>& arr, int left, int right) { if (left >= right) {return;}int i = left;int j = right;int pivot = arr[(left + right) / 2]; // 选取中间元素作为基准 while (i <= j) {while (arr[i] < pivot) {i++;}while (arr[j] > pivot) {j--;}if (i <= j) {swap(arr[i], arr[j]);i++;j--;}}quickSort(arr, left, j);quickSort(arr, i, right);}int main() {int n = 10000; // 测试数据规模vector<int> arr;generateRandomArray(arr, n);clock_t start = clock();quickSort(arr, 0, n - 1);clock_t end = clock();cout << "排序用时：" << double(end - start) / CLOCKS_PER_SEC << "秒" << endl;return 0;}```2. 快速排序算法的时间复杂度分析根据实验结果，快速排序算法在平均情况下的时间复杂度为O(nlogn)，在最坏情况下的时间复杂度为O(n^2)。
实验一分治与递归（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容掌握递归算法的概念和基本思想，分析并掌握“整数划分”问题的递归算法。
三、实验题任意输入一个整数，输出结果能够用递归方法实现整数的划分。
四、程序代码五、实验结果首先按照提示输入数字：按回车键，得到此数划分的个数：此时您可以接着计算另一个数的划分个数：若要退出，请输入一个小于等于零的数：六、结果分析及程序功能经过和其它同学的实验数据对比，初步认定此程序基本正确，然而不足之处是只能得到划分的个数，而不能列出每个划分的详细情况。
一、实验目的与要求1、掌握棋盘覆盖问题的算法；2、初步掌握分治算法二、实验题盘覆盖问题：在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
三、程序代码四、实验结果按照提示输入特殊方格的行号和列号（起始行列号为0）：按回车键，得到一个矩阵，数字相同区域为一个L型骨牌覆盖：五、结果分析及程序功能得到的16*16棋盘覆盖结果正确，此程序的不足之处：只能设定特殊方格的行列号，而不能设定棋盘的大小。
实验二动态规划算法(4学时)一、实验目的与要求1、熟悉最长公共子序列问题的算法；2、初步掌握动态规划算法；二、实验题若给定序列X={x1,x2,…,xm}，则另一序列Z={z1,z2,…,zk}，是X的子序列是指存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。
例如，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。
给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。
算法设计的实验报告1. 引言算法设计是计算机科学与技术领域的核心内容之一。
通过设计有效的算法，可以解决各种实际问题，提高计算机程序的性能，并优化资源利用。
本实验旨在通过实际案例，展示算法设计的过程及其在实际应用中的重要性。
2. 实验背景在本实验中，我们以图搜索算法为例，着重介绍了深度优先搜索（DFS）和广度优先搜索（BFS）两种经典的图搜索算法。
图搜索算法是图论中的重要概念，应用广泛，例如路径规划、迷宫问题、图像分割等领域。
通过比较两种算法的性能和应用场景，我们可以更好地理解算法设计的意义。
3. 实验目的1. 了解深度优先搜索和广度优先搜索两种常见的图搜索算法；2. 分析两种算法的优缺点和适用场景；3. 通过实际案例，比较两种算法在不同情况下的性能。
4. 实验方法本实验采用Python语言实现DFS和BFS算法，并通过相同的测试用例对两种算法进行评估。
4.1 深度优先搜索算法（DFS）深度优先搜索算法是一种遍历图的方法，其基本思想是从起始节点出发，不断向下搜索，直到找到目标节点或无法继续下去为止。
具体实现过程如下：1. 将起始节点入栈；2. 判断栈是否为空，若为空则搜索结束；3. 弹出栈顶节点，判断是否为目标节点，若是，则搜索成功，返回结果；4. 若不是目标节点，则将该节点的未访问过的相邻节点入栈；5. 重复步骤2至步骤4，直到找到目标节点或栈为空。
4.2 广度优先搜索算法（BFS）广度优先搜索算法是一种逐层遍历图的方法，其基本思想是从起始节点开始，先访问其所有相邻节点，再逐层向外扩展。
具体实现过程如下：1. 将起始节点入队；2. 判断队列是否为空，若为空则搜索结束；3. 出队一个节点，判断是否为目标节点，若是，则搜索成功，返回结果；4. 若不是目标节点，则将该节点的未访问过的相邻节点入队；5. 重复步骤2至步骤4，直到找到目标节点或队列为空。
5. 实验结果与分析我们通过使用DFS和BFS算法解决迷宫问题进行测试，并比较了两种算法的性能。
第1篇一、实验目的本次实验旨在深入理解并掌握裁剪算法的基本原理，通过编程实现Cohen-Sutherland算法和Liang-Barsky算法，对图形进行窗口裁剪，从而提高图形处理效率，优化显示效果。
二、实验环境1. 开发环境：Visual Studio 20192. 编程语言：C++3. 图形库：OpenGL三、实验内容1. 理解裁剪算法的基本原理；2. 实现Cohen-Sutherland算法；3. 实现Liang-Barsky算法；4. 对图形进行窗口裁剪，并展示裁剪效果。
四、实验过程1. 理解裁剪算法的基本原理裁剪算法是计算机图形学中的一个重要技术，用于将一个图形或图像中不需要的部分去除，只保留需要的部分。
常见的裁剪算法有Cohen-Sutherland算法、Liang-Barsky算法等。
Cohen-Sutherland算法是一种编码线段裁剪算法，通过将线段端点相对于窗口的位置进行编码，判断线段是否与窗口相交，从而实现裁剪。
Liang-Barsky算法是一种参数化线段裁剪算法，通过计算线段参数，判断线段是否与窗口相交，从而实现裁剪。
2. 实现Cohen-Sutherland算法（1）定义窗口边界首先，定义窗口边界，包括左边界、右边界、上边界和下边界。
（2）编码线段端点将线段端点相对于窗口的位置进行编码，编码规则如下：- 如果端点在窗口内，则编码为0；- 如果端点在窗口左侧，则编码为1；- 如果端点在窗口右侧，则编码为2；- 如果端点在窗口上方，则编码为4；- 如果端点在窗口下方，则编码为8。
（3）判断线段是否与窗口相交将线段两端点的编码进行异或运算，如果结果为0，则线段与窗口相交；否则，线段与窗口不相交。
（4）裁剪线段如果线段与窗口相交，则根据端点编码，将线段分为两部分，分别进行裁剪。
3. 实现Liang-Barsky算法（1）定义窗口边界首先，定义窗口边界，包括左边界、右边界、上边界和下边界。
一、实验目的1. 理解算法设计的基本原理和方法。
2. 掌握常见算法的设计技巧和优化策略。
3. 培养编程实践能力，提高算法实现效率。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容本次实验主要涉及以下算法设计内容：1. 排序算法（冒泡排序、选择排序、插入排序）2. 查找算法（顺序查找、二分查找）3. 动态规划（斐波那契数列、背包问题）四、实验步骤1. 冒泡排序（1）设计冒泡排序算法，实现降序排列。
```pythondef bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] < arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]return arrarr = [64, 34, 25, 12, 22, 11, 90]print("降序排列：", bubble_sort(arr))```（2）分析冒泡排序的时间复杂度和空间复杂度。
时间复杂度：O(n^2)空间复杂度：O(1)2. 选择排序（1）设计选择排序算法，实现升序排列。
```pythondef selection_sort(arr):n = len(arr)for i in range(n):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i] return arrarr = [64, 34, 25, 12, 22, 11, 90]print("升序排列：", selection_sort(arr))```（2）分析选择排序的时间复杂度和空间复杂度。
算法设计与分析实验报告1. 引言本实验报告旨在介绍算法设计与分析的相关内容。
首先，我们将介绍算法设计的基本原则和步骤。
然后，我们将详细讨论算法分析的方法和技巧。
最后，我们将通过一个实例来演示算法设计与分析的过程。
2. 算法设计算法设计是解决问题的关键步骤之一。
它涉及确定问题的输入和输出，以及找到解决方案的具体步骤。
以下是算法设计的一般步骤：2.1 理解问题首先，我们需要全面理解给定问题的要求和约束。
这包括确定输入和输出的格式，以及问题的具体要求。
2.2 制定算法思路在理解问题后，我们需要制定解决问题的算法思路。
这涉及确定解决问题的高层次策略和步骤。
通常，我们使用流程图、伪代码等工具来表示算法思路。
2.3 编写算法代码在制定算法思路后，我们可以根据思路编写实际的算法代码。
这可能涉及选择适当的数据结构和算法，以及编写相应的代码来实现解决方案。
2.4 调试和测试编写算法代码后，我们需要进行调试和测试，以确保算法的正确性和可靠性。
这包括检查代码中可能存在的错误，并使用不同的测试样例来验证算法的正确性。
3. 算法分析算法分析是评估算法性能的过程。
它涉及确定算法的时间复杂度和空间复杂度，以及评估算法在不同输入情况下的执行效率。
3.1 时间复杂度时间复杂度是衡量算法执行时间随输入规模增长的速度。
常见的时间复杂度包括常数时间复杂度 O(1)、线性时间复杂度 O(n)、对数时间复杂度 O(log n)、平方时间复杂度 O(n^2) 等。
通过分析算法中的循环、递归等关键部分，可以确定算法的时间复杂度。
3.2 空间复杂度空间复杂度是衡量算法所需空间随输入规模增长的速度。
它通常用于评估算法对内存的使用情况。
常见的空间复杂度包括常数空间复杂度 O(1)、线性空间复杂度 O(n)、对数空间复杂度 O(log n) 等。
通过分析算法中的变量、数组、递归栈等关键部分，可以确定算法的空间复杂度。
3.3 执行效率评估除了时间复杂度和空间复杂度外，我们还可以通过实验和测试来评估算法的执行效率。
算法设计及实验报告实验报告1 递归算法一、实验目的掌握递归算法的基本思想；掌握该算法的时间复杂度分析；二、实验环境电脑一台，Turbo C 运行环境三、实验内容、步骤和结果分析以下是四个递归算法的应用例子：用C语言实现1.阶乘：main(){int i,k;scanf("%d\n",&i);k= factorial(i);printf("%d\n",k);}int factorial(int n){ int s;if(n==0) s=1;else s=n*factorial(n-1); //执行n-1次return s;}阶乘的递归式很快，是个线性时间，因此在最坏情况下时间复杂度为O(n)。
2.Fibonacci 数列：main(){int i,m;scanf("%d\n",&i);m=fb(i);printf("%d",m);}int fb(int n){int s;if(n<=1)return 1;else s=fb(n-1)+fb(n-2);return s;}Fibonacci数列则是T(n)=T(n-1)+T(n-2)+O(1)的操作，也就是T(n)=2T(n)+O(1),由递归方程式可以知道他的时间复杂度T(n)是O(2n)，该数列的规律就是不停的赋值，使用的内存空间也随着函数调用栈的增长而增长。
3.二分查找（分治法）#include<stdio.h>#define const 8main(){int a[]={0,1,2,3,4,5,6,7,8,9};int n=sizeof(a);int s;s=BinSearch(a,const,n);printf("suo cha de shu shi di %d ge",s);}BinSearch(int a[],int x,int n){int left,right,middle=0;left=0;right=n-1;whlie(left<=right){middle=(left+right)/2;if(x==a[middle]) return middle;if(x>a[middle]) left=middle+1;else right=middle-1;}return -1;}二分搜索算法利用了元素间的次序关系，采用分治策略，由上程序可知，每执行一次while循环，数组大小减少一半，因此在最坏情况下，while循环被执行了O（logn）次。
计算机算法设计与分析实验报告专业：软件技术学号：************姓名：覃立煜指导老师：***实验一：最长公共子序列问题一、实验目的与要求1、明确子序列公共子序列的概念2、最长公共子序列(Longest Common Subsequence,简称LCS) 的概念3、利用动态规划解决最长公共子序列问题二、实验题：问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。
令给定的字符序列X=“x0，x1，…，x m-1”，序列Y=“y0，y1，…，y k-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，i k-1>，使得对所有的j=0，1，…，k-1，有x ij=y j。
例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。
给定两个序列A和B，称序列Z是A和B的公共子序列，是指Z同是A和B的子序列。
问题要求已知两序列A和B的最长公共子序列。
三、实验代码#include<stdlib.h>#include<stdio.h>#include<string.h>#define Size 100void LCSLength(int m,int n,char *x,char *y,int c[Size][Size],int b[Size][Size]){ int i,j;for(i=1;i<=m+1;i++) c[i][0]=0;for(i=1;i<=n+1;i++) c[0][i]=0;for(i=1;i<=m+1;i++)for(j=1;j<=n+1;j++){ if(x[i]==y[j]){ c[i][j]=c[i-1][j-1]+1; b[i][j]=0; }else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j];b[i][j]=1; }else { c[i][j]=c[i][j-1];b[i][j]=2; }}}void LCS(int i,int j,char *x,int b[Size][Size]){ if(i==0||j==0) return;if(b[i][j]==0){ LCS(i-1,j-1,x,b);printf("%c",x[i]); }else if(b[i][j]==1) LCS(i-1,j,x,b);else LCS(i,j-1,x,b);}main(){ int m,n,i;int c[Size][Size],b[Size][Size];char x[Size],y[Size];printf("输入序列x的长度(小于100):");scanf("%d",&m);printf("输入序列y的长度(小于100):");scanf("%d",&n);i=1;printf("输入x的成员(不用空格,直接输入字符串):\n");while(i<m+2){ scanf("%c",&x[i]);if(x[i]!='\0') i++;}i=1;printf("输入y的成员(不用空格,直接输入字符串):\n");while(i<n+2){ scanf("%c",&y[i]);if(y[i]!='\0') i++;}LCSLength(m,n,x,y,c,b);printf("最长公共子序列:\n");LCS(m+1,n+1,x,b);printf("\n"); }四、实验结果实验二：0-1背包问题一、实验目的与要求1、明确0-1背包问题的概念2、利用动态规划解决0-1背包问题问题二、实验题：0-1背包问题(knapsack problem)，某商店有n个物品，第i个物品价值为vi，重量(或称权值)为wi，其中vi和wi为非负数, 背包的容量为W，W为一非负数。
一、实验目的1. 了解加密算法的基本原理和设计方法；2. 掌握加密算法的评估标准；3. 提高对加密算法的安全性分析和改进能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3. 开发工具：PyCharm三、实验内容1. 设计一个简单的加密算法；2. 对算法进行安全性分析；3. 改进算法，提高安全性。
四、实验步骤1. 设计加密算法（1）算法原理：采用异或（XOR）运算对明文进行加密，加密密钥为随机生成的密钥。
（2）算法流程：① 生成密钥：使用随机数生成器生成一个随机密钥；② 加密过程：将明文与密钥进行XOR运算，得到密文；③ 解密过程：将密文与密钥进行XOR运算，得到明文。
2. 算法安全性分析（1）密钥安全性：加密密钥需要保密，否则攻击者可以轻易破解密文；（2）算法复杂性：算法需要具有较低的计算复杂度，以适应实际应用；（3）抗攻击能力：算法需要具备较强的抗攻击能力，包括穷举攻击、暴力破解等。
3. 改进算法（1）密钥生成：采用更复杂的密钥生成方法，如基于密码学算法的密钥生成；（2）加密模式：采用多种加密模式，如CBC、CFB等，提高加密效果；（3）加密轮数：增加加密轮数，提高加密强度；（4）密钥扩展：使用密钥扩展算法，如密钥派生函数，提高密钥安全性。
五、实验结果与分析1. 实验结果（1）加密算法实现：完成加密算法的设计和实现；（2）安全性分析：对加密算法进行安全性分析，发现存在一定的安全隐患；（3）改进算法：根据安全性分析结果，对加密算法进行改进，提高安全性。
2. 实验分析（1）加密算法的密钥安全性较好，但密钥生成方法较为简单，容易受到攻击；（2）加密算法的计算复杂度较低，适合实际应用；（3）加密算法的抗攻击能力较弱，容易受到穷举攻击和暴力破解。
六、实验结论1. 通过本次实验，掌握了加密算法的基本原理和设计方法；2. 了解加密算法的评估标准，能够对加密算法进行安全性分析；3. 提高了加密算法的安全性分析和改进能力，为后续研究奠定了基础。
深圳大学实验报告课程名称计算机基础项目名称算法设计工具学院专业指导教师报告人学号实验时间 2016.12.01 提交时间 2016.12.08教务处制一、实验目的与要求1．加深对算法设计和流程图的认识和理解；2．掌握算法设计工具Raptor的基本工作环境；3．掌握顺序结构、选择结构和循环结构的设计方法；4．掌握Raptor的子图和子程序设计方法。
二、实验内容与方法1.Raptor的工作环境2.控制结构（1）顺序结构案例一（2）选择结构案例2（3）循环结构案例33.子图和子程序案例44.练习题三、实验步骤与过程1.Raptor的工作环境1）Raptor的下载与安装在Internet上查找Raptor4.0.5.0003汉化版并下载，或访问Raptor官网（http：///）下载，按照Raptor汉化版安装向导的说明进行安装即可。
2）Raptor的窗口组成启动Windows系统后，选择“开始”→“所有程序”→“Raptor汉化版”命令，或双击桌面上的Raptor快捷图标，打开Raptor的应用窗口，如图1所示。
图1（1） 标题栏。
标题栏位于Raptor 窗口的顶部，显示该软件的图标，应用程序名称（Raptor 汉化版）以及当前正在处理的Raptor 的文件名。
标题栏最左端是Raptor 图标，单击该图标可以打开该软件的控制菜单，包括“还原”、“移动”、“移动”、“大小”、“最大化”、“最小化”和“关闭”等命令。
右边的三个按钮分别是“最小化”按钮、“最大化”/ “还原”按钮和“关闭”按钮。
（2） 菜单栏。
菜单栏位于标题栏的下方，包括“文件”、“编辑”、“比例”、“视图”、“运行”、“模式”、“画笔”、“窗口”、“生成”、“帮助”等10个菜单选项。
单击每一个菜单选项都会激活一个下拉菜单，列出有关此项功能的具体操作命令。
其中，“模式”菜单选项包含“初级”、“中级”、和“面向对象”3种模式。
（3） 工具栏。
工具栏位于菜单栏的下方，显示常用的Raptor 命令选项，用于快速启动这些应用，如“新建”、“打开”、“保存”、“运行”、“单步运行”以及“画笔”等。
（4） 符号区。
Raptor 有6种基本符号，每个符号代表一个特定的语句类型。
各类语句的功能如下。
① 赋值语句：用于各类运算以更改变量的值。
② 调用语句：用于调用Raptor 内置过程、子图和子程序。
③ 输入语句：允许用户输入数据，并将数据赋值给一个变量。
④ 输出语句：用于显示变量的值或保存到文件中。
⑤ 选择语句：经过条件判断后选择两条路径之一，并继续执行。
⑥ 循环语句：允许重复执行一个或多个语句，知道某些条件为真值。
符号区 标题栏 菜单栏 工具栏工作区（5）工作区。
工作区就是编制流程图的地方，用于显示当前编辑的程序。
初级模式下，右击main程序可建立子图或子程序。
（6）主控台。
在Raptor中，当输出语句执行时，会将数据输出到“主控台”窗口上。
每当程序运行结束时，在主控台上均会显示程序执行了多少条语句。
Raptor的“主控台”窗口如图2所示。
图2 Raptor的“主控台”窗口退出Raptor的方法有多种，常用的方法是在Raptor应用程序窗口中选择“文件”→“退出”命令，或直接单击Raptor应用程序窗口上标题栏右端的“关闭”按钮。
2.控制结构编写程序的重要工作之一就是控制语句的执行流程，控制结构含有3种基本类型，它们是顺序结构、选择结构和循环结构。
1)顺序结构顺序结构是最简单的程序构造，它把每条语句按顺序排列，执行时程序从开始（Start）语句顺序执行到结束（End）语句，箭头连接着语句并指示程序的执行方向。
案例1已知某圆的半径radius，求该圆的面积Area。
首先确定计算圆的面积公式：Area=pi*radius*radius然后在Raptor中编制相应的流程图，如图3所示。
图3 计算圆的面积其运行结果如图4图4注意：在Raptor中目前没有提供为用户定义常量的功能，而只是在系统内部定义了若干符号来表示常用的数值型常数。
当用户需要相应的值时，可直接使用代表这些常数的符号（这些符号也被称为保留字，保留字不可以再作为变量或者子图、子程序的名字）。
圆周率pi被定义为3.1416（Raptor默认精度为4位）。
2）选择结构很多情况下，仅使用顺序结构进行程序控制是无法得到针对现实世界问题的解决方案的。
有时需要根据某些条件是否满足来决定程序执行的方向，或者从给定的两种操作中选择其一，这就是选择结构要解决的问题。
选择语句可以使程序根据数据的当前状态选择两条可以选择的路径中一条继续执行。
案例2已知某圆的半径radius，求该圆的面积Area。
如果输入圆的半径radius是负数，那就没有意义了。
请设计程序，当输入的半径radius为负数时，输出错误提示信息。
分析题目可知，当输入半径radius之后，如果半径radius小于零，则输出相应的错误提示信息：如果半径不小于零，则进行相应半径radius的圆面积计算。
根据数据当前状态选择两条可以选择的路径中的一条继续执行，显然要用到选择结构。
在Raptor中编制相应的流程图，如图5图5 计算圆的面积当输入半径radius小于零的时候，得到运行结果如下：当输入半径radius不小于零的时候，得到运行结果如下：3）循环结构循环结构就是反复执行某段程序，直到某种条件满足时才结束执行的控制结构。
一个循环语句允许重复执行一个或多个语句，直到某种条件为真。
控制循环体执行次数的方法有以下两种。
（1）采用计数器方法：设置一个计数器，通过判断计数器的数值来控制循环体是否继续进行。
（2）采用“哨兵法”：这种方法在“事先不知道要循环多少次”的情况下特别有效。
通过“对数据内容的判断”来控制循环是否继续。
哨兵法的实现：在被处理数据序列的尾部安放一个“哨兵”——即事先知道的数据。
所以，每次循环体执行时，都会通过判断哨兵是否出现来控制循环体是否继续进行，一旦发现“哨兵”，则结束循环体的执行。
案例3 接着案例2的问题，如果要在一个程序中多次进行半径radius 的输入并计算圆的面积Area，该如何实现？题目要求多次进行半径radius的输入并计算圆的面积Area，因此重复执行某段程序，直到某种条件满足时才结束该段程序执行，显然，使用循环结构较为合适。
考虑到有两种循环的情况：第一，事先知道有多少组数据要进行测试；第二，事先不知道有多少组数据要测试。
因此，通过两种方式来控制循环的条件，从而实现程序求解问题。
（1）事先知道有多少组数据要进行测试。
可以通过输入要测试数据的组数来控制循环，在Raptor中编制相应的流程图，如图6所示。
图6 计算圆的面积（计数法）按照提示信息输入待测试的数据组数为2，接着输入两个半径radius的值为10和100，运行结果如图7：图7（2）事先不知道有多少组数据要测试，这种情况下，可以利用“哨兵法”，即在要测试的最后一组数据后边做上标记，像“哨兵”一样来提示循环的结束。
这里用0来作为“哨兵”，即当输入的半径radius等于0时，循环结束。
在Raptor中编制相应的流程图，如图8所示按照提示信息依次输入2、3/10/0，得到的运行结果如下：图8 计算圆的面积3．子图和子程序Raptor模式有初级、中级和面向对象3种形式可供选择。
其中，初级模式和中级模式没有太大的查边，唯一不同的地方就是初级模式中的调用语句可以调用语句进行调用，子图调用时无须提供参数，因为所有的Raptor子图共享所有的变量。
而子程序相当于Raptor的内置过程，必须提供完成任务所需要的数据，也就是所谓的参数。
Raptor的子图和子程序之间的最大差别在于不能给子图传递参数，子图也不会返回任何值。
所有Raptor子图共享所有的变量，而子程序的所有变量“自成系统”。
案例4输入两个数a和b，交换之后输出。
在Raptor中编制相应的流程图，main子图的实现如图9所示，swap子图的实现如图10所示。
图10 判断最大数的main子图图11 判断最大数的main子图图12 判断最大数的Maxximum_value子程序其运行结果如下：子程序如同一个加工厂，输入原材料，然后按照设计要求，输出所需要的产品。
子程序（Maxximum_value）的原材料就是一些变量，这里是指in：m和in：n，这是子程序待处理的数据，子程序（Maxximum_value）的产品也是变量，这里是指out：max_number，用于向调用它的程序返回处理结果。
其中in和out代表子程序的输入和输出参数。
子程序定义界面上的接口参数称为“形式参数”，如图13.从中可以看出，Raptor中的子程序参数不得超过6个，任何参数只要是有in（输入参数）的属性，那么在程序调用该子程序之前，必须准备好这个参数，即已经初始化且有数值。
子程序运行中的所有变量都“自成系统”，与调用它的程序没有关系。
调用它的程序只是通过调用参数与它交接“原材料”（待处理的数据）和“所需产品”（已处理的数据）。
子程序的所有变量在子程序运行过程中存在，运行结束后，除了传回调用程序的参数，所有变量立即释放或删除。
图13Maxximum_value子程序定义界面练习题1.输入三角形的三条边长，求三角形的面积。
输入a=3，b=2，c=1，运算结果如下输入a=20，b=21，c=19，运算结果如下2.求方程ax²+bx+c=0在实数域上的根。
a、b、c由键盘输入。
输入a=0时，运算结果如图:输入a=1，b=0，c=1时，运算结果如图：输入a=1，b=0，c=-1时，运算结果如图：输入a=1，b=-2，c=1时，运算结果如图：3.设计程序，判断输入的数是否为素数，是则输出“Yes”，否则输出“No”如图输入n=177，运行结果如下：4.写一个子图或子程序，用递归方法求Fibonacci数列的第n项，n由键盘输入。
输入n=3，运行结果如下：四、实验结论或体会刚开始对Raptor的算法一无所知，不过通过这次实验开始喜欢算法了。
我们平时遇到的一些难以解决的题目，都可以用算法来解决。
而且，设计算法也是一种锻炼逻辑思维的好途径，同时也能让我养成检查，寻找最佳优化方案的习惯。
在完成这次实验报告的过程中，也会遇到一些找不出原因的问题，幸亏最后都解决了。
总而言之，这次实验让我有很大的进步。
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
