算法设计实验报告.doc

课程名称：算法设计学生姓名：张樱紫学生学号：0743111317算法设计课程报告课题名称： 算法设计与实现课题负责人名（学号）： 张樱紫 0743111317 同组成员名单（角色）： 无 指导教师： 左劼评阅成绩： 评阅意见： 提交报告时间：2009 年 12 月 23 日算法设计与实现课程设计软件工程 专业学生 张樱紫 指导老师 左劼摘要 课程设计报告实现了算法设计课程中5个的主要算法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。每种算法用一个问题描述应用解决，包括源程序代码及执行结果还有算法复杂度以及问题描述，分析、证明，测试数据和运行结果。关键词：算法设计 分治法 动态规划 贪心算法 回溯法 分支限界法对计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程。算法实由若干条指令组成的有穷序列，且满足确定性，有限性，输入满足：有零个或多个由外部提供的量作为算法的输入。输出满足：算法产生至少一个量作为输入。通过在课程中，学习掌握了一些主要算法并了解了一些新型算法。本课程设计报告中，主要实现了五种算法，包括分治法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。下面是每种算法的详细设计实现：一、 分治法：问题描述赛程问题: 有N个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。试用分治法为这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轮比赛空选手与下一个未参赛的选手进行比赛代码实现 voidmatch(intaN,intk).intn=1,m=1;for(inti=1;i=k;i+)n*=2;for(inti=0;in;i+)ai0=i+1;for(ints=0;sk;s+)/k个阶段，从左到右.n/=2;for(intt=0;tn;t+)/每个阶段有t次循环.for(intj=m;j2*m;j+)for(inti=m;i2*m;i+).ai-m+2*t*mj=ai+2*t*mj-m;ai+2*t*mj=ai-m+2*t*mj-m;m*=2;测试数据、运行结果Please input:3 The result is:3Please input:4The result is:3复杂度分析 T(n)O(n2)二、 动态规划算法：问题描述：数字三角形问题 给定一个由n行数字组成的数字三角形，如图。设计一个算法，计算出从三角形的顶至底的一条路径，是该路径经过的数字总和最大。分析设计：动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接求解的子问题，然后一级一级地向上求解。与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保留已求出问题的解。满足动态规划需符合的条件1）最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。对于给定的由n行数字组成的数字三角形，计算从三角形的底至顶的路径经过的数字和的最大值。代码实现与结果：#includestdio.hvoid main()int i,j,n,a100100;int M(int n,int a100100);FILE *fp1,*fp2;if(fp1=fopen(input.txt,r)=NULL)printf(file cannot be openedn);/exit(1);fscanf(fp1,%d,&n);for(i=0;in;i+)for(j=0;j=0;i-) for(j=0;j=b)return a;elsereturn b;/*Input： 573 88 1 02 7 4 44 5 2 6 5*/ Output：30算法复杂度：O(T(n)O(n2)三、 贪心算法问题描述：删数问题给定n位正整数a,去掉其中期任意kn个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n为正整数a和正整数k，设计一个算法找出剩下的数字组成的新数最小的删数方案。分析证明：贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。满足贪心算法两个基本要素1)、贪心选择性质：选择具有无后效性，即不依赖与以后将要作出的选择。问题的整体最优解可通过一系列的局部最优选择来达到。证明方法：用归纳法证明此问题的最优解包括一个贪心选择的解。2)、最优子结构性质一个问题的最优解包括其子问题的最优解。算法设计：对于给定的正整数a，计算删去k个数字后得到的最小数。数据输入：第一行是1个正整数a。第二行是正整数k算法实现代码与结果：#include 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 num j + 1 ) for ( k = j; k len - 1; k+ ) num k = num k + 1 ; break; len-; if ( len = 0 ) cout 0; else for ( i = 0; i len; i+ ) cout num i ; cout=number)final_cost=current_cost;elsefor(i=k;inumber;i+)current_cost+=arayklisti;if(current_costfinal_cost)swap(&listk,&listi);assign(k+1); swap(&listk,&listi);current_cost-=arayklisti;void swap(int *a,int *b)int temp;temp=*a;*a=*b;*b=temp;main()int m;scanf(%d,&m);while(m-) int i,j; scanf(%d ,&number);aray=(int *)malloc(sizeof(int *)*number);list=(int *)malloc(sizeof(int)*number); for(i=0;inumber;i+)listi=i; for(i=0;inumber;i+)arayi=(int *)malloc(sizeof(int)*number);for(i=0;inumber;i+) for(j=0;jnumber;j+)scanf(%d,&arayij);final_cost+=arayii; assign(0);printf(%dn,final_cost);free(list);free(aray);算法复杂度：T(n)O(n2)五、 分支限界法问题描述：在n*n的国际象棋棋盘上摆下n个后，使所有的后都不能攻击到对方，找出所有符合要求的情况。在nn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线的棋子。也就是说，n后问题等价于在nn格的棋盘上放置n个皇后，任何两个皇后不放在同一行或同一列或同一斜线上。n后问题是一个路径问题。国际象棋的规则就是限界函数的约束条件。分析证明：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。n后问题的解空间树是一棵排列树，一旦一种组合是一种解，则解与解之间不存在优劣的分别。用分支限界法，在解空间树的第一层就会产生n个活结点，如果不考虑剪枝，将在第二层产生n*(n-1)个活结点，如此下去对队列空间的要求太高。n后问题不适合使用分支限界法处理的根源是它需要找处所有解的组合，而不是某种最优解（事实上也没有最优解可言）。分支限界法则可以被这样表述。拿来一个棋盘，摆下一只后；再拿一个棋盘，再摆一只；待到每个棋盘都有一只后以后，每个棋盘又被分解成更多的盘面。算法实现代码与结果#include#includeusing namespace std;const int N=20;int a_xyN2;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;in;i+,printf(n) for(j=0;jn;j+) if(j=a_xyi1)printf(* ); else printf(0 ); for(i=0;in;i+)printf(-); printf(n);*/ sum+; return ; bool t1; for(i=0;in;i+) for(j=0,t1=true;jm;j+) if(a_xyj1=i|abs(a_xyj0-m)=abs(a_xyj1-i) t1=false;break; if(t1) a_xym0=m; a_xym1=i; n_queue(m+1); int main() while(true) p