算法分析實验六报告.docVIP

《算法设计与分析》实验报告 目 录 实验内容描述和功能分析. 算法过程设计. 程序调试及结果（附截图）. 源代码（附源代码）. 实验内容描述和功能分析. 1.Optimal Services 内容描述：设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ，1 ≤ i ≤ n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n 个顾客等待服务时间的总和除以n。 编程任务：对于给定的n个顾客需要的服务时间，编程计算最优服务次序。 功能分析：输入由多组测试数据组成。 每组测试数据输入的第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。 对应每组输入，输出的每行是计算出的最小平均等待时间。 例如：输入： 10 输出：532.00 56 12 1 99 1000 234 33 55 99 812 汽车加油问题 内容描述：一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。并证明算法能产生一个最优解。 编程任务： 对于给定的n和k个加油站位置，编程计算最少加油次数。 功能分析：输入由多组测试数据组成。每组测试数据输入的第一行有2 个正整数n和k，表示汽车加满油后可行驶n公里，且旅途中有k个加油站。接下来的1 行中，有k+1 个整数，表示第k个加油站与第k-1 个加油站之间的距离。第0 个加油站表示出发地，汽车已加满油。第k+1 个加油站表示目的地。 对应每组输入，输出的每行是计算出的最少加油次数。如果无法到达目的地，则输出”No Solution”。 例如：输入：7 7 输出：4 1 2 3 4 5 1 6 6 算法过程设计. Optimal Services 该问题通过设定一个最大值和两个变量，通过两个变量之间的对比和相关库函数的调用，来实现问题的解决。 汽车加油问题 此问题也设定了一个最大值，还有几个变量，通过条件判断来实现对问题的解决。 三、程序调试及结果（附截图）. 1.Optimal Services 汽车加油问题 四、源代码（附源代码）. 1.矩阵连乘问题 #includestdio.h int main() { int n,i; int j,temp; double a[10001]; double sum,p; while(scanf(%d,n)!=EOF) { p=sum=0; for(i=0;in;i++) scanf(%lf,a[i]); for(i=1;in;i++) for(j=0;jn-i;j++) if(a[j]a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } for(i=0;in;i++) { sum=sum+p+a[i]; p=p+a[i]; } printf(%.2lf\n,sum/n); } return 0; } Pebble Merging #includestdio.h int main() { int n,i,k; int j,flag; int a[10001]; int sum,p; while(scanf(%d%d,n,k)==2) { for(i=0;i=k;i++) scanf(%d,a[i]); sum = 0 ; p = n; flag = 1; for (j = 0;j=k;j++) { if (pa[j]) { flag = 0; break; } p -= a[j]; if (j=k pa[j+1]) { p = n ; sum ++; } } if (flag==1) printf (%d\n , sum); else printf (No Solution\n); } return 0; }