算法设计与分析课后部分习题答案.doc

算法实现题3-7数字三角形问题问题描述：给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务：对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入：有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1=n=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出：程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。输入文件示例输出文件示例input.txtoutput.txt530738810274445265源程序：#includestdio.hvoidmain()intn,triangle100100,i,j;/triangle数组用来存储金字塔数值,n表示行数FILE*in,*out;/定义in，out两个文件指针变量in=fopen(input.txt,r);fscanf(in,%d,&n);/将行数n读入到变量n中for(i=0;in;i+)/将各行数值读入到数组triangle中for(j=0;j=0;row-)/从上往下递归计算for(intcol=0;coltrianglerow+1col+1)trianglerowcol+=trianglerow+1col;elsetrianglerowcol+=trianglerow+1col+1;out=fopen(output.txt,w);fprintf(out,%d,triangle00);/将最终结果输出到output.txt中算法实现题4-9汽车加油问题问题描述：一辆汽车加满油后可行驶nkm。旅途中有若干加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产出一个最优解。编程任务：对于给定的n和k个加油站位置，编程计算最少加油次数。数据输入：由文件input.txt给出输入数据。第1行有2个正整数n和k，表示汽车加满油后可行驶nkm，且旅途中有k个加油站。接下来的1行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。结果输出：将编程计算出的最少加油次数输出到文件output.txt。如果无法到达目的地，则输出NoSolution“。输入文件示例输出文件示例input.txtoutput.txt77412345166源程序：#includestdio.hvoidmain()FILE*in,*out;inti,s,n,k,x100,sum=0;/x数组用来存储距离，sum表示加油次数，s表示加油后行驶的距离in=fopen(input.txt,r);/读入n，k以及距离fscanf(in,%d,&n);fscanf(in,%d,&k);for(i=0;i=k;i+)fscanf(in,%d,&xi);for(i=0;in)printf(NoSolution!);for(i=0,s=0;in)sum+;s=xi;out=fopen(output.txt,w);/输出结果sum到output.txt中fprintf(out,%d,sum);算法实现题5-15最佳调度问题问题描述：假设有n个任务由k个可并行工作的机器来完成。完成任务i需要的时间为ti。试设计一个算法找到出完成这个n个任务的最佳调度，使得完成全部任务的时间最早。编程任务：对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1-n。编程计算完成这n个任务的最佳调度。数据输入：由文件input.txt给出输入数据。第1行有2个正整数n和k。第2行的n个正整数是完成n根任务需要的时间。结果输出：将计算出的完成全部任务的最早时间输出到文件output.txt。输入文件示例输出文件示例input.txtoutput.txt7317214416653源程序：#includestdio.hintlen100,t100,best=1000,n,k;intcomp()/comp函数用来计算完成时间inttmp=0;for(inti=0;itmp)tmp=leni;returntmp;voidsearch(intdep)/search函数用来回溯搜索if(dep=n)inttmp=comp();if(tmpbest)best=tmp;return;for(inti=0;ik;i+)leni+=tdep;if(lenibest)search(dep+1);leni-=tdep;voidmain()FILE*in,*out;in=fopen(input.txt,r);/读入n，k以及每个任务需要时间tifscanf(in,%d,&n);fscanf(in,%d,&k);