算法设计实验报告

《算法设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称：算法设计学生姓名：张樱紫学生学号：0743111317《算法设计》课程报告课题名称：算法设计与实现课题负责人名（学号）：张樱紫0743111317同组成员名单（角色）：无指导教师：左劼评阅成绩：评阅意见：提交报告时间：2009年12月23日-18-课程名称：算法设计学生姓名：张樱紫学生学号：0743111317算法设计与实现课程设计软件工程专业学生张樱紫指导老师左劼[摘要]课程设计报告实现了算法设计课程中5个的主要算法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。每种算法用一个问题描述应用解决，包括源程序代码及执行结果还有算法复杂

2、度以及问题描述，分析、证明，测试数据和运行结果。关键词：算法设计分治法动态规划贪心算法回溯法分支限界法对计算机科学来说，算法的概念至关重要。通俗的讲，算法是指解决问题的一种方法或一个过程。算法实由若干条指令组成的有穷序列，且满足确定性，有限性，输入满足：有零个或多个由外部提供的量作为算法的输入。输出满足：算法产生至少一个量作为输入。通过在课程中，学习掌握了一些主要算法并了解了一些新型算法。本课程设计报告中，主要实现了五种算法，包括分治法，包括分治法，动态规划，贪心算法，回溯法以及分支限界法。下面是每种算法的详细设计实现：一、分治法：问题描述 赛程问题

3、:有N个运动员进行单循环赛，即每个运动员要和所有其他运动员进行一次比赛。-18-课程名称：算法设计学生姓名：张樱紫学生学号：0743111317•试用分治法为这N个运动员安排比赛日程。•要求每个运动员每天只进行一场比赛，•n是偶数时循环进行n-1天，n是奇数时循环进行n天。•将运动员从1到N编号。分析、证明整个赛程，当N为偶数的时候，N-1天能够结束，而当N为奇数的时候，只能在至少N天结束，、 因为，由已知 “每个运动员要和所有其他运动员进行一次比赛”则每个运动员总共进行N-1场，又由每一场有两个运动员参加，N个运动员就进行了M=[N*（N-1）]/

4、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

5、+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

6、  n /= 2;     for(int t=0; t

7、    }               m *= 2;       }          }测试数据、运行结果 Pleaseinput:3Theresultis:3Pleaseinput:4Theresultis:3复杂度分析 T(n)∈O(n^2)一、动态规划算法：-18-课程名称：算法设计学生姓名：张樱紫学生学号：0743111317问题描述：数字三角形问题给定一个由n行数字组成的数字三角形，如图。设计一个算法，计算出从三角形的顶至底的一条路径，是该路径经过的数字总和最大。分析设计：动态规划：与分治法相似，把问题分解按层次分成子问题，直到可以直接

8、求解的子问题，然后一级一级地向上求解。与分治法的出别在于：动态规划适用有许多重复子问题出现的问题，它保留已求