分治-环法自行车赛-实验指导书

一：环法自行车赛（一）基本信息自行车的驱动系统包含很多齿轮。齿轮通常分成两组：前端齿轮（通常2至3个齿轮组成）和后端齿轮（通常5至10个齿轮组成）。自行车就是通过链接一个前端齿轮和一个后端齿轮来驱动的。设有f个前端齿轮，r个后端齿轮；每个前端齿轮i有m[i]个齿，i=1,2,3,……f，每个后端齿轮有n[j]个齿，j=1,2,3……r。所有共有f*r个可能得驱动率d[k]=n[j]:m[i]，其中k=1,2,3.....f*r；j=1,2,……r；i=1,2,3,……f。假定d排好序，这样数组d中有两个相邻元素d1和d2,不存在d3使得d1d3d2的条件。由此可计算出自行车速度spread[1,2.....f*r-1]数组：spread[k]=d[k+1]/d[k],k=1,2,3……f*r-1，求自行车的最大速度。假定每组齿轮数不多于10个，每个齿轮的齿子数大于10且小于100。（二）任务描述本问题可以形式化为：输入：正整数f，前端齿轮数；正整数r，后端齿轮数；数组m[1,2,……f]，f个前端齿轮的齿子数；数组n[1,2,……r]，r个后端齿轮的齿子数；输出：根据数组m和n计算出spread[1,2.....f*r-1]数组中的最大值。（三）指导内容1、相关知识：（1）排序算法基本思想（2）选择最大数的基本思想（3）算法的时间复杂度。2、过程与步骤：（1）分析题目任务。（2）写出排序算法和选择最大数算法的伪代码及实现程序。（3）给出测试程序，验证算法。（4）分析算法的时间复杂度，改进算法。（四）成果提交提交实验报告；项目报告中需给出主要的程序及伪代码，程序运行结果截图，并给出算法时间复杂度的分析过程。（五）考核方式与标准1、考核方法在指定日期之前提交实验报告。2、考核标准本项目满分50分。标准：根据程序、报告完成的质量、运行结果（1）程序编制规范，运行结果、算法时间复杂度分析正确。40-50分（2）按要求完成程序，运行结果、算法时间复杂度分析基本正确。30-40分（3）设计思路基本正确，程序编制不规范，运行结果、算法时间复杂度分析基本正确。20-30分（4）算法设计考虑不周全，运行结果、算法时间复杂度分析有部分错误。10-20分（5）算法设计考虑不周全，运行结果、算法时间复杂度分析错误较多。1-10分（6）其它情况0分