《算法设计》课程报告
课题名称: 算法设计与实现
课题负责人名(学号): 张樱紫 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-
算法设计课程报告课题名称算法设计与实现课题负责人名学号张樱紫0743111317同组成员名单角色无指导教师左劼评阅成绩评阅意见提交…
算法设计与分析实验报告实验三贪心算法实验目的1理解贪心算法的概念2掌握贪心算法的基本要素3理解贪心算法与动态规划算法的差异4理解贪…
算法设计与分析实专业班级学生姓名号验报告学一实验目的与要求1熟悉CC语言的集成开发环境2通过本实验加深对递归过程的理解二实验内容掌…
算法设计实验报告一实验内容题目1编程实现常见排序算法如插入排序归并排序快速排序随机化的快速排序等并统计不同输入规模下1组从小到大排…
算法设计与分析实验报告班级姓名学号年月日目录实验一二分查找程序实现03页实验二棋盘覆盖问题分治法08页实验三01背包问题的动态规划…
算法设计与分析实验报告班级姓名学号20xx年11月18日目录实验一二分查找程序实现01页实验二棋盘覆盖问题04页实验三01背包问题…
算法分析与设计实验报告实验报告题目实验一递归与分治策略一实验目的1加深学生对分治法算法设计方法的基本思想基本步骤基本方法的理解与掌…
算法设计与分析实验报告实验一递归与分治策略应用基础学号姓名班级日期20xx20xx学年第1学期第九周一实验目的1理解递归的概念和分…
郑州航空工业管理学院计算机科学与应用系课程设计报告操作系统原理操作系统课程设计目录1题目简述22需求分析221设计思想222要求3…