深圳大学算法设计与分析杨煊实验三

深圳大学实验报告课程名称：算法分析与复杂性理论实验项目名称：八皇后问题学院：计算机与软件学院专业：软件工程指导教师：杨烜报告人：学号：班级：15级软工学术型实验时间：2015-12-08实验报告提交时间：2015-12-09教务部制一．实验目的1.掌握选回溯法设计思想。

2.掌握八皇后问题的回溯法解法。

二．实验步骤与结果实验总体思路：根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。

测试数据模块主要调用判断模块进行判断，完成测试。

用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。

相应结果和过程如下所示（代码和结果如下图所示）。

回溯法的实现及实验结果：1、判断函数代码1：procedure BTrack_Queen(n)皇后问题 2.测试数据0.退出**"<<endl;cout<<"******************************************"<<endl;cin>>n;switch(n){case 0: cout<<"退出程序成功..."<<endl;return 0; //一个程序两个出口case 1: cout<<"八皇后问题的解为："<<endl;BackTrack_Queen(0);cout<<"共有"<<sum<<"个解"<<endl;break;case 2: cout<<"运行测试数据："<<endl;while(1) {cout<<"请输入要测试的数据："<<endl;for(int j=0;j<max;j++)cin>>queen[j];if(Judge(max)==1) cout<<"该数据是八皇后问题的解"<<endl;else cout<<"该数据不是八皇后问题的解"<<endl;}break;default: cout<<"输入非法，请重新输入！"<<endl;}}return 0;}注：MFC实现代码下载：若链接无效可加我百度云好友：123望月台456。

《算法设计与分析》实验报告实验一递归与分治策略应用基础学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期第九周一、实验目的1、理解递归的概念和分治法的基本思想2、了解适用递归与分治策略的问题类型，并能设计相应的分治策略算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：以下题目要求应用递归与分治策略设计解决方案，本次实验成绩按百分制计，完成各小题的得分如下，每小题要求算法描述准确且程序运行正确。

1、求n个元素的全排。

（30分）2、解决一个2k*2k的特殊棋牌上的L型骨牌覆盖问题。

（30分）3、设有n=2k个运动员要进行网球循环赛。

设计一个满足要求的比赛日程表。

（40分）提交结果：算法设计分析思路、源代码及其分析说明和测试运行报告。

三、设计分析四、算法描述及程序五、测试与分析六、实验总结与体会#include "iostream"using namespace std;#define N 100void Perm(int* list, int k, int m){if (k == m){for (int i=0; i<m; i++)cout << list[i] << " ";cout << endl;return;}else{for (int i=m; i<k; i++){swap(list[m], list[i]);Perm(list, k, m+1);swap(list[m], list[i]);}}}void swap(int a,int b){int temp;temp=a;a=b;b=temp;}int main(){int i,n;int a[N];cout<<"请输入排列数据总个数：";cin>>n;cout<<"请输入数据：";for(i=0;i<n;i++){cin>>a[i];}cout<<"该数据的全排列："<<endl;Perm(a,n,0);return 0;}《算法设计与分析》实验报告实验二递归与分治策略应用提高学号：**************姓名：*************班级：*************日期：2014-2015学年第1学期一、实验目的1、深入理解递归的概念和分治法的基本思想2、正确使用递归与分治策略设计相应的问题的算法3、掌握递归与分治算法时间空间复杂度分析，以及问题复杂性分析方法二、实验内容任务：从以下题目中任选一题完成，要求应用递归与分治策略设计解决方案。

《算法设计与分析》实验指导《算法分析与设计》实验指导 .1 实验一锦标赛问题 [实验目的] 1. 基本掌握分治算法的原理. 2. 能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1. 认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2. 设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有 n=2 k 个运动员要进行网球循环赛。

现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他 n-1 个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在 n-1 天内结束。

请按此要求将比赛日程表设计成有 n 行和 n-1 列的一个表。

在表中的第 i 行，第 j 列处填入第 i 个选手在第 j 天所遇到的选手。

其中 1≤i≤n，1≤j≤n-1。

[实验提示] 我们可以按分治策略将所有的选手分为两半，则 n 个选手的比赛日程表可以通过 n/2个选手的比赛日程表来决定。

递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。

这时只要让这两个选手进行比赛就可以了。

1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 2 1 4 3 6 7 8 5 3 4 1 2 7 8 5 6 1 2 3 4 3 2 1 8 5 6 7 1 2 3 4 5 6 7 8 1 4 3 2 1 2 1 4 3 6 5 8 7 2 1 4 3 1 2 3 4 1 2 7 8 5 6 3 2 1 4 2 1 4 3 2 1 8 7 6 5 4 3 2 1 （1）（2）（3）图 1 2 个、4 个和 8 个选手的比赛日程表图 1 所列出的正方形表（3）是 8 个选手的比赛日程表。

其中左上角与左下角的两小块分别为选手 1 至选手 4 和选手 5 至选手 8 前 3 天的比赛日程。

据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这2 样我们就分别安排好了选手 1 至选手 4 和选手 5 至选手 8 在后 4 天的比赛日程。

《算法设计与分析》课程实验教学大纲Design and Analysis of Computer Algorithm总学时 16 总学分 0.5 实验学时 16一、基本情况1. 课程性质：专业实践2. 设课方式：独立设课3. 适用专业：计算机科学与技术专业4. 开课学期：第5学期5. 实验教材：《算法设计与分析》实验指导书6. 先修课程：高级语言程序设计、离散数学、数据结构二、课程简介算法设计与分析实验将覆盖计算机软件实现中的大部分算法，具有一定的深度和广度，目的是让学生掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略来分析、解决实际问题并编程实现。

同时，算法设计与分析实验是对学生在软件设计方面的综合训练，包括问题分析，总体结构设计，程序设计基本技能和技巧等，以培养良好的编程风格和科学作风。

通过理论联系实际，最终提高学生动手操作的能力以及分析问题和解决问题的能力，培养对算法的复杂性进行分析的逻辑思维能力。

三、实验目的与任务实验是教学内容的重要一环，其目的一方面是为了让学生掌握算法设计与分析中的一些常用的典型的算法设计思想和方法；另一方面是为了让学生切实掌握各种算法的具体实现方法，培养学生的实际动手能力，加强学生创新思维能力的培养。

四、课程的基本要求（1）了解实验目的，熟悉实验环境。

（2）预习实验，准备好实验题目和操作步骤。

（3）能编译调试源程序,分析错误原因并加以修改,得出正确结果。

（4）能运用所学的知识正确分析程序得出的结果，并能给出改进的方案。

（5）将上述各项要求及实验结果编写成实验报告。

实验前学生要认真预习实验内容，按要求编写源程序及准备测试数据。

实验中,要按操作规程操作计算机，集中精力调试程序,并认真测试实验数据。

对实验程序的故障应自行分析解决，不拷贝其它人的成果。

对实验得出的结果能加以分析，提出改进的具体措施。

掌握递归与分治策略、动态规划、贪心算法、回溯法、分支限界法等算法思想；能独立运用相关算法策略分析问题、解决实际问题并编程实现。

算法设计与分析实验报告算法设计与分析实验报告引言：算法设计与分析是计算机科学中的重要课程，它旨在培养学生解决实际问题的能力。

本次实验旨在通过设计和分析不同类型的算法，加深对算法的理解，并探索其在实际应用中的效果。

一、实验背景算法是解决问题的步骤和方法的描述，是计算机程序的核心。

在本次实验中，我们将重点研究几种经典的算法，包括贪心算法、动态规划算法和分治算法。

通过对这些算法的设计和分析，我们可以更好地理解它们的原理和应用场景。

二、贪心算法贪心算法是一种基于局部最优选择的算法，它每一步都选择当前状态下的最优解，最终得到全局最优解。

在实验中，我们以背包问题为例，通过贪心算法求解背包能够装下的最大价值物品。

我们首先将物品按照单位重量的价值从大到小排序，然后依次将能够装入背包的物品放入，直到背包无法再装下物品为止。

三、动态规划算法动态规划算法是一种通过将问题分解为子问题，并记录子问题的解来求解整体问题的算法。

在实验中，我们以斐波那契数列为例，通过动态规划算法计算斐波那契数列的第n项。

我们定义一个数组来保存已经计算过的斐波那契数列的值，然后通过递推公式将前两项的值相加得到后一项的值，最终得到第n项的值。

四、分治算法分治算法是一种将问题分解为更小的子问题，并通过递归求解子问题的算法。

在实验中，我们以归并排序为例，通过分治算法对一个无序数组进行排序。

我们首先将数组分成两个子数组，然后对子数组进行递归排序，最后将两个有序的子数组合并成一个有序的数组。

五、实验结果与分析通过对以上三种算法的设计和分析，我们得到了以下实验结果。

在贪心算法中，我们发现该算法能够在有限的时间内得到一个近似最优解，但并不能保证一定得到全局最优解。

在动态规划算法中，我们发现该算法能够通过记忆化搜索的方式得到准确的结果，但在问题规模较大时，其时间复杂度较高。

在分治算法中，我们发现该算法能够将问题分解为更小的子问题，并通过递归求解子问题，最终得到整体问题的解。

实验一找最大和最小元素与归并分类算法实现（用分治法）一、实验目的1．掌握能用分治法求解的问题应满足的条件；2．加深对分治法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容1、找最大和最小元素输入n 个数，找出最大和最小数的问题。

2、归并分类将一个含有n个元素的集合，按非降的次序分类（排序）。

三、实验要求（1）用分治法求解问题（2）上机实现所设计的算法；四、实验过程设计（算法设计过程）1、找最大和最小元素采用分治法，将数组不断划分，进行递归。

递归结束的条件为划分到最后若为一个元素则max和min都是这个元素，若为两个取大值赋给max，小值给min。

否则就继续进行划分，找到两个子问题的最大和最小值后，比较这两个最大值和最小值找到解。

2、归并分类使用分治的策略来将一个待排序的数组分成两个子数组，然后递归地对子数组进行排序，最后将排序好的子数组合并成一个有序的数组。

在合并过程中，比较两个子数组的首个元素，将较小的元素放入辅助数组，并指针向后移动，直到将所有元素都合并到辅助数组中。

五、源代码1、找最大和最小元素#include<iostream>using namespace std;void MAXMIN(int num[], int left, int right, int& fmax, int& fmin); int main() {int n;int left=0, right;int fmax, fmin;int num[100];cout<<"请输入数字个数：";cin >> n;right = n-1;cout << "输入数字:";for (int i = 0; i < n; i++) {cin >> num[i];}MAXMIN(num, left, right, fmax, fmin);cout << "最大值为：";cout << fmax << endl;cout << "最小值为：";cout << fmin << endl;return 0;}void MAXMIN(int num[], int left, int right, int& fmax, int& fmin) { int mid;int lmax, lmin;int rmax, rmin;if (left == right) {fmax = num[left];fmin = num[left];}else if (right - left == 1) {if (num[right] > num[left]) {fmax = num[right];fmin = num[left];}else {fmax = num[left];fmin = num[right];}}else {mid = left + (right - left) / 2;MAXMIN(num, left, mid, lmax, lmin);MAXMIN(num, mid+1, right, rmax, rmin);fmax = max(lmax, rmax);fmin = min(lmin, rmin);}}2、归并分类#include<iostream>using namespace std;int num[100];int n;void merge(int left, int mid, int right) { int a[100];int i, j,k,m;i = left;j = mid+1;k = left;while (i <= mid && j <= right) {if (num[i] < num[j]) {a[k] = num[i++];}else {a[k] = num[j++];}k++;}if (i <= mid) {for (m = i; m <= mid; m++) {a[k++] = num[i++];}}else {for (m = j; m <= right; m++) {a[k++] = num[j++];}}for (i = left; i <= right; i++) { num[i] = a[i];}}void mergesort(int left, int right) { int mid;if (left < right) {mid = left + (right - left) / 2;mergesort(left, mid);mergesort(mid + 1, right);merge(left, mid, right);}}int main() {int left=0,right;int i;cout << "请输入数字个数：";cin >> n;right = n - 1;cout << "输入数字:";for (i = 0; i < n; i++) {cin >> num[i];}mergesort(left,right);for (i = 0; i < n; i++) {cout<< num[i];}return 0;}六、运行结果和算法复杂度分析1、找最大和最小元素图1-1 找最大和最小元素结果算法复杂度为O(logn）2、归并分类图1-2 归并分类结果算法复杂度为O(nlogn）实验二背包问题和最小生成树算法实现（用贪心法）一、实验目的1．掌握能用贪心法求解的问题应满足的条件；2．加深对贪心法算法设计方法的理解与应用；3．锻炼学生对程序跟踪调试能力；4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

第1篇一、实验目的本次实验旨在通过实际操作，加深对算法设计方法、基本思想、基本步骤和基本方法的理解与掌握。

通过具体问题的解决，提高利用课堂所学知识解决实际问题的能力，并培养综合应用所学知识解决复杂问题的能力。

二、实验内容1. 实验一：排序算法分析- 实验内容：分析比较冒泡排序、选择排序、插入排序、快速排序、归并排序等基本排序算法的效率。

- 实验步骤：1. 编写各排序算法的C++实现。

2. 使用随机生成的不同规模的数据集进行测试。

3. 记录并比较各算法的运行时间。

4. 分析不同排序算法的时间复杂度和空间复杂度。

2. 实验二：背包问题- 实验内容：使用贪心算法、回溯法、分支限界法解决0-1背包问题。

- 实验步骤：1. 编写贪心算法、回溯法和分支限界法的C++实现。

2. 使用标准测试数据集进行测试。

3. 对比分析三种算法的执行时间和求解质量。

3. 实验三：矩阵链乘问题- 实验内容：使用动态规划算法解决矩阵链乘问题。

- 实验步骤：1. 编写动态规划算法的C++实现。

2. 使用不同规模的矩阵链乘实例进行测试。

3. 分析算法的时间复杂度和空间复杂度。

4. 实验四：旅行商问题- 实验内容：使用遗传算法解决旅行商问题。

- 实验步骤：1. 设计遗传算法的参数，如种群大小、交叉率、变异率等。

2. 编写遗传算法的C++实现。

3. 使用标准测试数据集进行测试。

4. 分析算法的收敛速度和求解质量。

三、实验结果与分析1. 排序算法分析- 通过实验，我们验证了快速排序在平均情况下具有最佳的性能，其时间复杂度为O(nlogn)，优于其他排序算法。

- 冒泡排序、选择排序和插入排序在数据规模较大时效率较低，不适合实际应用。

2. 背包问题- 贪心算法虽然简单，但在某些情况下无法得到最优解。

- 回溯法能够找到最优解，但计算量较大，时间复杂度较高。

- 分支限界法结合了贪心算法和回溯法的特点，能够在保证解质量的同时，降低计算量。

3. 矩阵链乘问题- 动态规划算法能够有效解决矩阵链乘问题，时间复杂度为O(n^3)，空间复杂度为O(n^2)。

深圳大学实验报告课程名称：算法设计与分析实验项目名称：高斯消元学院：专业、班级：指导教师：杨烜报告人：学号：实验报告提交时间： 2015.5.15教务处制一、实验目的1.掌握变治法思想。

2.学会高斯列主元消去法及其应用。

二、实验内容1. 高斯列主元消去法求解线性方程组。

2. 高斯列主元消去法判断矩阵是否可逆？需要说明理由，如果可逆，求出其逆矩阵。

三、实验原理算法：GaussElimination(A[1...n,1...n],b[1...n])//用部分选主元法实现高斯消去法//输入：矩阵A[1...n,1...n]和列向量b[1...n]//输出：一个代替A的上三角形等价矩阵图，相应的右边的值位于第(n+1)列中for i<-1 to n do A[i,n+1]<-b[i] //把b作为最后一列添加到A中for i<-1 to n-1 dopivotrow<-ifor j<-i+1 to n doif |A[j,i]|>|A[pivotrow,i]|pivotrow<-jfor k<-i to n+1 doswap(A[i,k],A[pivotrow,k])for j<-i+1 to n dotemp<-A[j,i]/A[i,i]for k<-i to n+1 doA[j,k]<-A[j,k]-A[i,k]*temp算法：GaussBackSub(A[1...n,1...n+1])//实现高斯消去法的反向替换//输入：一个代替A的上三角形等价矩阵图，相应的右边的值位于第(n+1)列中 //输出：方程组的n个解for i<-n downto 1 dotemp<-0.0for j<-n downto i+1temp<-temp+A[i,j]*x[j]x[i]<-(A[i,n+1]-temp)/A[i,i]return x算法：IsInverseMatrix(A[1...n,1...n],b[1...n])//用高斯消去法判断是否为逆矩阵//输入：矩阵A[1...n,1...n]//输出：如果是逆矩阵输出1，否则输出0for i<-1 to n do A[i,n+1]<-b[i] //把b作为最后一列添加到A中for i<-1 to n-1 dopivotrow<-ifor j<-i+1 to n doif |A[j,i]|>|A[pivotrow,i]|pivotrow<-jfor k<-i to n+1 doswap(A[i,k],A[pivotrow,k])for j<-i+1 to n dotemp<-A[j,i]/A[i,i]for k<-i to n+1 doA[j,k]<-A[j,k]-A[i,k]*tempfor i<-1 to nif(A[i,i]=0)return 0return 1算法：求矩阵的逆矩阵(伪代码篇幅较长，仅描述主要思想)思想描述：设待求矩阵B的逆矩阵为X，根据逆矩阵的定义，满足BX=I(其中I为n阶单位矩阵)。

《算法设计与分析》课程实验报告实验序号：实验项目名称：随机化算法一、实验题目1.N后问题问题描述：在n*n格的棋盘上放置彼此不受攻击的n个皇后，任何两个皇后不放在同一行同一列，同一斜线上，问有多少种放法。

2.主元素问题问题描述：设A是含有n个元素的数组，如果元素x在A中出现的次数大于n/2，则称x是A的主元素。

给出一个算法，判断A中是否存在主元素。

二、实验目的（1）通过N后问题的实现，体会拉斯维加斯随机算法的随机特点：运行次数随机但有界，找到的解一定为正确解。

但某次运行可能找不到解。

（2）通过实现主元素的不同算法，了解蒙特卡罗算法的随机特性：对于偏真的蒙特卡罗算法，找到为真的解一定是正确解；但非真的解以高概率给出解的正确率------即算法找到的非真解以小概率出现错误。

同时体会确定性算法与随机化算法的差异及各自的优缺点。

（3）通过跳跃表的实现，体会算法设计的运用的广泛性，算法设计的思想及技巧不拘泥独立问题的解决，而在任何需要计算机解决的问题中，都能通过算法设计的技巧（无论是确定性还是随机化算法）来灵巧地解决问题。

此实验表明，通过算法设计技巧与数据组织的有机结合，能够设计出高效的数据结构。

三、实验要求（1）N后问题分别以纯拉斯维加斯算法及拉斯维加斯算法+回溯法混合实现。

要求对同一组测试数据，完成如下任务a.输出纯拉斯维加斯算法找到解的运行次数及运行时间。

b.输出混合算法的stopVegas值及运行时间c.比较a、b的结果并分析N后问题的适用情况。

（2）主元素问题，要求对同一组测试数据，完成如下任务：a.若元素可以比较大小，请实现O(n )的确定性算法，并输出其运行时间。

b.(选做题）若元素不可以比较大小，只能比较相同否，请实现O（n) 确性算法，并输出其运行时间。

c.实现蒙特卡罗算法，并输出其运行次数及时间。

d.比较确定性算法与蒙特卡罗算法的性能，分析每种方法的优缺点。

（3）参照教材实现跳跃表（有序）及基本操作：插入一个结点，删除一个结点。

《算法设计与分析》实验指导书《算法设计与分析》实验指导书本文档主要用于《算法设计与分析》课程的实验指导。

《算法设计与分析》旨在教会学生处理各种问题的方法，通过实验，使学生能够把所学的方法用于具体的问题，并对所用算法进行比较分析，从而提高学生分析问题、解决问题的能力。

通过该课程的实验，使学生对课堂中所讲述的内容有一个直观的认识，更好地掌握所学的知识，培养学生的实际动手能力，加强学生创新思维能力的培养。

本课程设计了7个设计型实验。

实验内容包括用分治法、动态规划、贪心法、回溯法以及分支限界法求解问题。

一、实验内容安排二、实验基本要求实验前要求学生一定要先了解实验目的、内容、要求以及注意事项，要求学生熟悉实验对象，设计并编写相应的算法。

学生应独立完成所布置实验内容，编写代码，运行程序，记录结果并撰写实验报告。

三、实验报告要求实验结束后，应及时整理出实验报告，实验报告提交书面文档。

四、考核方式理论考试（60％）＋实验（30％）+作业（10%）五、实验内容与指导实验一快速排序问题1．实验目的(1) 用分治法求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n个无序的数值数据，现要求将其排列成一个有序的序列。

4. 实验步骤(1) 输入实现该问题的源代码；(2) 输入测试数据，验证代码的正确性。

5.实验要求(1)做好实验预习，熟悉本实验中所使用的开发环境。

(2)写出实验报告①实验目的②实验内容③出错信息及处理方法④实验结果实验二最少硬币问题1．实验目的(1) 用动态规划求解该问题。

2．实验环境PC机，要求安装Eclipse软件或VC++软件供学生实验。

3．实验内容有n种不同面值的硬币，各硬币面值存于数组T[1:n]；现用这些面值的钱来找钱；各面值的个数存在数组Num[1:n]中。

对于给定的1≤n≤10，硬币面值数组、各面值的个数及钱数m，0<=m<=2001，设计一个算法，计算找钱m的最少硬币数。

算法设计与分析实验报告一实验名称统计数字问题评分实验日期2014 年11 月15 日指导教师姓名专业班级学号一.实验要求1、掌握算法的计算复杂性概念。

2、掌握算法渐近复杂性的数学表述。

3、掌握用C++语言描述算法的方法。

4．实现具体的编程与上机实验，验证算法的时间复杂性函数。

二.实验内容统计数字问题1、问题描述一本书的页码从自然数1 开始顺序编码直到自然数n。

书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。

例如，第6 页用数字6 表示，而不是06 或006 等。

数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9)2、编程任务给定表示书的总页码的10 进制整数n (1≤n≤109) 。

编程计算书的全部页码中分别用到多少次数字0，1，2， (9)三.程序算法将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。

把这些结果统计起来即可。

四.程序代码#include<iostream.h>int s[10]; //记录0~9出现的次数int a[10]; //a[i]记录n位数的规律void sum(int n,int l,int m){ if(m==1){int zero=1;for(int i=0;i<=l;i++) //去除前缀0{ s[0]-=zero;zero*=10;} }if(n<10){for(int i=0;i<=n;i++){ s[i]+=1; }return;}//位数为1位时,出现次数加1//位数大于1时的出现次数for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1){m=1;int i;for(i=1;i<t;i++)m=m*10;a[t]=t*m;}int zero=1;for(int i=0;i<l;i++){ zero*= 10;} //求出输入数为10的n次方int yushu=n%zero; //求出最高位以后的数int zuigao=n/zero; //求出最高位zuigaofor(i=0;i<zuigao;i++){ s[i]+=zero;} //求出0~zuigao-1位的数的出现次数for(i=0;i<10;i++){ s[i]+=zuigao*a[l];} //求出与余数位数相同的0~zuigao-1位中0~9出现的次数//如果余数是0,则程序可结束,不为0则补上所缺的0数,和最高位对应所缺的数if(yushu==0) //补上所缺的0数,并且最高位加1{ s[zuigao]++;s[0]+=l; }else{ i=0;while((zero/=10)>yushu){ i++; }s[0]+=i*(yushu+1);//补回因作模操作丢失的0s[zuigao]+=(yushu+1);//补回最高位丢失的数目sum(yushu,l-i-1,m+1);//处理余位数}}void main(){ int i,m,n,N,l;cout<<"输入数字要查询的数字:";cin>>N;cout<<'\n';n = N;for(i=0;n>=10;i++){ n/=10; } //求出N的位数n-1l=i;sum(N,l,1);for(i=0; i<10;i++){ cout<< "数字"<<i<<"出现了:"<<s[i]<<"次"<<'\n'; }} 五.程序调试中的问题调试过程，页码出现报错。

深圳大学实验报告课程名称：算法设计与分析实验项目名称：排序算法性能分析学院：专业、班级：指导教师：**报告人：学号：实验报告提交时间： 2015.4.3教务处制一、实验目的与实验环境实验目的：1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。

实验环境：VC++ 6.0二、实验原理与算法描述算法（1）选择排序 SelectSort(A[0...n-1],n)//利用选择排序对给定的数组排序//输入：一个可排序数组A[0...n-1]//输出：非降序排列的数组A[0...n-1]for i<-0 to n-2 domin<-ifor j<-i+1 to n-1 doif A[j]<A[min]min<-jswap A[i] and A[min]理论效率：C(n) ∈θ(n^2),不稳定算法算法（2）快速排序 QuickSort(A[0...n-1],n)//利用快速排序对给定的数组排序//输入：一个可排序数组A[0...n-1]//输出：非降序排列的数组A[0...n-1]if l<rs<-Partition(A[l...r]) //s是分裂位置Quicksort(A[l...s-1])Quicksort(A[s+1...r])Partition(A[l...r])//以第一个数为中轴，对子数组进行分区//输入：数组A[0...n-1]中的子数组A[l...r]，由左右下标l和r定义 //输出：数组A[l...r]的一个分区，分裂点的未知作为函数的返回值p<-A[l]i<-l;j<-r+1repeatrepeat i<-i+1 until A[i]>=Prepeat j<-j-1 until A[j]<=Pswap(A[i],A[j])until i>=jswap (A[i],A[j]) //当i>=j撤销最后一次交换swap (A[l],A[j])return j理论效率：C(n) ∈θ(nlnn)，不稳定算法算法（3）合并排序 MergeSort(A[0...n-1])//利用合并排序对给定的数组排序//输入：一个可排序数组A[0...n-1]//输出：非降序排列的数组A[0...n-1]if n>1copy A[0...⌊n/2⌋-1] to B[0...⌊n/2⌋-1]copy A[⌊n/2⌋...n-1] to C[0...⌈n/2⌉-1]Mergesort(B[0...⌊n/2⌋-1])Mergesort(C[0...⌈n/2⌉-1])Merge(B,C,A)Merge(B[0...p-1],C[0...q-1],A[0...p+q-1]) //将两个有序数组合并为一个有序数组//输入：两个有序数组B[0...p-1],C[0...q-1]//输出：A[0...p+q-1]中已经有序存放了B和C中的元素i<-0;j<-0;k<-0while i<p and j<q doif B[i]<=C[j]A[k]<-B[i];i<-i+1elseA[k]<-C[j];j<-j+1k<-k+1if i=pcopy C[j...q-1] to A[k...p+q-1]elsecopy B[i...p-1] to A[k...p+q-1] 理论效率：C(n)∈θ(nlogn)，稳定算法算法（4）冒泡排序 BubbleSort(A[0...n-1]) //利用冒泡排序对给定的数组排序//输入：一个可排序数组A[0...n-1]//输出：非降序排列的数组A[0...n-1]for i<-0 to n-2 dofor j<-0 to n-2-i doif A[j+1]<A[j]swap A[j] and A[j+1]理论效率：C(n)∈θ(n^2)，稳定算法算法（5）插入排序 InsertSort(A[0...n-1],n) //利用插入排序对给定的数组排序//输入：一个可排序数组A[0...n-1]//输出：非降序排列的数组A[0...n-1]for k<-2 to n doA[0]<-A[k]j<-k-1while (j!=0 and A[j]>A[0]) doA[j+1]<-A[j]j<-j-1A[j+1]<-A[0]理论效率：C(n)∈θ(n^2)，稳定算法三、实验代码与运行截图实验关键代码：1.选择排序2.快速排序3.合并排序4.冒泡排序5.插入排序四、实验数据整理与分析表一选择排序输入规模n与运行时间统计图n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0020 0.1795 17.8550表二快速排序输入规模n与运行时间统计图n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0010 0.0020 0.0435表三合并排序输入规模n与运行时间统计图n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0025 0.0260表四冒泡排序输入规模n与运行时间统计图n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0025 0.3550 39.8810表五插入排序输入规模n与运行时间统计图n 10 100 1000 10000 100000 t(Avg)/sec lim->0 lim->0 0.0005 0.0900 8.9120图1. 选择排序时间效率与输入规模n的关系图图2. 快速排序时间效率与输入规模n的关系图图3. 合并排序时间效率与输入规模n的关系图图4. 冒泡排序时间效率与输入规模n的关系图图5. 插入排序时间效率与输入规模n的关系图图6. 5种不同排序算法时间效率对比图实验分析：1.从实验结果可以看出，可以验证，当规模n趋向无穷大的时候，排序算法的效率关系为合并排序<快速排序<插入排序<选择排序<冒泡排序。

《算法设计与分析》实验教学大纲
课程名称：算法设计与分析
英文名称：Design and Analysis of Algorithms
课程编号：23132002
课程性质：课程类型：是否为独立设课的实验课：否
适用专业：计算机科学与技术，软件工程
学时与学分：总学时：54 总学分：2.5 实验学时：18 实验学分：0.5
执笔人：彭小刚
制定时间：2006年12月修订
一、实验课的任务、性质与目的：
本课程实验目的是验证、巩固和补充课堂讲授的理论知识。

培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力，为实际工作打下基础。

实验的安排和要求是：用程序实现经典算法，学习算法设计的主要策略方法、原理并根据实例加以调试，培养动手设计、分析和综合实验结果以及撰写实验报告的能力。

在实验中养成严肃认真的治学态度和踏实细致、实事求是的作风。

二、主要仪器设备及环境：
具备编程语言环境的PC机每组一台
三、实验项目的设置与实验内容
本课程上机实验可参考下表组织进行。

四、教材、实验教材（指导书）：
[1] 郑宗汉，郑晓明算法设计与分析清华大学出版社 2005年
[2] 实验教材：《算法设计与分析－实验讲义》王华民，彭小刚。

五、考核方式与评分办法：
本课程的考核分为实验成绩、平时作业成绩以及期末考试成绩三大部分，其中期末考试以闭卷笔试为主。

总成绩按以下公式计算：
总成绩＝(平时成绩＋实验成绩)×（30%～40％）＋期末成绩×（70%～60％）
六、大纲审核人：张席。

算法设计与分析实验报告1. 引言本实验旨在设计和分析一个算法，解决特定的问题。

通过对算法的设计、实现和性能分析，可以对算法的优劣进行评估和比较。

本报告将按照以下步骤进行展开：1.问题描述2.算法设计3.算法实现4.性能分析5.结果讨论和总结2. 问题描述在本实验中，我们面临的问题是如何在一个给定的无序数组中寻找一个特定元素的位置。

具体而言，给定一个包含n个元素的数组A和一个目标元素target，我们的目标是找到target在数组A中的位置，如果target不存在于数组中，则返回-1。

3. 算法设计为了解决上述问题，我们设计了一个简单的线性搜索算法。

该算法的思想是从数组的第一个元素开始，逐个比较数组中的元素与目标元素的值，直到找到匹配的元素或搜索到最后一个元素。

算法的伪代码如下：function linear_search(A, target):for i from 0 to len(A)-1:if A[i] == target:return ireturn -14. 算法实现我们使用Python编程语言实现了上述线性搜索算法。

以下是算法的实现代码：def linear_search(A, target):for i in range(len(A)):if A[i] == target:return ireturn-15. 性能分析为了评估我们的算法的性能，我们进行了一系列实验。

我们使用不同大小的数组和不同目标元素进行测试，并记录了每次搜索的时间。

实验结果显示，线性搜索算法的时间复杂度为O(n)，其中n是数组的大小。

这是因为在最坏的情况下，我们需要遍历整个数组才能找到目标元素。

6. 结果讨论和总结通过对算法的设计、实现和性能分析，我们可以得出以下结论：1.线性搜索算法是一种简单但有效的算法，适用于小规模的数据集。

2.线性搜索算法的时间复杂度为O(n)，在处理大规模数据时可能效率较低。

3.在实际应用中，我们可以根据具体的问题和数据特征选择合适的搜索算法，以提高搜索效率。

算法设计与分析实验报告算法设计与分析实验报告一、引言在计算机科学领域，算法设计与分析是非常重要的研究方向。

本次实验旨在通过实际案例，探讨算法设计与分析的方法和技巧，并验证其在实际问题中的应用效果。

二、问题描述本次实验的问题是求解一个整数序列中的最大子序列和。

给定一个长度为n的整数序列，我们需要找到一个连续的子序列，使得其和最大。

三、算法设计为了解决这个问题，我们设计了两种算法：暴力法和动态规划法。

1. 暴力法暴力法是一种朴素的解决方法。

它通过枚举所有可能的子序列，并计算它们的和，最终找到最大的子序列和。

然而，由于需要枚举所有子序列，该算法的时间复杂度为O(n^3)，在处理大规模数据时效率较低。

2. 动态规划法动态规划法是一种高效的解决方法。

它通过定义一个状态转移方程，利用已计算的结果来计算当前状态的值。

对于本问题，我们定义一个一维数组dp，其中dp[i]表示以第i个元素结尾的最大子序列和。

通过遍历整个序列，我们可以利用状态转移方程dp[i] = max(dp[i-1]+nums[i], nums[i])来计算dp数组的值。

最后，我们返回dp数组中的最大值即为所求的最大子序列和。

该算法的时间复杂度为O(n)，效率较高。

四、实验结果与分析我们使用Python编程语言实现了以上两种算法，并在相同的测试数据集上进行了实验。

1. 实验设置我们随机生成了1000个整数作为测试数据集，其中包含正数、负数和零。

为了验证算法的正确性，我们手动计算了测试数据集中的最大子序列和。

2. 实验结果通过对比实验结果，我们发现两种算法得到的最大子序列和是一致的，验证了算法的正确性。

同时，我们还对两种算法的运行时间进行了比较。

结果显示，暴力法的运行时间明显长于动态规划法，进一步证明了动态规划法的高效性。

五、实验总结通过本次实验，我们深入了解了算法设计与分析的方法和技巧，并通过实际案例验证了其在解决实际问题中的应用效果。

我们发现，合理选择算法设计方法可以提高算法的效率，从而更好地解决实际问题。

《算法设计与分析》实验指导书曹严元计算机与信息科学学院2007年5月目录实验一递归算法与非递归算法 (2)实验二分治算法 ................................................... 错误！未定义书签。

实验三贪心算法 (3)实验四动态规划 (2)实验五回溯法 (3)实验六分枝—限界算法 (4)实验七课程设计 (4)实验一递归与分治算法实验目的1.了解并掌握递归的概念，掌握递归算法的基本思想；2.掌握分治法的基本思想方法；3.了解适用于用递归与分治求解的问题类型，并能设计相应递归与分治算法；4.掌握递归与分治算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。

实验二动态规划实验目的1.掌握动态规划的基本思想方法；2.了解适用于用动态规划方法求解的问题类型，并能设计相应动态规划算法；3.掌握动态规划算法复杂性分析方法。

实验三贪心算法实验目的1.掌握贪心法的基本思想方法；2.了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法；3.掌握贪心算法复杂性分析方法分析问题复杂性。

实验五回溯法实验目的1.掌握回溯法的基本思想方法；2.了解适用于用回溯法求解的问题类型，并能设计相应回溯法算法；3.掌握回溯法算法复杂性分析方法，分析问题复杂性。

实验六 分枝—限界算法实验目的1. 掌握分枝—限界的基本思想方法；2. 了解适用于用分枝—限界方法求解的问题类型，并能设计相应动态规划算法；3. 掌握分枝—限界算法复杂性分析方法，分析问题复杂性。

实验七 课程设计实验目的1. 在已学的算法基本设计方法的基础上，理解算法设计的基本思想方法；2. 掌握对写出的算法的复杂性分析的方法，理解算法效率的重要性；3. 能运用所学的基本算法设计方法对问题设计相应算法，分析其效率，并建立对算法进行改进，提高效率的思想意识。

预习与实验要求1. 预习实验指导书及教材的有关内容，回顾所学过的算法的基本思想；2. 严格按照实验内容进行实验，培养良好的算法设计和编程的习惯；3. 认真听讲，服从安排，独立思考并完成实验。

深圳大学实验报告课程名称：算法设计与分析实验项目名称：大整数乘法学院：专业、班级：指导教师：杨烜报告人：学号：实验报告提交时间： 2015.4.30教务处制一、实验目的与实验环境实验目的：1.掌握分治法。

2.学会测试和分析算法的时间性能。

实验环境：VC++ 6.0二、实验原理与算法描述算法;基于分治法的大整数乘法实现思想描述：对于任何两位数a=a1a0和b=b1b0来说，它们的积可以用以下公式来实现：c=a*b=c2*(10^n)+c1*(10^(n/2))+c0其中：c2=a1*b1，是它们第一个数字的积c0=a0*b0，是它们第二个数字的积c1=(a1+a0)*(b1+b0)-(c2+c0)，是a数字和与b数字和的积减去c2与c0的和通过上式可以用分治法来求解两个n位大整数a和b的乘积。

首先从中间把两个数字一分为二，把a的前半部分即为a1，后半部分记为a0；对于b 亦是如此。

在这种记法中，a=a1a0意味着a=a1a0=a1*(10^(n/2))+a0，b=b1b0意味着b=b1b0=b1*(10^(n/2))+b0。

所以，利用与计算两位数相同的方法，可以得到：c= a*b =（a1*(10^(n/2))+a0）*（b1*(10^(n/2))+b0）= c2*(10^n)+c1*(10^(n/2))+c0同时，通过递归应用相同的方法来计算c2,c1,c0。

整个实现过程中，首先随机产生两个n位（n通过键盘输入）乘数，然后通过调用分段函数将两个乘数分成两半，最后通过上述分解式求解两个大整数的乘积。

整个过程需要实现的有随机函数、分段函数、倍数函数、减法函数、加法函数、乘法函数以及主函数（部分代码如下截图1至截图7所示，实验源代码作为附件上传）。

三、实验代码与运行截图截图1：随机函数截图3：倍数函数截图4：减法函数截图6：乘法函数截图7：主函数四、实验数据整理与分析表一基于分治的大整数乘法时间统计表数据规模n：10 100 1000 10000 100000耗时(sec) 0.0018 0.0255 0.9597 41.2395 1580.8500备注：所有数据均为20次随机产生大整数运行后的平均值说明：为了更清晰准确的看到数据规模与所需时间之间的关系，实验中将数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均数所得。