当前位置：文档之家 › 算法设计与分析实验报告

算法设计与分析实验报告

  • 格式：doc
  • 大小：184.50 KB
  • 文档页数：20

算法设计与分析实验报告 指导老师：沙莎 学 院：信息科学与工程学院 班 级：计科0508 姓 名：戚婕 学 号：10

完成日期：2007年12月 目 录 实验一 分治法 ………………………………………………………………………… 2 实验要求 ……………………………………………………………………… 2 实验内容 ……………………………………………………………………… 2 核心算法 ……………………………………………………………………… 2 程序代码 ……………………………………………………………………… 4 实验结果 ……………………………………………………………………… 8

实验二 贪心法 ……………………………………………………………………… 10 实验要求 …………………………………………………………………… 10 实验内容 …………………………………………………………………… 10 核心算法 …………………………………………………………………… 10 程序代码 …………………………………………………………………… 12 实验结果 …………………………………………………………………… 18

实验三 动态规划 ………………………………………………………………… 20

实验要求 …………………………………………………………………… 20 实验内容 …………………………………………………………………… 20 核心算法 …………………………………………………………………… 20 程序代码 …………………………………………………………………… 21 实验结果 …………………………………………………………………… 24

实验四 深度优先搜索 …………………………………………………………… 26

实验要求 …………………………………………………………………… 26 实验内容 …………………………………………………………………… 26 核心算法 …………………………………………………………………… 26 程序代码 …………………………………………………………………… 27 实验结果 …………………………………………………………………… 28

实验五 回溯法 ……………………………………………………………………… 30

实验要求 …………………………………………………………………… 30 实验内容 …………………………………………………………………… 30 核心算法 …………………………………………………………………… 30 程序代码 …………………………………………………………………… 31 实验结果 …………………………………………………………………… 33 实验一 分治法 一.实验要求 了解用分治法求解的问题：当要求解一个输入规模为n，且n的取值相当大的问题时， 如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中1子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。 掌握分治法的一般控制流程。 DanC(p,q)

global n，A[1:n]; integer m,p,q; 验内容 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。 输入10组相同的数据，验证排序结果和完成排序的比较次数。 与复杂性函数所计算的比较次数比较。 用表格列出比较结果。 给出文字分析。

三.程序算法 1. 归并排序算法 procedure MERGESORT(low，high) 快速排序算法 QuickSort(p,q)

序代码 归并排序 #include<> #include<> #include<> #include<> #define M 11 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[M]; class guibing{ public: guibing(sqlist b) { for(int i=0;ir[i]=b[i]; } void output(sqlist r,int n) { for(int i=0;icoutb[j].key) k=j; if(k!=i) { rec temp=b[k]; b[k]=b[i]; b[i]=temp; } } } void merge(int l,int m,int h,sqlist r2) { xuanze(r,l,m); xuanze(r,m,h); output(r,M); int i,j,k; k=i=l; for(j=m;i{ if(r[i].key<=r[j].key) { r2[k]=r[i]; i++; } else { r2[k]=r[j]; j++; } output(r2,M); } while(j{ r2[k]=r[j]; j++; k++; } while(i<=m) { r2[k]=r[i]; i++; k++; } output(r2,M); } private: sqlist r; }; void main() { cout<<"guibingfa1运行结果:\n"; sqlist a,b; int i,j=0,k=M/2,n=M; srand(time(0)); for(i=0;i{ a[i].key=rand()%80;b[i].key=0; } guibing gx(a); cout<<"排序前数组:\n"; (a,M); cout<<"数组排序过程演示:\n"; (j,k,n,b); cout<<"排序后数组:\n"; (b,M); (); } 快速排序 #include<> #include<> #include<> #include<> #define MAXI 10 typedef int KeyType; typedef int ElemType; struct rec{ KeyType key; ElemType data; }; typedef rec sqlist[MAXI]; class kuaisu { public: kuaisu(sqlist a,int m):n(m) { for(int i=0;i} void quicksort(int s,int t) { int i; if(si=part(s,t); quicksort(s,i-1); quicksort(i+1,t); } else return; } int part(int s,int t) { int i,j; rec p; i=s;j=t;p=b[s]; while(i{ while(i=j--; b[i]=b[j]; while(ib[j]=b[i]; } b[i]=p; output(); return i; } void output() { for(int i=0;icout

void main() { cout<<"运行结果:\n"; sqlist a1; int i,n=MAXI,low=0,high=9; srand(time(0)); for(i=0;ia1[i].key=rand()%80; kuaisu px(a1,n); cout<<"数组排序过程演示:\n"; (low,high); cout<<"排序后数组:\n"; (); (); }

五.实验结果 归并排序

合集下载

算法设计与分析实验报告

算法设计与分析实验报告

实验一排序算法设计一、实验内容冒泡排序二、实验问题分析该问题主要涉及到了指针和循环和相互比较的方法，是综合知识的应用。

三、数学模型根据题目要求，依次对每个数据进行比较，直至得出最后结果。

如果a>b则交换位置，如果a<b则不交换。

四、程序流程图五、源代码#include <stdio.h>void sort(int a[]){int temp;for(int i=0;i<9;i++){for(int j=0;j<10-i-1;j++){if(a[j]>a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}printf("排序后的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");}void main(){int a[10];for(int i=0;i<10;i++){scanf("%d",&a[i]);}printf("排序前的数据\n"); for(i=0;i<10;i++){if(i==5){printf("\n");}printf("%d ",a[i]);}printf("\n");sort(a);}六、测试结果实验二递归算法设计一、实验内容1.判断S字符是否为“回文”的递归函数，并编写程序测试。

二、实验问题分析递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法。

递归算法设计，就是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题，在逐步求解小问题后，再返回（回溯）得到大问题的解。

算法设计与分析实验报告(模版)

算法设计与分析实验报告(模版)

武汉工程大学计算机科学与工程学院《算法设计与分析》实验报告专业班级实验地点学生学号指导教师学生姓名实验时间实验项目算法基本工具和优化技巧实验类别基本性实验实验目的及要求目的与要求：练习算法基本工具和优化技巧的使用实验内容要点：1、熟悉循环和递归的应用2、熟悉数据结构在算法设计中的应用3、了解优化算法的基本技巧4、掌握优化算法的数学模型成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成实验设计任务30分实验报告及时递交、填写规范内容完整、体现收获70分说明：评阅教师：日期：年月日一、狼找兔子问题：一座山周围有n个洞，顺时针编号为0，1，2.，…，n-1。

一只狼从0号洞开始，顺时针方向计数，每当经过第m个洞时，就进洞找兔子。

输入m,n，问兔子有没有幸免的机会？如果有，该藏哪里？代码设计：。

结果：。

二、有52张牌，使他们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下，正面朝下的翻成正面朝上；第三轮从第4张开始，凡是4的倍数位置上的牌，正面朝上的翻成正面朝下，正面朝下的翻成正面朝上，以此类推，直到翻的牌超过104张为止。

统计最后有几张正面朝上，以及他们的位置号。

代码设计：。

结果：。

三、A、B、C、D、E 5人为某次竞赛的前5名，他们在名次公布前猜名次。

A说：B得第三名，C得第五名。

B说：D得第二名，E得第四名。

C说：B得第一名，E得第四名。

D说：C得第一名，B得第二名。

E说：D得第二名，A得第三名。

结果每个人都猜对了一半，实际名次是什么呢？代码设计：。

结果：。

算法设计与分析实验报告

算法设计与分析实验报告

算法设计与分析实验报告姓名：班级：计算机科学与技术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;}。

算法课设实验报告(3篇)

算法课设实验报告(3篇)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- 编写贪心算法的代码。

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

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

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

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

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

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

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

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

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

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