算法设计实验报告

《算法设计》课程报告

课题名称: 算法设计与实现

课题负责人名(学号): 张樱紫 0743111317 同组成员名单(角色): 无

指导教师: 左劼

评阅成绩:

评阅意见:

提交报告时间:2009 年 12 月 23 日

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法设计与实现课程设计

软件工程 专业

学生 张樱紫 指导老师 左劼

[摘要] 课程设计报告实现了算法设计课程中5个的主要算法,包括分治法,动态规划,贪心算法,回溯法以及分支限界法。每种算法用一个问题描述应用解决,包括源程序代码及执行结果还有算法复杂度以及问题描述,分析、证明,测试数据和运行结果。

关键词:算法设计 分治法 动态规划 贪心算法 回溯法 分支限界法

对计算机科学来说,算法的概念至关重要。通俗的讲,算法是指解决问题的一种方法或一个过程。算法实由若干条指令组成的有穷序列,且满足确定性,有限性,输入满足:有零个或多个由外部提供的量作为算法的输入。输出满足:算法产生至少一个量作为输入。通过在课程中,学习掌握了一些主要算法并了解了一些新型算法。

本课程设计报告中,主要实现了五种算法,包括分治法,包括分治法,动态规划,贪心算法,回溯法以及分支限界法。下面是每种算法的详细设计实现:

一、 分治法:

问题描述

赛程问题: 有N个运动员进行单循环赛,即每个运动员要和所有其他运动员进行一次比赛。

-1-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

?试用分治法为这N个运动员安排比赛日程。

?要求每个运动员每天只进行一场比赛,

?n是偶数时循环进行n-1天,n是奇数时循环进行n天。

?将运动员从1到N编号。

分析、证明

整个赛程,当N为偶数的时候,N-1天能够结束,

而当N为奇数的时候,只能在至少N天结束,、

因为,由已知 “每个运动员要和所有其他运动员进行一次比赛”则 每个运动员总共进行N-1场,又由每一场有两个运动员参加,N个运动员就进行了M=[N*(N-1)]/2,又因为已知“要求每个运动员每天只进行一场比赛”则没人每天只能进行1场,所有运动员为N,每一场由两个运动员参加,当N为偶数的时候,每天只能出现的场数为N/2场,推出至少的天数为M/(N/2)=N-1场。 当N为奇数的时候,由于每个运动员每天只能进行一场,所以每天能进行的总场数最多只能为(N-1)/2场,则整个赛程的天数最少需要 天数 M/[(N-1)/2]=N天

总体思路:按分治策略,将所有分为两半,n个选手可以通过n/2个选手设计的比赛日程表来决定。递归地用一分为二的略对选手进行分割,直到只剩下两个选手。

对于N为奇数的情况可以虚拟多一个选手,使其编程N+1个选手的日程表,最然后忽略虚拟运动员参与的比赛。对于分割时候N/2的情况也做特殊处理, 前n/2轮比赛空选手与下一个未参赛的选手进行比赛

代码实现

void match(int a[][N], int k)

{

int n=1, m=1;

for (int i=1; i<=k; i++)

n *= 2;

for(int i=0; i<n; i++)

-2-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

a[i][0]=i+1;

for(int s=0; s<k; s++) // k个阶段,从左到右

{

n /= 2;

for(int t=0; t<n; t++) // 每个阶段有t次循环

{

for(int j=m; j<2*m; j++)

for(int i=m; i<2*m; i++)

{

a[i-m+2*t*m][j] = a[i+2*t*m][j-m]; a[i+2*t*m][j] = a[i-m+2*t*m][j-m]; }

}

m *= 2;

}

}

测试数据、运行结果

Please input:3

The result is:3

Please input:4

The result is:3

复杂度分析

T(n)∈O(n^2)

二、 动态规划算法:

问题描述:数字三角形问题

给定一个由n行数字组成的数字三角形,如图。设计一个算法,计算出从三角形的顶至底的一条路径,是该路径经过的数字 -3-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

总和最大。

分析设计:动态规划:与分治法相似,把问题分解按层次分成子问题,直到可以直接求解的子问题,然后一级一级地向上求解。 与分治法的出别在于:动态规划适用有许多重复子问题出现的问题,它保留已求出问题的解。

满足动态规划需符合的条件

1)最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。

对于给定的由n行数字组成的数字三角形,计算从三角形的底至顶的路径经过的数字和的最大值。

代码实现与结果:

#include"stdio.h"

void main()

{

int i,j,n,a[100][100]; int M(int n,int a[100][100]); FILE *fp1,*fp2; if((fp1=fopen("input.txt","r"))==NULL) { } fscanf(fp1,"%d",&n); for(i=0;i<n;i++) { -4- printf("file cannot be opened\n"); //exit(1); for(j=0;j<=i;j++) fscanf(fp1,"%d",&a[i][j]); if((fp2=fopen("output.txt","w"))==NULL)

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

} } printf("file cannot be opened\n"); //exit(1); fprintf(fp2,"%d\n",M(n,a));

int M(int n,int a[100][100])

{

}

int MAX(int a,int b)

{

}

/*

-5- int i,j; int m[100][100]; int MAX(int a,int b); for(i=n-1;i>=0;i--) { } return m[0][0]; if(i==n-1) m[i][j]=a[i][j]; else for(j=0;j<=i;j++) m[i][j]=MAX(m[i+1][j]+a[i][j],m[i+1][j+1]+a[i][j]); if(a>=b) return a; return b; else

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

Input:

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

*/

Output:

算法设计实验报告

30

算法复杂度:O(T(n)∈O(n^2))

三、 贪心算法

问题描述:删数问题

给定n位正整数a,去掉其中期任意k≤n个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n为正整数a和正 -6-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

整数k,设计一个算法找出剩下的数字组成的新数最小的删数方案。

分析证明:

贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。

虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解。如单源最短路经问题,最小生成树问题等。 在一些情况下,即使贪心算法不能得到整体最优解,其最终结果却是最优解的很好近似。

满足贪心算法两个基本要素

1)、贪心选择性质:

选择具有无后效性,即不依赖与以后将要作出的选择。

问题的整体最优解可通过一系列的局部最优选择来达到。

证明方法:用归纳法证明此问题的最优解包括一个贪心选择的解。

2)、最优子结构性质

一个问题的最优解包括其子问题的最优解。

算法设计:对于给定的正整数a,计算删去k个数字后得到的最小数。

-7-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

数据输入:第一行是1个正整数a。第二行是正整数k

算法实现代码与结果:

#include <iostream>

using namespace std;

char num[ 100 ];

int s,len,i,j,k;

int main( )

{

cin >> num >> s; len = strlen( num ); for ( i = 0; i < s; i++ ) { for ( j = 0; j < len - 1; j++ ) if ( num[ j ] > num[ j + 1 ] ) { } len--; for ( k = j; k < len - 1; k++ ) num[ k ] = num[ k + 1 ]; break;

-8-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

} } if ( len <= 0 ) cout << 0; else for ( i = 0; i < len; i++ ) cout << num[ i ]; cout<<"\n"; return 0;

算法设计实验报告

算法复杂度:T(n)∈O(n^2)

四、 回溯法

问题描述:工作分配问题

设有 n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法为每一个人都分配1件不同的工作,并使总费用达到最小。

-9-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法设计:设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

输入:第一行有一个正整数n

(1≤n≤20)。接下来的n行,每行n个数,表示工作费用。

分析证明:

回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯;否则,进入该子树,继续按深度优先策略搜索。

算法代码与结果:

#include "stdio.h"

#include "string.h"

#include "malloc.h"

int **aray;

int *list;

int number;

int final_cost=0;

-10-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

int current_cost=0;

void assign(int);

void swap(int*, int*);

void assign(int k){

int i; if(k>=number){ } else{ for(i=k;i<number;i++){ current_cost+=aray[k][list[i]]; if(current_cost<final_cost){ swap(&list[k],&list[i]); assign(k+1); final_cost=current_cost;

swap(&list[k],&list[i]);

} } } } current_cost-=aray[k][list[i]];

-11-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

void swap(int *a,int *b){

}

main()

{

int m; scanf("%d",&m); while(m--) { int temp; temp=*a; *a=*b; *b=temp;

int i,j;

scanf("%d" ,&number);

aray=(int **)malloc(sizeof(int *)*number); list=(int *)malloc(sizeof(int)*number);

for(i=0;i<number;i++)

list[i]=i;

for(i=0;i<number;i++)

aray[i]=(int *)malloc(sizeof(int)*number);

-12-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

for(i=0;i<number;i++)

{

for(j=0;j<number;j++) { } final_cost+=aray[i][i]; scanf("%d",&aray[i][j]);

}

} }

算法设计实验报告

assign(0); printf("%d\n",final_cost); free(list); free(aray);

算法复杂度:T(n)∈O(n^2)

五、 分支限界法

问题描述:在n*n的国际象棋棋盘上摆下n个后,使所有的后都 -13-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

不能攻击到对方,找出所有符合要求的情况。

在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线的棋子。也就是说,n后问题等价于在n×n格的棋盘上放置n个皇后,任何两个皇后不放在同一行或同一列或同一斜线上。n后问题是一个路径问题。国际象棋的规则就是限界函数的约束条件。

分析证明:

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。

在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。

此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

n后问题的解空间树是一棵排列树,一旦一种组合是一种解,则解与解之间不存在优劣的分别。用分支限界法,在解空间树的第一层就会产生n个活结点,如果不考虑剪枝,将在第二层产生n*(n-1)个活结点,如此下去对队列空间的要求太高。n后问题不适合使用 -14-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

分支限界法处理的根源是它需要找处所有解的组合,而不是某种最优解(事实上也没有最优解可言)。分支限界法则可以被这样表述。拿来一个棋盘,摆下一只后;再拿一个棋盘,再摆一只;待到每个棋盘都有一只后以后,每个棋盘又被分解成更多的盘面。 算法实现代码与结果

#include<iostream>

#include<stdio.h>

using namespace std;

const int N=20;

int a_xy[N][2];

long sum;

int n;

void n_queue(int m)

{

int i,j;

if(m>=n)

{

/*

printf("the %ldth method:\n",sum+1);

for(i=0;i<n;i++,printf("\n"))

-15-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

{

for(j=0;j<n;j++)

if(j==a_xy[i][1])printf("* ");

else printf("0 ");

}

for(i=0;i<n;i++)printf("--");

printf("\n");*/

sum++;

return ;

}

bool t1;

for(i=0;i<n;i++)

{

for(j=0,t1=true;j<m;j++)

if(a_xy[j][1]==i||abs(a_xy[j][0]-m)==abs(a_xy[j][1]-i)) {t1=false;break;}

if(t1)

{

a_xy[m][0]=m;

-16-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

a_xy[m][1]=i;

n_queue(m+1);

}

}

}

int main()

{

while(true)

{

printf("please input n:");

scanf("%d",&n);

sum=0;

n_queue(0);

printf("the result is:%ld\n",sum);

}

return 0;

算法设计实验报告

}

-17-

课程名称:算法设计 学生姓名:张樱紫 学生学号:0743111317

算法复杂度: T(n)∈O(n^2)

六、总结:通过本课程的学习,了解了一些基本的算法以及他们的实现和应用,并学会了算法的分析与设计,解决一些基本问题。但更多还有待进一步研究与提高。

参考文献

[1] 计算机算法设计与分析(第三版)王晓东

[2] 算法设计与实验题解 王晓东

[2] 算法分析与设计

-18-

相关推荐