2022年软件设计师几个历届的题目 .pdf

软件设计师（数据结构算法C）来源： 问题：有一个赛道全长为S m，要求安排一部分队员进行接力跑步，每位队员只能上场一次，不能中途休息，请用贪心思想安排队员，用最短的时间跑完全程。现有n 位队员110.,nppp,供选择， 各位队员的跑步平均速度是011,nv vvm/s(假设速度值已从大到小排序 )，在此速度下各位队员能持续的时间为011, ,nttt秒。#include stdio.h #include math.h #define eps 1e-8 double fn(int S,int v,int t,int n) double time; int i; int sum_s=0; / 跑的赛道米数int sum_t=0;/ 持续秒数for(i=0;in;i+) if( sum_sS )/第 1 个空 sum_s+= vi*ti ; /第 2 个空sum_t+=ti;/ 累积持续时间 else break; if( sum_s=0 ) /第 3 个空return -1.0; else time=sum_t-( sum_s-S )/(double)vi; / 第 4 个空return time; int main() int S,n,i; /定义赛道的长度，队员数量名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - int v100,t100; / 定义平均速度与持续速度变量double time;/ 定义时间变量scanf(%d%d,&S,&n);/输入赛道长度跟队员数量for(i=0;in;i+) scanf(%d%d,&vi,&ti);/输入每个队员的平均速度和持续时间time=fn(S,v,t,n);/ 调用函数if(abs(time+1.0)eps) printf( 没有足够队员！n); else printf( 跑完全程需要的最短时间为：%lf sn,time); 问题 1：请填写上面代码中的空格（1）(4) 问题 2：根据对以上代码的分析，作出函数fn() 的流程图。并用文字描述贪心思想解决本题的过程。开始定义：doubletimeint iint sum s=0int sum t=0insum_sS判断是否满足条件sum_s+=vi*tisum_t+=ti进行平均时间和速度的累加结束sum_s=0判断平均时间return -1.0返回不合法的值time=sum_tsum_s-S/(double)vi 计算最短时间YNYN流程图贪心思想：贪心算法总是做出在当前看来最好的选择。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。 虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。根据贪心算法的概念1.输入已经排好序的速度，赛道长度，运动员，持续时间2.取每次跑的最快的运动员的速度和持续时间进行累计，求出最短时间，总用时减去超出的路程的用时3.最后输出跑完路程的用时时间问题 3：若有 7 位队员，速度分别为：9，8，8，7，6，6，5；时间分别为：10，20，15，40，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 100，110，1000。赛道长度1000m，则最短时间为多少秒（保留两位小数）。答：最短时间为143.33 秒问题 4：分析函数fn()的时间复杂度是什么？答：函数 fn() 的时间复杂度是O(n) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -