资源描述:
《算法分析与设计课程总结》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、桂林理工大学算法分析与设计课程总结指导老师:董明刚班级:计本07-3班姓名:覃立泉学号:30704171212010/6/10前言算法设计与分析是一门面向设计,且处于计算机学科核心地位的课程,是计算机软件开发人员必修课,软件的效率和稳定性取决于软件中所采用的算法。对于一般程序员和计算机专业学生,学习算法设计与分析课程,可以开阔编程思路,编写出优质程序。使学生掌握算法设计过程与方法,并学会分析算法的时间复杂度、空间复杂度和稳定性,具有问题抽象和建模的初步能力,培养对算法的计算复杂性正确分析的能力,为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。课程内容包括:
2、算法与程序设计简介、穷举与回溯、递归与分治、递推、贪心算法、动态规划算法等。程序一一问题描叙有3根柱子A,B,C,A柱上有n个盘子,盘子的大小不等,大的盘子在下,小的盘子在上。要求将A柱上的n个盘子移到C柱上,每次只能移动一个盘子。在移动过程中,可以借助于任何一根柱子(A、B、C),但必须保证3根柱子上的盘子都是大的盘子在下,小的盘子在上。二使用的算法递归算法三源代码及思考#includeintq; /*全局变量,统计移动的步数*/voidmove(charx,chary) /*将1个盘子从x柱移到y柱*/{ printf("%c->%c
3、n",x,y);}/*把A柱上的n个盘子借助于B柱移到C柱上*/voidhanoi(intn,charA,charB,charC){ if(n==1) { move(A,C); q++; } else { hanoi(n-1,A,C,B);/*把A柱上的n个盘子借助于C柱移到B柱上*/ move(A,C); /*把A柱上的最后一个盘子移到C柱上*/ q++; hanoi(n-1,B,A,C);/*把B柱上的n个盘子借助于A柱移到C柱上*/ }}intmain(void){ intn; printf("Enterthenumberofdiskes:"
4、); scanf("%d",&n); printf(""); hanoi(n,'A','B','C'); printf("Steps:%d",q); return0;}1个的时候当然是1次,2个的时候是3次,3个的时候就用了7次,因此让我们逻辑性的思考一下吧。4个的时候能够移动最大的4盘时到此为止用了7次。在上面再放上3个圆盘时还要用7次(把3个圆盘重新放在一起需要的次数)。因此,4个的时候是“3个圆盘重新摞在一起的次数”+1次+“3个圆盘重新摞在一起需要的次数”=2x“3个圆盘重新摞在一起的次数”+1次=15次。 那么,n个的时候是2x“(n-
5、1)个圆盘重新摞在一起的次数”+1次。 由于1个的时候是1次,结果n个的时候为(2的n次方减1)次。 1个圆盘的时候2的1次方减1 2个圆盘的时候2的2次方减1 3个圆盘的时候2的3次方减1 4个圆盘的时候2的4次方减1 5个圆盘的时候2的5次方减1 ........ n个圆盘的时候2的n次方减1 也就是说,n=64的时候是(2的64次方减1)次。四运行结果:1个盘子:1步2个盘子:3步3个盘子:7步4个盘子:15步5个盘子:31步6个盘子:63步7个盘子:127步8个盘子:255步9个盘子:511步......n个盘子:2^n-1步程序二一问题
6、描叙一辆汽车加满油后可行驶n千米。旅途中有若干个加油站。若要使沿途加油次数最少,设计一个有效算法,指出应在哪些加油站停靠。二使用的算法贪心算法三源代码及思考#include"stdafx.h"intmain(intargc,char*argv[]){intOilStationNum;//加油站的数目intMaxDist;//汽车加满油以后行驶的最大距离intDiscOfCar;//汽车一次加油后已经行驶的距离intCount;int*OilStationDist;printf("请输入加油站的段数(用整数表示):");scanf("%d",&OilStationN
7、um);printf("------------------------------");printf("汽车加满油以后行驶的最大距离(用整数表示):");scanf("%d",&MaxDist);printf("---------------------------------------");OilStationDist=newint[OilStationNum-1];printf("请输入各各加油站之间的距离(假设不能有环路):");for(Count=0;Count<=OilStationNum-1;){scanf("%d",&OilStati
8、onDis