算法设计与分析实验

算法设计与分析实验报告姓名：班级：计算机科学与技术102班学号：1090教师：设计时间：2012.04.23编程工具：C-Free 5.0【实验一】：使用递归方法输出杨辉三角杨辉三角.cpp//使用递归方法输出杨辉三角，每个数字占用4个空格位#include <stdlib.h>#include <stdio.h>int calcit(int x, int y){if (x==y||y==0)return 1;elsereturn calcit(x-1,y-1)+calcit(x-1,y);}int main(){int i, j,k,n;printf("请输入行数(最好<=13)：");scanf("%d",&n);for (i = 0; i<n; i++){for(k=(n-i)*2;k>0;k--)printf(" ");for (j=0;j<=i;j++)printf("%4d",calcit(i, j));printf("\n");}return 0;}【实验二】：快速排序（一）快速排序.cpp#include<stdio.h>#include<stdlib.h>#define SIZE 100void quick_sort(int data[],int x,int y);int pation(int data[],int x,int y);int main(){int i,n,data[SIZE];printf("请输入要排列的数目（<=100）：");scanf("%d",&n);printf("请输入要排列的数列：\n");for(i=0;i<n;++i)scanf("%d",&data[i]);quick_sort(data,0,n-1);printf("排列后的数列为：\n");for(i=0;i<n;++i)printf( "%d ",data[i]);printf("\n");return 0;}void quick_sort(int data[],int x,int y){if(x>=y) return;int q=pation(data,x,y);quick_sort(data,x,q-1);quick_sort(data,q+1,y);}int pation(int data[],int x,int y){int n=data[x],i=x+1,j=y,temp;while(1){while(data[i]<n) ++i;while(data[j]>n) --j;if(i>=j) break;temp=data[i]; data[i]=data[j]; data[j]=temp;}data[x]=data[j];data[j]=n;return j;}（二）插入排序.cpp#include<stdio.h>#include<conio.h>#define X 100#define Y 100int main(){int a[X],r[Y];int *p;int i,j,n;printf("请输入要排列的数目（<=100）：");scanf("%d",&n);printf("请输入要排列的数列：\n");for(i=0;i<n;i++){p=&a[i];scanf("%d",p);r[i+1]=a[i];}r[0]=1;for(i=2;i<=n;i++){r[0]=r[i];j=i-1;while(r[j]>r[0]){r[j+1]=r[j];j--;}r[j+1]=r[0];}printf("排列后的顺序是：\n");for(i=1;i<=n;i++){p=&r[i];printf("%d ",*p);}printf("\n");return 0;}【实验三】：趣味矩阵（一）次上三角的自动打印次上三角的自动打印.cpp#include "stdio.h"#include "stdlib.h"#define MAX 100void InterestMatrix(int n){int a[MAX][MAX];int k=1,m=0; // 计数器int i,j;//矩阵初始化for(i=0;i<n;i++){for(j=0;j<=i;j++)a[i][j]=k++;}//打印矩阵for(i=0;i<n;i++){m=i;for(j=0;j<n-i;j++)printf("%d ",a[m++][j]);printf("\n");}}int main(){int n;printf("输入矩阵的阶数n:");scanf("%d",&n);printf("\n");InterestMatrix(n);printf("\n");return 0;}（二）特殊趣味矩阵的打印趣味矩阵.cpp//使左对角线和右对角线上的元素为0，它们上方的元素为1，左边的元素为2，下方的元素为3，右边的元素为4#include<stdio.h>int main(){int i,j,a[100][100],n;printf("请输入矩阵的阶数：");scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){if(i==j||i+j==n+1)a[i][j]=0;if(i<j&&i+j<n+1)a[i][j]=1;if(i>j&&i+j<n+1)a[i][j]=2;if(i>j&&i+j>n+1)a[i][j]=3;if(i<j&&i+j>n+1)a[i][j]=4;}for(i=1;i<=n;i++){printf("\n");for(j=1;j<=n;j++)printf("%d ",a[i][j]);}printf("\n");return 0;}。

第1篇一、实验背景与目的随着计算机技术的飞速发展，算法在计算机科学中扮演着至关重要的角色。

为了加深对算法设计与分析的理解，提高实际应用能力，本实验课程设计旨在通过实际操作，让学生掌握算法设计与分析的基本方法，学会运用所学知识解决实际问题。

二、实验内容与步骤本次实验共分为三个部分，分别为排序算法、贪心算法和动态规划算法的设计与实现。

1. 排序算法（1）实验目的：熟悉常见的排序算法，理解其原理，比较其优缺点，并实现至少三种排序算法。

（2）实验内容：- 实现冒泡排序、快速排序和归并排序三种算法。

- 对每种算法进行时间复杂度和空间复杂度的分析。

- 编写测试程序，对算法进行性能测试，比较不同算法的优劣。

（3）实验步骤：- 分析冒泡排序、快速排序和归并排序的原理。

- 编写三种排序算法的代码。

- 分析代码的时间复杂度和空间复杂度。

- 编写测试程序，生成随机测试数据，测试三种算法的性能。

- 比较三种算法的运行时间和内存占用。

2. 贪心算法（1）实验目的：理解贪心算法的基本思想，掌握贪心算法的解题步骤，并实现一个贪心算法问题。

（2）实验内容：- 实现一个贪心算法问题，如活动选择问题。

- 分析贪心算法的正确性，并证明其最优性。

（3）实验步骤：- 分析活动选择问题的贪心策略。

- 编写贪心算法的代码。

- 分析贪心算法的正确性，并证明其最优性。

- 编写测试程序，验证贪心算法的正确性。

3. 动态规划算法（1）实验目的：理解动态规划算法的基本思想，掌握动态规划算法的解题步骤，并实现一个动态规划算法问题。

（2）实验内容：- 实现一个动态规划算法问题，如背包问题。

- 分析动态规划算法的正确性，并证明其最优性。

（3）实验步骤：- 分析背包问题的动态规划策略。

- 编写动态规划算法的代码。

- 分析动态规划算法的正确性，并证明其最优性。

- 编写测试程序，验证动态规划算法的正确性。

三、实验结果与分析1. 排序算法实验结果：- 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)。

《算法设计与分析》实验指导实验一分治与递归一、实验目的：1. 理解递归的概念。

2. 掌握设计有效算法的分治策略。

3. 掌握C++面向对象编程方法。

二、实验指导1. 分治法的总体思想求解一个复杂问题可以将其分解成若干个子问题，子问题还可以进一步分解成更小的问题，直到分解所得的小问题是一些基本问题，并且其求解方法是已知的，可以直接求解为止。

分治法作为一种算法设计策略，要求分解所得的子问题是同类问题，并要求原问题的解可以通过组合子问题的解来获取。

分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效的算法。

2. 分治法的基本步骤divide-and-conquer(P){if ( | P | <= n0) adhoc(P); //解决小规模的问题divide P into smaller subinstances P1,P2,...,Pk；//分解问题for (i=1,i<=k,i++)yi=divide-and-conquer(Pi); //递归的解各子问题return merge(y1,...,yk); //将各子问题的解合并为原问题的解}3. C++类定义例class Complex{public:Complex( ):real(0),imag(0) {} //构造函数Complex(double r,double i):real(r),imag(i) {} //构造函数Complex operator + (Complex c2); //重载“+”运算符operator double( ) //重载类型转换运算符{return real;}friend ostream& operator << (ostream&,Complex&); //重载流插入运算符“<<”private:double real;double imag;};三、实验内容及要求：在程序中创建一个学生对象数组并初始化数据，完成如下编程任务。

《算法分析与设计》实验教学大纲一、课程描述《算法分析与设计》是计算机科学与技术专业的一门核心课程，旨在让学生了解并掌握基本的算法和算法分析的方法。

通过本课程的学习，学生将能够理解算法设计的基本原理和方法，并能够应用这些原理和方法解决实际问题。

二、课程目标1.了解算法设计和算法分析的基本概念和方法；2.掌握常用的算法设计和分析技巧；3.能够独立设计和实现算法，并进行正确性和效率分析；4.熟悉常用的算法实现和优化技术；5.能够将算法应用于解决实际问题。

三、教学内容1.算法基础知识(1)算法的定义和特性；(2)算法的表达方式；(3)算法的复杂度分析。

2.基本排序算法(1)冒泡排序；(3)选择排序；(4)快速排序；(5)归并排序；(6)堆排序。

3.检索算法(1)顺序查找；(2)二分查找；(3)哈希查找；(4)平衡二叉树查找。

4.图算法(1)图的表示方式；(2)深度优先；(3)广度优先；(4)最短路径算法；(5)最小生成树算法；(6)拓扑排序。

5.动态规划算法(1)递归算法；(3)状态转移方程；(4)应用案例分析。

6.贪心算法(1)贪心算法的基本思想和特点；(2)贪心算法的应用案例。

7.分治算法(1)分治算法的基本思想和特点；(2)分治算法的应用案例。

8.高级算法设计思想(1)动态规划的高级技巧；(2)贪心算法的高级技巧；(3)分治算法的高级技巧；(4)随机化算法；(5)近似算法。

四、实验教学安排1.实验1：基本排序算法的实现及性能比较(1)实现冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序；(2)对比各个排序算法的性能（时间复杂度和空间复杂度）。

2.实验2：检索算法的实现及性能比较(1)实现顺序查找、二分查找、哈希查找、平衡二叉树查找；(2)对比各个检索算法的性能（时间复杂度和空间复杂度）。

3.实验3：图算法的实现及应用(1)实现图的基本操作（创建、添加节点、添加边）；(2)实现图的深度优先和广度优先；(3) 实现最短路径算法（Dijkstra算法和Floyd算法）；(4) 实现最小生成树算法（Kruskal算法和Prim算法）；(5)实现拓扑排序。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法设计与分析实验报告实验一全排列、快速排序【实验目的】1. 掌握全排列的递归算法。

2. 了解快速排序的分治算法思想。

【实验原理】一、全排列全排列的生成算法就是对于给定的字符集，用有效的方法将所有可能的全排列无重复无遗漏地枚举出来。

任何n个字符集的排列都可以与1～n的n个数字的排列一一对应，因此在此就以n 个数字的排列为例说明排列的生成法。

n个字符的全体排列之间存在一个确定的线性顺序关系。

所有的排列中除最后一个排列外，都有一个后继；除第一个排列外，都有一个前驱。

每个排列的后继都可以从它的前驱经过最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。

二、快速排序快速排序（Quicksort）是对冒泡排序的一种改进。

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

【实验内容】１.全排列递归算法的实现。

２.快速排序分治算法的实现。

【实验结果】１. 全排列：２. 快速排序：实验二最长公共子序列、活动安排问题【实验目的】１. 了解动态规划算法设计思想，运用动态规划算法实现最长公共子序列问题。

２. 了解贪心算法思想，运用贪心算法设计思想实现活动安排问题。

【实验原理】一、动态规划法解最长公共子序列设序列X=和Y=的一个最长公共子序列Z=，则：i. 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列；ii. 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列；iii. 若xm≠yn且z k≠yn ，则Z是X和Yn-1的最长公共子序列。

其中Xm-1=，Yn-1=，Zk-1=。

最长公共子序列问题具有最优子结构性质。

由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。

第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)。

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

现要设计一个满足以下要求的比赛日程表：（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 71 2 3 4 5 6 7 82 1 43 6 7 8 53 4 1 2 7 8 5 61 2 3 4 3 2 1 8 5 6 71 2 3 4 5 6 7 8 1 4 3 21 2 1 4 3 6 5 8 7 2 1 4 31 2 3 4 1 2 7 8 5 6 3 2 1 42 1 43 2 1 8 7 6 54 3 2 1（1）（2）（3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。

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

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

依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。

《算法设计与分析》实验教学大纲实验学时：32 实验个数：7 实验学分：1课程性质：适用专业：计算机科学与技术、软件工程教材及参考书：1.《计算机算法设计与分析》，王晓东，北京：电子工业出版社，2005年2.《算法与数据结构》，傅清祥等著，北京：电子工业出版社，20033.《计算机算法导引—设计与分析》，卢开澄著，北京：清华大学出版社，2001 大纲执笔人：刘芳大纲审定人：郭涛一、实验课的性质与任务算法的设计与分析是计算机科学的核心问题之一，也是计算机科学与技术专业本科及研究生的一门重要的专业基础课，其内容是研究计算机领域及其有关领域中的一些非数值计算的常用算法。

课程将覆盖计算机软件实现中常用的、有代表性的算法，并具有一定的深度和广度，通过实验，使学生理解并掌握算法设计的基本技术，让学生具有针对所给的问题设计和实现高效算法的基本能力。

二、实验课程目的与要求计算机科学的一个核心问题是算法理论，本课程介绍非数值算法设计的策略与技术，同时介绍算法的复杂性的概念通过对一些代表性算法的使用达到了解掌握与运用的目的。

通过完成课程实验，使学生达到如下要求：1.熟悉各种基本常用算法的基本思想、适用范围，初步掌握算法分析的基本技巧以及如何根据实际问题设计一个有效的算法。

2.能对给定问题分析出恰当的数学模型，并设计出解决方案，将算法用高级语言（C，VC++等）编程实现。

三、实验内容安排：实验一算法设计基础（验证型、设计型实验4学时）1.实验目的（1）巩固程序设计语言基础知识，熟悉文件操作等。

（2）对给定问题，能设计算法并编程实现问题的求解，并分析算法的时间复杂性。

2.实验要求（1）认真填写实验报告，附加源代码（主要代码）和运行记录；（2）对设计好的算法，测试运行实验数据，检查输出是否正确。

并对算法的时间和空间复杂度进行分析。

3.实验内容：（1）统计数字问题（P8）#include "stdafx.h"#include <iostream>#include <conio.h>#include <string>using namespace std;void read_information(string &Data){//从文件中读出停车场信息，并且存放在数组中cout<<"正在读取数据......"<<endl;FILE *fp;char ch;if((fp=fopen("data.txt","rt+"))==NULL){printf("\nCannot open file strike any key exit!");getch();exit(1);}ch=fgetc(fp);while(ch!=EOF){Data = Data + ch;ch=fgetc(fp);}fclose(fp);cout<<"读取完成......"<<endl;}void save_information(string data){//把数组中的停车场信息存放回文件中cout<<"正在写入文件......"<<endl;FILE *fp;//定义文件流指针，用于打开写操作的文件char ch[2]="\0";//定义一个字符串数组，用于存储读取的字符int i=0;fp = fopen("answer.txt","w");//写方式打开文件a.txtwhile(i < data.length())//逐行读取fp1所指向文件中的内容到text中{ch[0] = data[i++];fputs(ch,fp);//将内容写到fp2所指向文件中}fclose(fp);//关闭文件b.txtcout<<"写入完成......"<<endl;}int main(int argc, char* argv[]){int Page;int Num[10] = {0,0,0,0,0,0,0,0,0,0};string Data;int jishu = 0;read_information(Data);Page = atoi(Data.c_str());cout<<"计算中.\n"<<jishu<<"%"<<endl;;for(int i=1; i<=Page; i++){char sz[10];itoa(i, sz, 10);for(int j=0; sz[j]!='\0'; j++){Num[sz[j]-48]++;}if((int)i/Page*100>jishu){jishu = i/Page*100;cout<<jishu<<"%"<<endl;}}cout<<endl;string answer = "";for (i=0; i<10; i++){char tmp[10];char sz[2];itoa(Num[i], tmp, 10);itoa(i, sz, 10);answer = answer + sz[0];answer = answer + ":";for(int j=0; j<10 && tmp[j]!='\0'; j++){answer = answer + tmp[j];}answer = answer + '\n';}save_information(answer);system("pause");return 0;}字典序问题（P8）（2）最多约数问题（P9）#include "stdafx.h"#include <iostream>#include <string>using namespace std;int yueshuNum(int x){int num = 0;for(int i=1; i<=x; i++){if(x%i == 0){num++;}}return num;}void read_information(string &Data){//从文件中读出停车场信息，并且存放在数组中cout<<"正在读取数据......"<<endl;FILE *fp;char ch;if((fp=fopen("data.txt","rt+"))==NULL){printf("\nCannot open file strike any key exit!");exit(1);}ch=fgetc(fp);while(ch!=EOF){Data = Data + ch;ch=fgetc(fp);}fclose(fp);cout<<"读取完成......"<<endl;}void save_information(string data){//把数组中的停车场信息存放回文件中cout<<"正在写入文件......"<<endl;FILE *fp;//定义文件流指针，用于打开写操作的文件char ch[2]="\0";//定义一个字符串数组，用于存储读取的字符int i=0;fp = fopen("answer.txt","w");//写方式打开文件a.txtwhile(i < data.length())//逐行读取fp1所指向文件中的内容到text中{ch[0] = data[i++];fputs(ch,fp);//将内容写到fp2所指向文件中}fclose(fp);//关闭文件b.txtcout<<"写入完成......"<<endl;}int main(int argc, char* argv[]){int start, end;int Num=0, flag = 1;string data;read_information(data);char tmpstart[10];char tmpend[10];for(int j=0; data[j]!='\0';j++){if(data[j] == ' '){flag = j + 1;}else if(flag == 1){tmpstart[j] = data[j];}else{tmpend[j-flag] = data[j];}}start = atoi(tmpstart);end = atoi(tmpend);for(int i=start; i<=end; i++){int num = yueshuNum(i);if(num > Num){Num = num;}}char answerchar[10];string answer = "";itoa(Num, answerchar, 10);for(i=0; i<10 && answerchar[i]!='\0'; i++){answer = answer + answerchar[i];}save_information(answer);return 0;}（3）最大间隙问题（P10）（4）设计算法求解fibonacci数列的第110项的值，并统计和分析算法的时间性能。