算法实验报告

算法设计与分析实验报告

重 庆 交 通 大 学 学 生 实 验 报 告

实验课程名称 算法设计与分析 开课实验室 数学实验室

学院 数学与统计学院 年级13 专业班 信息与计算科学2 学 生 姓 名 辜朕圆 学 号 631322020223 开 课 时 间 2015 至 2016 学年 第 1 学期

假设合理 建模求解全面 结果分析完善 文档清晰 综合成绩 教师姓名

优 优 优 优 良 良 良 良 中 中 中 中 差 差 差 差 韩逢庆 2015-2016学年 第一学期

算法设计与分析实验报告

实验报告题目 实验一 递归与分治策略

开课实验室：数学实验室 指导老师：韩逢庆 时间：2015.9 学院：理学院 专业：信息与计算科学 班级：2013级2班

姓名： 辜朕圆 学号：631322020223

一、 实验目的

1．加深学生对分治法算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、 实验内容

题目 ①设a[0:n-1]是已排好序的数组。请写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

②写出三分搜索法的程序。 三、 实验要求

（1）用分治法求解…问题；

（2 ）再选择自己熟悉的其它方法求解本问题； （3）上机实现所设计的所有算法； 四、 实验过程设计（算法设计过程）

1、已知a[0:n-1]是一个已排好序的数组，可以采用折半查找（二分查找）算法。如果搜索元素在数组中，则直接返回下表即可；否则比较

2015-2016学年 第一学期

算法设计与分析实验报告

搜索元素x与通过二分查找所得最终元素的大小，注意边界条件，从而计算出小于x的最大元素的位置i和大于x的最小元素位置j。 2、先判定输入的数x是否在数组的范围内，再将n个元素分成大致相同的三部分，取在数组a的左三分之一部分中继续搜索x。如果x>a[san2]，则只需在数组a的右三分之一部分中继续搜索x。上述两种情况不成立时，则在数组中间的三分之一部分中继续搜索x。 五、 实验结果分析

(1)例子为数组a[1,2,3,4,5,6,7,8,9],n=9,x=9。

实验结果为

(2)例子为数组a[1,2,3,4,5],x=3,n=5。

实验结果为

时间复杂性：最好情况下，最坏情况下

二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(log n)。（n代表集合中元素的个数） 三分搜索法：O（3log3n） 空间复杂性分析：O（1）。

六、 实验体会

本次试验解决了二分查找和三分查找的问题，加深了对分治法的

2015-2016学年 第一学期

算法设计与分析实验报告

理解，收获很大，同时我也理解到学习算法是一个渐进的过程，算法可能一开始不是很好理解，但是只要多看几遍，再实践操作，毕竟实践是检验真理的唯一标准，只要动手就能感受自己写出算法的喜悦，从而良性循环越学越好。 七、 附录：（源代码）

(1) public static int binarySearch(int a[],int x,int n)

{

int left=0;int right=n-1;int i,j; while(left<=right) {

int middle=(left+right)/2;

if(x==a[middle]){i=j=middle;System.out.println(\);return if(x>a[middle])left=middle+1; else right=middle-1; }

i=right;j=left; return 0; }

1;}

(2)

public class sanfen {

public static int sanSearch(int []a,int x,int n){

int left=0;int right=n-1; while(right>left){

if(xa[right])

{ System.out.println(\根本不在数组里\); break; }

int san1=(left+right)/3; int san2=2*(left+right)/3; if(x==a[san1])

{

System.out.println(\找到了\); return san1; }

else if(xa[san2])left=san1+1;

2015-2016学年 第一学期

算法设计与分析实验报告

else{left=san1;right=fan2;} } }

}

public static void main(String []args) { }

sanfen s=new sanfen(); int []b={1,2,3,4,5}; s.sanSearch(b,3,5); return -1;

实验二 动态规划

一、实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握；

2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。 二、实验内容

(1)设计一个O（n）时间的算法，找出由n个数组成的序列的最长单调递增子序列

(2)考虑下面的整数线性规划问题：maxi?12?cjnii ,i?1?axnii?b

xi为非负整数，1<=i<=n 试设计一个解此问题的动态规划算法，并分

析算法的计算复杂性。 三、实验要求

（1）用动态规划思想求解最优问题；

（2）再选择自己熟悉的程序设计语言实现所有算法； （3）分析所设计的算法的时间/空间复杂性。

2015-2016学年 第一学期

算法设计与分析实验报告

四、实验过程设计（算法设计过程）

(1)用数组b[0:n-1]记录以a[i],0<=i

max{b[k]}?1 据此将计算b[i]长度。序列a的最长递增子序列的长度为0?k?ia[k]?a[i]转化为i个规模更小的子问题。

(2)转化成一般背包问题即可，具体算法过程与背包问题大同小异 五、实验结果分析

(2)六、实验体会

时间复杂度为O(nb)

学会了用动态规划的想法来解决背包问题，为了给出合适的测试数据也是捣鼓了好久，让我知道算法思想重要，他的测试和实现也很重要，这次课题的限制降低很多让我们有更多的思考空间，提升了想象力。 七、附录：（源代码）

(1)int pia() { }

int maxL(int n)

2015-2016学年 第一学期

int i,j,k;

for(i=1,b[0];i

return maxL(n);

for(j=0,k=0;j

b[i]=k-1;

算法设计与分析实验报告

{ }

(2)import java.util.Scanner; public class beibao{

static void knapsack(int n,float c,float[] v,float[]w,float []x) {

Sort(n,v,w); int i;

for(i=1;i<=n;i++) x[i]=0; for(i=1;i<=n;i++) { if(w[i]>c)

break; x[i]=1; c-=w[i]; } if(i<=n)

x[i]=c/w[i]; }

int i,j;

for(i=0;i

Scanner scan =new Scanner(System.in); System.out.println(\输背包中物品的个数：\); int n=scan.nextInt();

System.out.println(\输入背包的容量：\); float c=scan.nextFloat(); float [] v=new float[n+1];

for(int i=0,temp=0;itemp)temp=b[i]; return temp;

static void Sort(int n, float[] v, float[] w) {

if(v[i]/w[i]

public static void main(String[] args) {

float [] w=new float[n+1]; float [] x=new float[n+1]; for(int i=1;i<=n;i++) {

System.out.println(\输入第\+i+\的重量\); w[i]=scan.nextFloat();

System.out.println(\输入第\+i+\的价值\); v[i]=scan.nextFloat();

2015-2016学年 第一学期

算法设计与分析实验报告

}

knapsack(n,c,v,w,x);

System.out.println(\一般背包问题的解为：\); for(int i=1;i<=n;i++)

System.out.print(x[i]+\); } }

实验三 贪心算法

一、实验目的

1．加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。

二、实验内容

1、单源最短路径

2、一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，之处应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。

三、实验要求

（1）用贪心算法思想求解最优问题；

（2）再选择自己熟悉的程序设计语言实现所有算法； （3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

1、设置顶点几何S并不断地做贪心选择来扩充这个集合一个顶点属于s当且仅当源到该顶点的最短路径长度已知，u为g中某个顶点，把从源到u且中间只经过s中顶点的路径称为从源到u的特殊路径，并用dist记录当前每个顶点所对应的最短特殊路径长度。一旦s包含了所有v的点，dist就记录了从源到所有其他顶点之间的最短路径长度。 2、设加油次数为k，每个加油站间距离为a[i]；i=0，1，2，3……n 1.始点到终点的距离小于Ｎ，则加油次数k=0； 2.始点到终点的距离大于N，

① 加油站间的距离相等，即ａ[i]=a[j]=L=N，则加油次数最少k=n； ② 加油站间的距离相等，即ａ[i]=a[j]=L>N，则不可能到达终点；

③ 加油站间的距离相等，即ａ[i]=a[j]=L

④ 加油站间的距离不相等，即ａ[i]！=a[j]，则加油次数k通过下面的算法求解。

五、实验结果分析

2015-2016学年 第一学期

算法设计与分析实验报告

(1)

时间复杂度为O(n)

2(2)时间复杂度为O(n)

六、实验体会

通过这次实验让我感受到独立思考写算法的乐趣，尤其是加油站问题，其中遇到很多困难，但是在和同学们的讨论下，我茅塞顿开，感受到了贪心算法是如何进行他的贪心行为，大大提升了我的编程能力和对贪心算法的理解。 七、附录：（源代码）

(1)public class Dijkstra { static int MAX_SIZE=6;

public static void dijkstra(int v,float[][]a,float[]dist,int[]prev){ int n=dist.length-1; if(v<1||v>n)return;

boolean []s=new boolean[n+1];

for(int i=1;i<=n;i++) { dist[i]=a[v][i]; s[i]=false;

if(dist[i]==Float.MAX_VALUE) prev[i]=0; else prev[i]=v; } dist[v]=0;s[v]=true; for(int i=1;i

for(int j=1;j<=n;j++)

2015-2016学年 第一学期

算法设计与分析实验报告

if((!s[j])&&(dist[j]

temp=dist[j]; } s[u]=true;

for(int j=1;j<=n;j++)

if((!s[j])&&(a[u][j]

public static void main(String args[]){ float a[][]=new float[MAX_SIZE][MAX_SIZE]; float[]dist=new float[MAX_SIZE]; int []prev=new int[MAX_SIZE]; for(int i=0;i<6;i++) for(int j=0;j<6;j++) a[i][j]=Float.MAX_VALUE; a[1][2]=10;

a[1][4]=30;a[1][5]=100;

a[2][3]=50; a[3][5]=10; a[4][3]=20; a[4][5]=60;

int v=1;//假设从顶点1处出发 dijkstra(v,a,dist,prev); System.out.println(\从1出发到2、3、4、5的最短路径依次是:\

for(int j=2;j<6;j++){ System.out.println(dist[j]); } int z=prev[5],y=prev[z],x=prev[y];

System.out.println(\从1到5最短路径经过的点为：\ System.out.print(x+\ (2)public class qiyou {

public static void greedy(int []v,int n,int N){

//定义每个加油站的距离存进数组v，定义加满油可以开n公里 //定义要跑N公里 int s=v.length;

int k=0; //初始化经过加油站的数量k int load=0;//初始化走过的长度 if(N

System.out.println(\不需要加油\ }

for(int i=0;in) {

System.out.println(\还没到加油站就没油了！\ } }

for(int i=0;i

2015-2016学年 第一学期

算法设计与分析实验报告

if(load>n){ k++;

load=v[i-1];//load大于n所以加油点必在i-1 n=n+load; }

System.out.println(\最少加\次油\} }

public static void main(String []args){ qiyou s=new qiyou();

s.greedy(v, n, N);//改这个就能测试 } }

实验四 回溯法

一、实验目的

1．掌握能用回溯法求解的问题应满足的条件； 2．加深对回溯法算法设计方法的理解与应用； 3．锻炼学生对程序跟踪调试能力；

4．通过本次实验的练习培养学生应用所学知识解决实际问题的能力。

二、实验内容

1、对于一个n位正整数a，去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的

正整数。设计一个删数算法，使得剩下的数字组成的正整数最小

2、n皇后问题 三、实验要求。

（1）用回溯法算法设计方法求解问题； （2）上机实现所设计的算法；

（3）分析所设计的算法的时间/空间复杂性。

四、实验过程设计（算法设计过程）

1、一个n位数，删去k位后，也就是剩下一个 n-k位 数，那么这个数要最小，我们就要保证我们我们得出的数是所有删除后得到的数的最小值。问题转换一下，用回溯法的思想如果最后就剩下一位，结果就是这些数字的最小值，最后剩下两位在这个区间（从左往右数第一位，从右往左数第二位），且是其中的最小值，而次最高位在这个区间（刚才最高位+1，从右往左数第一位即是最后一位）；

2、n皇后问题中用完全n叉树表示解空间，约束place减去不满足行列和斜线约束的子树。递归方法backtrack（1）实现对整个解空间的回溯搜索。Backtrack（i）搜索解空间中第i层子树，sum记录当前已找到的可行方案数。

2015-2016学年 第一学期

算法设计与分析实验报告

五、实验结果分析

(1)

例如输入1 7 4 0 9 4 8 8 2 4 5 5 长度为12，删完剩下5.

时间复杂度:0（k*(n-k)）

（2）当a=8即8皇后问题时结果为： sum=98 时间复杂度为o(n!)

六、实验体会

在这个实验中给我印象最深的是n皇后问题，只有n大于三才能进行，并且还有递归和非递归两种形态，而且多个函数的关联最让我着迷，应用backtrack来进行回溯算法，用place来进行判断，环环相扣，使人深陷其中，通过这次实验让我提升了自己的动手能力和对回溯算法的理解能力，最重要的还是老师教的好。 七、附录：（源代码） (1)#include using namespace std ; const int K = 5 ; const int size = 12 ;

void GetMinBit( int * data,int length,int start,int end,int &bit ) {

if( data != NULL || length < 1 ) {

if( 0 <= start && start <= end && end < length ) { int min = *(data+start) ; bit = start;

for( int i=start ; i <= end ; i++ ) { if( *(data+i) < min ) {

2015-2016学年 第一学期

算法设计与分析实验报告

min = *(data+i); bit = i; } } } else

{ cout<<\ system(\ } } else

{ cout<<\ system(\ } }

int GetMinData(int * data,int length,int k ) { if( data != NULL || length < 1 ) {if( 0 <= k && k < length ) { int result = 0 ; int bit = -1 ; int end = k ;

while( end

GetMinBit( data,length,bit+1,end,bit );

result = result*10 + *(data+bit); end++ ; }

return result ; } else {

cout<<\ system(\ } } else {

cout<<\ system(\ } }

int main()

{ int * data = new int[size];

2015-2016学年 第一学期

算法设计与分析实验报告

for(int i= 0 ;i

*(data+i)=rand(); }

for(int j= 0 ;j

cout<<*(data+j)<<\ }

cout<

cout<<\ system(\ return 0; }

(2)递归public static long nQueen(int a) { n=a;sum=0; if(n<3) System.out.println(\皇后问题不可行！\ x=new int[n+1]; for(int i=0;i<=n;i++)x[i]=0; backtrack(1); return sum; } private static boolean place(int k) { for(int j=1;jn)sum++; else for(int i=1;i<=n;i++){x[t]=i;if(place(t))backtrack(t+1); } }

非递归public class NQueen2 { static int n; static int[]x; static long sum;

public static long nQueen(int a) { n=a;sum=0; if(n<3) System.out.println(\皇后问题不可行！\ x=new int [n+1];

2015-2016学年 第一学期

算法设计与分析实验报告

for(int i=0;i<=n;i++)x[i]=0; backtrack(); return sum; }

private static boolean place(int k) { for(int j=1;j

private static void backtrack() { x[1]=0; int k=1; while(k>0){ x[k]+=1; while((x[k]<=n)&&!(place(k)))x[k]+=1; if(x[k]<=n) if(k==n)sum++; else{k++;x[k]=0;} else k--; } } }

2015-2016学年 第一学期

本文来源：https://www.bwwdw.com/article/orvg.html