下载文档原格式
一、实验背景随着计算机科学技术的不断发展，算法作为计算机科学的核心内容之一，其重要性日益凸显。
为了验证和评估不同算法的性能，我们进行了一系列算法实验，通过对比分析实验结果，以期为后续算法研究和优化提供参考。
二、实验方法本次实验选取了三种常见的算法：快速排序、归并排序和插入排序，分别对随机生成的数据集进行排序操作。
实验数据集的大小分为10000、20000、30000、40000和50000五个级别，以验证算法在不同数据量下的性能表现。
实验过程中，我们使用Python编程语言实现三种算法，并记录每种算法的运行时间。
同时，为了确保实验结果的准确性，我们对每种算法进行了多次运行，并取平均值作为最终结果。
三、实验结果1. 快速排序快速排序是一种高效的排序算法，其平均时间复杂度为O(nlogn)。
从实验结果来看，快速排序在所有数据量级别下均表现出较好的性能。
在数据量较小的10000和20000级别，快速排序的运行时间分别为0.05秒和0.1秒；而在数据量较大的40000和50000级别，运行时间分别为0.8秒和1.2秒。
总体来看，快速排序在各个数据量级别下的运行时间均保持在较低水平。
2. 归并排序归并排序是一种稳定的排序算法，其时间复杂度也为O(nlogn)。
实验结果显示，归并排序在数据量较小的10000和20000级别下的运行时间分别为0.15秒和0.25秒，而在数据量较大的40000和50000级别，运行时间分别为1.5秒和2.5秒。
与快速排序相比，归并排序在数据量较小的情况下性能稍逊一筹，但在数据量较大时，其运行时间仍然保持在较低水平。
3. 插入排序插入排序是一种简单易实现的排序算法，但其时间复杂度为O(n^2)。
实验结果显示，插入排序在数据量较小的10000和20000级别下的运行时间分别为0.3秒和0.6秒，而在数据量较大的40000和50000级别，运行时间分别为8秒和15秒。
可以看出，随着数据量的增加，插入排序的性能明显下降。
一、实验目的本次实验旨在通过对比分析几种常用排序算法的性能，深入了解各种算法在不同数据规模和不同数据分布情况下的时间复杂度和空间复杂度，为实际应用中算法的选择提供参考。
二、实验环境- 操作系统：Windows 10- 编程语言：C++- 编译器：Visual Studio 2019- 测试数据：随机生成的正整数序列三、实验内容本次实验主要对比分析了以下几种排序算法：1. 冒泡排序（Bubble Sort）2. 选择排序（Selection Sort）3. 插入排序（Insertion Sort）4. 快速排序（Quick Sort）5. 归并排序（Merge Sort）6. 希尔排序（Shell Sort）四、实验方法1. 对每种排序算法，编写相应的C++代码实现。
2. 生成不同规模（1000、5000、10000、50000、100000）的随机正整数序列作为测试数据。
3. 对每种排序算法，分别测试其时间复杂度和空间复杂度。
4. 对比分析不同算法在不同数据规模和不同数据分布情况下的性能。
五、实验结果与分析1. 时间复杂度（1）冒泡排序、选择排序和插入排序的平均时间复杂度均为O(n^2)，在数据规模较大时性能较差。
（2）快速排序和归并排序的平均时间复杂度均为O(nlogn)，在数据规模较大时性能较好。
（3）希尔排序的平均时间复杂度为O(n^(3/2))，在数据规模较大时性能优于冒泡排序、选择排序和插入排序，但不如快速排序和归并排序。
2. 空间复杂度（1）冒泡排序、选择排序和插入排序的空间复杂度均为O(1)，属于原地排序算法。
（2）快速排序和归并排序的空间复杂度均为O(n)，需要额外的空间来存储临时数组。
（3）希尔排序的空间复杂度也为O(1)，属于原地排序算法。
3. 不同数据分布情况下的性能（1）对于基本有序的数据，快速排序和归并排序的性能会受到影响，此时希尔排序的性能较好。
（2）对于含有大量重复元素的数据，快速排序的性能会受到影响，此时插入排序的性能较好。
算法实验报告算法实验报告引言：算法是计算机科学的核心内容之一，它是解决问题的方法和步骤的描述。
算法的设计和分析是计算机科学与工程中的重要研究方向之一。
本实验旨在通过对算法的实际应用和实验验证，深入理解算法的性能和效果。
实验一：排序算法的比较在本实验中，我们将比较三种常见的排序算法：冒泡排序、插入排序和快速排序。
我们将通过对不同规模的随机数组进行排序，并记录每种算法所需的时间和比较次数，以评估它们的性能。
实验结果显示，快速排序是最快的排序算法，其时间复杂度为O(nlogn)，比较次数也相对较少。
插入排序的时间复杂度为O(n^2)，比较次数较多，但对于小规模的数组排序效果较好。
而冒泡排序的时间复杂度也为O(n^2)，但比较次数更多，效率相对较低。
实验二：图的最短路径算法在图的最短路径问题中，我们将比较Dijkstra算法和Floyd-Warshall算法的效率和准确性。
我们将使用一个带权有向图，并计算从一个顶点到其他所有顶点的最短路径。
实验结果表明，Dijkstra算法适用于单源最短路径问题，其时间复杂度为O(V^2)，其中V为顶点数。
而Floyd-Warshall算法适用于多源最短路径问题，其时间复杂度为O(V^3)。
两种算法在准确性上没有明显差异，但在处理大规模图时，Floyd-Warshall算法的效率较低。
实验三：动态规划算法动态规划是一种通过将问题分解成子问题并记录子问题的解来解决复杂问题的方法。
在本实验中，我们将比较两种动态规划算法：0-1背包问题和最长公共子序列问题。
实验结果显示，0-1背包问题的动态规划算法可以有效地找到最优解，其时间复杂度为O(nW)，其中n为物品个数，W为背包容量。
最长公共子序列问题的动态规划算法可以找到两个序列的最长公共子序列，其时间复杂度为O(mn)，其中m和n分别为两个序列的长度。
结论：通过本次实验，我们对不同算法的性能和效果有了更深入的了解。
排序算法中，快速排序是最快且效率最高的；在图的最短路径问题中，Dijkstra算法和Floyd-Warshall算法分别适用于不同的场景；动态规划算法可以解决复杂的问题，并找到最优解。
一、实验目的1. 掌握阶乘算法的基本原理和实现方法；2. 分析不同阶乘算法的效率；3. 提高编程能力和算法优化能力。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 阶乘算法实现2. 性能分析四、实验步骤1. 阶乘算法实现（1）递归法实现阶乘```pythondef factorial_recursive(n):if n == 0 or n == 1:return 1else:return n factorial_recursive(n - 1) ```（2）迭代法实现阶乘```pythondef factorial_iterative(n):result = 1for i in range(1, n + 1):result = ireturn result```2. 性能分析（1）测试数据为了测试不同阶乘算法的性能，我们选取以下测试数据：- 较小数值：n = 5- 较大数值：n = 10- 极大数值：n = 20（2）性能测试```pythonimport timedef test_factorial():n_list = [5, 10, 20]for n in n_list:start_time = time.time()factorial_recursive(n)recursive_time = time.time() - start_time start_time = time.time()factorial_iterative(n)iterative_time = time.time() - start_timeprint(f"n = {n}:")print(f"递归法耗时：{recursive_time:.6f}秒")print(f"迭代法耗时：{iterative_time:.6f}秒")print("")test_factorial()```五、实验结果与分析1. 实验结果（1）n = 5递归法耗时：0.000002秒迭代法耗时：0.000001秒（2）n = 10递归法耗时：0.000003秒迭代法耗时：0.000001秒（3）n = 20递归法耗时：0.000016秒迭代法耗时：0.000002秒2. 分析（1）从实验结果可以看出，迭代法在计算阶乘时比递归法具有更高的效率。
第1篇一、实验目的1. 了解现代密码学的基本原理和数论基础知识；2. 掌握非对称密码体制的著名代表RSA加密算法的工作原理和流程；3. 设计实现一个简单的密钥系统；4. 掌握常用加密算法AES和DES的原理及实现。
二、实验内容1. RSA加密算法实验2. AES加密算法实验3. DES加密算法实验三、实验原理1. RSA加密算法RSA算法是一种非对称加密算法，由罗纳德·李维斯特、阿迪·沙米尔和伦纳德·阿德曼三位密码学家于1977年提出。
其基本原理是选择两个大质数p和q，计算它们的乘积n=pq，并计算欧拉函数φ(n)=(p-1)(q-1)。
选择一个整数e，满足1<e<φ(n)且e与φ(n)互质。
计算e关于φ(n)的模逆元d。
公开密钥为(e,n)，私有密钥为(d,n)。
加密过程为C=Me mod n，解密过程为M=Cd mod n。
2. AES加密算法AES（Advanced Encryption Standard）是一种分组加密算法，采用128位分组大小和128、192或256位密钥长度。
AES算法主要分为四个阶段：初始轮、密钥扩展、中间轮和最终轮。
每个轮包括字节替换、行移位、列混淆和轮密钥加。
3. DES加密算法DES（Data Encryption Standard）是一种分组加密算法，采用64位分组大小和56位密钥长度。
DES算法主要分为16轮，每轮包括置换、置换-置换、S盒替换和密钥加。
四、实验步骤及内容1. RSA加密算法实验（1）选择两个大质数p和q，计算n=pq和φ(n)=(p-1)(q-1)；（2）选择一个整数e，满足1<e<φ(n)且e与φ(n)互质，计算e关于φ(n)的模逆元d；（3）生成公开密钥(e,n)和私有密钥(d,n)；（4）用公钥对明文进行加密，用私钥对密文进行解密。
2. AES加密算法实验（1）选择一个128、192或256位密钥；（2）初始化初始轮密钥；（3）进行16轮加密操作，包括字节替换、行移位、列混淆和轮密钥加；（4）输出加密后的密文。
第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。
为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。
二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。
1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。
（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。
- 对每种算法进行时间复杂度和空间复杂度的分析。
- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。
（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。
- 编写三种排序算法的代码。
- 分析代码的时间复杂度和空间复杂度。
- 编写测试程序，生成随机测试数据，测试三种算法的性能。
- 比较三种算法的运行时间和内存占用。
2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。
（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。
- 分析贪心算法的正确性，并证明其最优性。
（3）实验步骤：- 分析活动选择问题的贪心策略。
- 编写贪心算法的代码。
- 分析贪心算法的正确性，并证明其最优性。
- 编写测试程序，验证贪心算法的正确性。
3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。
（2）实验内容：- 实现一个动态规划算法问题，如背包问题。
- 分析动态规划算法的正确性，并证明其最优性。
（3）实验步骤：- 分析背包问题的动态规划策略。
- 编写动态规划算法的代码。
- 分析动态规划算法的正确性，并证明其最优性。
- 编写测试程序，验证动态规划算法的正确性。
三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。
算法与分析实验报告一、引言算法是现代计算机科学中的核心概念，通过合理设计的算法可以解决复杂的问题，并提高计算机程序的执行效率。
本次实验旨在通过实际操作和数据统计，对比分析不同算法的执行效率，探究不同算法对于解决特定问题的适用性和优劣之处。
二、实验内容本次实验涉及两个经典的算法问题：排序和搜索。
具体实验内容如下：1. 排序算法- 冒泡排序- 插入排序- 快速排序2. 搜索算法- 顺序搜索- 二分搜索为了对比不同算法的执行效率，我们需要设计合适的测试用例并记录程序执行时间进行比较。
实验中，我们将使用随机生成的整数数组作为排序和搜索的测试数据，并统计执行时间。
三、实验步骤1. 算法实现与优化- 实现冒泡排序、插入排序和快速排序算法，并对算法进行优化，提高执行效率。
- 实现顺序搜索和二分搜索算法。
2. 数据生成- 设计随机整数数组生成函数，生成不同大小的测试数据。
3. 实验设计- 设计实验方案，包括测试数据的规模、重复次数等。
4. 实验执行与数据收集- 使用不同算法对随机整数数组进行排序和搜索操作，记录执行时间。
- 多次重复同样的操作，取平均值以减小误差。
5. 数据分析与结果展示- 将实验收集到的数据进行分析，并展示在数据表格或图表中。
四、实验结果根据实验数据的收集与分析，我们得到以下结果：1. 排序算法的比较- 冒泡排序：平均执行时间较长，不适用于大规模数据排序。
- 插入排序：执行效率一般，在中等规模数据排序中表现良好。
- 快速排序：执行效率最高，适用于大规模数据排序。
2. 搜索算法的比较- 顺序搜索：执行时间与数据规模成线性关系，适用于小规模数据搜索。
- 二分搜索：执行时间与数据规模呈对数关系，适用于大规模有序数据搜索。
实验结果表明，不同算法适用于不同规模和类型的问题。
正确选择和使用算法可以显著提高程序的执行效率和性能。
五、实验总结通过本次实验，我们深入了解了不同算法的原理和特点，并通过实际操作和数据分析对算法进行了比较和评估。
第1篇一、实验背景聚类分析是数据挖掘中的一种重要技术，它将数据集划分成若干个类或簇，使得同一簇内的数据点具有较高的相似度，而不同簇之间的数据点则具有较低相似度。
本实验旨在通过实际操作，了解并掌握聚类分析的基本原理，并对比分析不同聚类算法的性能。
二、实验环境1. 操作系统：Windows 102. 软件环境：Python3.8、NumPy 1.19、Matplotlib 3.3.4、Scikit-learn0.24.03. 数据集：Iris数据集三、实验内容本实验主要对比分析以下聚类算法：1. K-means算法2. 聚类层次算法（Agglomerative Clustering）3. DBSCAN算法四、实验步骤1. K-means算法（1）导入Iris数据集，提取特征数据。
（2）使用Scikit-learn库中的KMeans类进行聚类，设置聚类数为3。
（3）计算聚类中心，并计算每个样本到聚类中心的距离。
（4）绘制聚类结果图。
2. 聚类层次算法（1）导入Iris数据集，提取特征数据。
（2）使用Scikit-learn库中的AgglomerativeClustering类进行聚类，设置链接方法为'ward'。
（3）计算聚类结果，并绘制树状图。
3. DBSCAN算法（1）导入Iris数据集，提取特征数据。
（2）使用Scikit-learn库中的DBSCAN类进行聚类，设置邻域半径为0.5，最小样本数为5。
（3）计算聚类结果，并绘制聚类结果图。
五、实验结果与分析1. K-means算法实验结果显示，K-means算法将Iris数据集划分为3个簇，每个簇包含3个样本。
从聚类结果图可以看出，K-means算法能够较好地将Iris数据集划分为3个簇，但存在一些噪声点。
2. 聚类层次算法聚类层次算法将Iris数据集划分为3个簇，与K-means算法的结果相同。
从树状图可以看出，聚类层次算法在聚类过程中形成了多个分支，说明该算法能够较好地处理不同簇之间的相似度。
第1篇一、实验目的本次实验旨在通过实现冒泡排序算法，加深对排序算法原理的理解，掌握冒泡排序的基本操作，并分析其性能特点。
二、实验内容1. 冒泡排序原理冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。
遍历数列的工作是重复地进行，直到没有再需要交换，也就是说该数列已经排序完成。
2. 实验步骤（1）设计一个冒泡排序函数，输入为待排序的数组，输出为排序后的数组。
（2）编写一个主函数，用于测试冒泡排序函数的正确性和性能。
（3）通过不同的数据规模和初始顺序，分析冒泡排序的性能特点。
3. 实验环境（1）编程语言：C语言（2）开发环境：Visual Studio Code（3）测试数据：随机生成的数组、有序数组、逆序数组三、实验过程1. 冒泡排序函数设计```cvoid bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n - 1; i++) {for (j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}```2. 主函数设计```cinclude <stdio.h>include <stdlib.h>include <time.h>int main() {int n;printf("请输入数组长度：");scanf("%d", &n);int arr = (int )malloc(n sizeof(int)); if (arr == NULL) {printf("内存分配失败\n");return 1;}// 生成随机数组srand((unsigned)time(NULL));for (int i = 0; i < n; i++) {arr[i] = rand() % 100;}// 冒泡排序bubbleSort(arr, n);// 打印排序结果printf("排序结果：\n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");// 释放内存free(arr);return 0;}```3. 性能分析（1）对于随机生成的数组，冒泡排序的平均性能较好，时间复杂度为O(n^2)。
一、实验目的本次实验旨在通过仿真实验，验证某算法在实际应用中的性能和效果，并对算法的优化进行初步探讨。
通过实验，深入了解算法的原理，分析其优缺点，为实际工程应用提供参考。
二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 仿真软件：MATLAB 2019b4. 硬件环境：****************************，16GB RAM三、实验内容1. 算法原理及描述2. 仿真实验设计3. 实验结果分析4. 算法优化及讨论四、实验原理及描述本次实验采用的算法为某种优化算法，该算法基于某种迭代优化策略，通过迭代计算，逐步逼近最优解。
算法原理如下：（1）初始化：随机生成一组初始解；（2）迭代计算：根据某种迭代规则，对当前解进行更新；（3）判断：判断是否满足终止条件，若满足，则输出最优解；否则，继续迭代计算；（4）更新：将新解作为当前解，返回步骤（2）。
五、仿真实验设计1. 实验数据：选取一组具有代表性的测试数据，包括输入数据和期望输出数据；2. 实验步骤：（1）导入实验数据；（2）调用算法进行仿真实验；（3）记录实验结果；（4）分析实验结果。
六、实验结果分析1. 实验结果展示（1）输入数据：[1, 2, 3, 4, 5]（2）期望输出：[1, 2, 3, 4, 5]（3）算法输出：[1, 2, 3, 4, 5]（4）误差分析：误差为0，说明算法输出与期望输出一致。
2. 性能分析（1）算法运行时间：0.001s（2）迭代次数：100次（3）算法收敛速度：较快3. 优缺点分析（1）优点：算法简单易实现，收敛速度快；（2）缺点：对初始解敏感，容易陷入局部最优。
七、算法优化及讨论1. 优化策略（1）改进初始解：采用某种方法生成更好的初始解，提高算法的鲁棒性；（2）调整迭代规则：优化迭代规则，使算法在迭代过程中更加稳定；（3）引入多种优化算法：结合多种优化算法，提高算法的适应性和全局搜索能力。
《算法设计与分析》上机实验报告一、分治与递归1、问题描述编写程序，实现线性时间内选择n个元素的中位数的算法。
并对于不同的n，测试平均时间效率。
2、问题分析本问题属于线性选择问题的一个特例，可以使用分治法进行求解。
其基本思想是模仿快速排序方法，对输入的数组进行划分，求出中位数所在的子数组，然后用递归的方法进行求解，最终可以求得问题的解。
3、算法设计将n个输入元素根据随机选择的基准划分成2个子数组，a[p:r]被划分成a[p:i]和a[i+1:r]两组，使得a[p:i]中每个元素都不大于a[i+1:r]中元素。
接着算法计算子数组a[p:i]中元素个数j，如果k<=j，则a[p:r]中第k个小元素落在子数组a[p:i]中元素均小于要找的第k小元素，因此要找的a[p:r]中第k小元素是a[i+1:r]中的第k-j小元素。
按照上述的方法递归的执行，直到当前数组中只剩下一个元素，就可以得到问题的解。
4、算法实现#include"iostream.h"#include"stdlib.h"#include"time.h"#include<sys/types.h>#include<sys/timeb.h>#include"windows.h"#include<stdio.h>int randomizedSel(int *,int ,int ,int );void main(){srand((unsigned int)time(NULL));_timeb time0,time1;int n;cout << "请输入数组的长度：";cin >> n;cout << "请输入数组的每一个数：" << endl;int *a=new int[n];for(int i=0;i<n;i++)cin >> a[i];DWORD stime=GetTickCount();_ftime(&time0);int result=randomizedSel(a,0,n-1,(n+1)/2);DWORD Etime=GetTickCount();_ftime(&time1);cout << "结果为：" << result << endl;cout << litm*litm*1000<<endl;cout<<Etime-stime<<endl;}void swap(int *a,int i,int j){int temp=a[i];a[i]=a[j];a[j]=temp;}int partition(int *a,int p,int r){int i=p,j=r+1;int x=a[p];while(1){while(a[++i]<x && i<r);while(a[--j]>x);if(i>=j) break;swap(a,i,j);}a[p]=a[j];a[j]=x;return j;}int randomizedpar(int *a,int p,int r){int i=rand()%(r-p+1)+p;swap(a,i,p);return partition(a,p,r);}int randomizedSel(int *a,int p,int r,int k){if(p == r)return a[p];int i=randomizedpar(a,p,r);int j=i-p+1;if(k<=j) return randomizedSel(a,p,i,k);else return randomizedSel(a,i+1,r,k-j);}5、运行结果运行结果如下图所示：经过测试，当输入的数组长度不大时，执行时间几乎为零，当输入数组很大时，执行时间随之增大，与数组长度成正相关。
二、动态规划1、问题描述实现0/1背包问题的求解算法。
2、问题分析可以将上述问题转化为以下的数学表达式的形式：求：i mi i x v ∑=1max ，满足以下的条件：⎪⎩⎪⎨⎧≤≤∈≤∑=n i x Cx w ii ni i 1},1,0{1记m （i ，j ）表示背包容量为j ，可选物品为i ，i+1，.....，n 时0-1背包问题的最优值，则可以得到如下的算式：⎩⎨⎧≤≤+≥+-++=i i i i w j j i m w j v w j i m j i m j i m 0),1(}),1(),,1(max{),( ⎩⎨⎧<≤>=nnw j 0 0w j ),(m n v j n 则m （1，c ）即为所求的最优值3、算法设计将问题分析中的m （i ，j ）用二维数组m[ ][ ]存储，则可以得到问题的求解。
4、算法实现#include <stdio.h> #include <stdlib.h> #include <iostream> using namespace std; int max(int x,int y);int main(int argc, char *argv[]) {//定义int n,c,w[105],v[105],m[105][105]; int i,j,jmax;cout<<"请输入物品的数量与背包容量:"<<endl; cin>>n>>c; //最后一层的计算cout<<"输入各个物品的重量："; for (i=1;i<=n;i++) cin>>w[i];cout<<"输入各个物品的价值："; for (i=1;i<=n ;i++)cin>>v[i];jmax=w[n-1]<c?w[n-1]:c;for(j=0;j<=jmax;j++)m[n][j]=0;for(j=w[n];j<=c;j++)m[n][j]=v[n];//中间的计算for(i=n-1;i>1;i--){jmax=w[i-1]<c?w[i-1]:c;for(j=0;j<=jmax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);}//第一层的计算m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);//输出cout<<"最优的背包价值为:" << m[1][c]<<endl;system("pause");return 0;}int max(int x,int y){int t;if(x>y)t=x;elset=y;return t;}5、运行结果执行结果如下图所示：三、贪心法1、问题描述给定n位整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。
对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
2、问题分析本题可以用贪心算法求解，由于左边的数比右边的数具有更大的位值，所以应该从左边开始遍历，当遇到一个右边的数大于左边的数时，删去右边的数，可以得到删除一个数时的最大数。
这样，通过多次这样的遍历，就可以的问题的解了。
3、算法设计算法对数组进行扫描遍历，当遇到第一个右边的数比左边的数大的时候，就把右边的数据删除，同时将后面的每一位数据按位向前移动一位，这样就完成了一次遍历。
执行上述步骤k次，将最终得到删除后的数组。
4、算法实现#include"iostream.h"#include"string.h"void greedy(char *,int);void main(){char number[30];int k;cout << "请输入一个正整数：";cin >> number;cout << "请输入删除的位数：";cin >> k;greedy(number,k);cout<< "删数后的结果为：" << number << endl;}void greedy(char *number,int k){for(int i=1;i<=k;i++){int j=0;while(number[j]){j++;if(number[j-1]<=number[j]) //若前一位小于后一位，则继续执行continue;while(number[j]) //若前一位大于后一位，则删除前一位，后面的数顺次前移一位{number[j-1]=number[j];j++;}number[j-1]=number[j];}}}5、运行结果执行结果如下图所示四、回溯/分支限界法1、问题描述某售货员要到若干城市去推销商品，已知各城市之间的路程（或运费）。
他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程（或总旅费）最小。
2、问题分析本问题可以使用回溯法进行求解，该问题的解空间书是一颗排列树，从树的根节点到任意叶子节点的路径定义了图中的一条周游路线。
用深度优先的方式对排列数进行遍历，添加剪枝函数减少遍历中的节点数。
3、算法设计在递归算法汇中，当i=n时，当前扩展节点是排列数的叶节点的父节点。
此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。
如果这两条边都存在，则找到一条旅行售货员的回路。
此时，算法还需判断这条回路的费用是否优于当前已找到的最有回路的费用bestc，如果是，则必须更新当前最优值bestc和当前最优解bestx。
当i<n时，当前扩展节点位于排列数的第i-1层。
图G中存在从顶点x[i-1]到顶点x[i]的边时，x[1:i]构成图G的一条路径，且当x[1:i]的费用小于当前最优值时，算法进入排列树的第i层，否则，将渐趋相应的子树。
