算法设计实验报告_48289.doc

《算法设计》课程报告 课题名称： 算法设计与实现 课题负责人名（学号）： 张樱紫 0743111317 同组成员名单（角色）： 无 指导教师： 左劼 评阅成绩： 评阅意见： 提交报告时间：2009 年 12 月 23 日  算法设计与实现课程设计 软件工程 专业 学生 张樱紫 指导老师 左劼 [摘要] 课程设计报告实现了算法设计课程中5个的主要算法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。每种算法用一个问题描述应用解决，包括源程序代码及执行结果还有算法复杂度以及问题描述，分析、证明，测试数据和运行结果。 关键词：算法设计 分治法 动态规划 贪心算法 回溯法 分支限界法 对计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程。算法实由若干条指令组成的有穷序列，且满足确定性，有限性，输入满足：有零个或多个由外部提供的量作为算法的输入。输出满足：算法产生至少一个量作为输入。通过在课程中，学习掌握了一些主要算法并了解了一些新型算法。 本课程设计报告中，主要实现了五种算法，包括分治法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。下面是每种算法的详细设计实现： 分治法： 问题描述 赛程问题: 有N个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。 ?试用分治法为这N个运动员安排比赛日程。 ?要求每个运动员每天只进行一场比赛， ?。 ?将运动员从1到N编号。 整个赛程，当N为偶数的时候，N-1天能够结束， 而当N为奇数的时候，只能在至少N天结束，、 ?因为，由已知?“每个运动员要和所有其他运动员进行一次比赛”则 每个运动员总共进行N-1场，又由每一场有两个运动员参加，N个运动员就进行了[N*（N-1）]/2，又因为已知“要求每个运动员每天只进行一场比赛”则没人每天只能进行1场，所有运动员为N，每一场由两个运动员参加，当N为偶数的时候，每天只能出现的场数为N/2场,推出至少的天数为/(N/2)=N-1场 ?当N为奇数的时候，由于每个运动员每天只能进行一场，所以每天能进行的总场数最多只能为（N-1）/2场，则整个赛程的天数最少需要 天数 /[(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;?in;?i++) ???????a[i][0]=i+1; for(int?s=0;?sk;?s++)???//?k个阶段，从左到右 ...{ ??????n?/=?2; ?????for(int?t=0;?tn;?t++)?//?每个阶段有t次循环 ?????...{ ??????????for(int?j=m;?j2*m;?j++) ???????????????for(int?i=m;?i2*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行数字组成的数字三角形，如图。设计一个算法，计算出从三角形的顶至底的一条路径，是该路径经过的数字总和最大。 分析设计：动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接求解的子问题，然后一级一级地向上求解。 与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保留已求出问题的解。 满足动态规划需符合的条件 1）最优化原理：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的