发布时间 : 星期四 文章2017年上半年软件设计师下午真题试卷更新完毕开始阅读54f68a475beef8c75fbfc77da26925c52cc591a0
【分析问题】
将n枚硬币分成相等的两部分:
(1)当n为偶数时，将前后两部分，即 1。。。n/2和n/2+1。。。0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币: (2)当n为奇数时，将前后两部分，即1。。(n -1)/2和(n+1)/2+1。。。0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币；若两端重量相等，则中间的硬币，即第 (n+1)/2枚硬币是假币。 【C代码】
下面是算法的C语言实现，其中: coins[]： 硬币数组
first，last：当前考虑的硬币数组中的第一个和最后一个下标 #include
int getCounterfeitCoin(int coins[]， int first，int last) {
int firstSum = 0，lastSum = 0; int ì;
if(first==last-1){ /*只剩两枚硬币*/
if(coins[first] < coins[last]) return first; return last; }
if((last - first + 1) % 2 ==0) {
/*偶数枚硬币*/ for(i = first;i <( 1 );i++){ firstSum+= coins[i]; }
for(i=first + (last-first) / 2 + 1;i < last +1;i++){
lastSum += coins[i]; }
if( 2 ){
Return getCounterfeitCoin(coins,first,first+(last-first)/2;) } else{
Return getCounterfeitCoin(coins,first+(last-first)/2+1,last;) } } else {
/*奇数枚硬币*/
for(i=first;i firstSum+=coins[i]; } for(i=first+(last-first)/2+1;i lastSum+=coins[i]; } if(firstSum return getCounterfeitCoin(coins,first,first+(last-first)/2-1); } else if(firstSum>lastSum){ return getCounterfeitCoin(coins,first+(last-first)/2-1,last); } else{ Return( 3 ) } } } 问题 问题：根据题干说明，填充C代码中的空（1）-（3） 问题：根据题干说明和C代码，算法采用了（）设计策略。 函数getCounterfeitCoin的时间复杂度为（）（用O表示）。 问题：若输入的硬币数为30，则最少的比较次数为（），最多的比较次数为（）。 答案解析： 问题1 （1）first+(last-first)/2 或(first+last)/2 （2）firstSum （6）2 （7）4 试题分析：若输入30个硬币，找假硬币的比较过程为： 第1次：15 比 15，此时能发现假币在15个的范围内。 第2次：7 比 7，此时，如果天平两端重量相同，则中间的硬币为假币，此时可找到假币，这是最理想的状态。 第3次：3 比 3，此时若平衡，则能找出假币，不平衡，则能确定假币为3个中的1个。 第4次：1 比 1，到这一步无论是否平衡都能找出假币，此时为最多比较次数。 第6题 阅读下列说明和 Java代码，将应填入 (n) 处的字句写在答题纸的对应栏内。 【说明】某快餐厅主要制作并出售儿童套餐，一般包括主餐(各类比萨)、饮料和 玩具，其餐品种类可能不同，但其制作过程相同。前台服务员 (Waiter) 调度厨师制作套餐。现采用生成器 (Builder) 模式实现制作过程，得到如图 6-1 所示的类图。 【Java代码】 class Pizza{ private String parts； public void setParts(String parts) { this。parts = parts; } public String toString() { return this。parts; } } abstract class PizzaBuilder{ protected Pizza pizza; public Pizza getPizza() { return pizza; } public void createNewPizza() { pizza = new Pizza(); } public (1) ; } class HawaiianPizzaBuilder extends PizzaBuilder{ public void buildParts(){