现有n枚外观相同的硬币和一架天平，已知硬币中有一枚重量较轻的硬币是假币，要求设计一个高效的算法来检测出这枚假币。请写出分治法求解该问题的详细步骤，并分析其时间复杂性。
现有n枚外观相同的硬币和一架天平，已知硬币中有一枚重量较轻的硬币是假币，要求设计一个高效的算法来检测出这枚假币。请写出分治法求解该问题的详细步骤，并分析其时间复杂性。
参考答案和解析
B 解析：用分治法找假币的过程为：先将16枚硬币对等分为2堆(各8枚)并比较其重量，假币在较轻的那一堆中；然后将8枚硬币对等分为2堆(各4枚)并比较其重量，假币在较轻的那一堆中；再将4枚硬币对等分为2堆(各2枚)并比较其重量，假币在较轻的那一堆中；最后比较两个硬币的重量，找出假币。因此，至少比较4次才能够找出该假币。
相关考题：
：通常认为，抛掷一枚质量均匀的硬币的结果是随机的。但实际上，抛掷结果是由抛掷硬币的冲力和初始高度共同决定的。尽管如此，对抛掷硬币的结果作出准确预测还是十分困难。下面哪一项最有助于解释题干所说到的现象，即抛掷结果被某些因素决定，但预测却很困难（ ）A．很长时间以来，抛掷硬币已被用作随机事件的典型例证B．如果抛掷一枚质量不均匀的硬币。其结果总能够被精确地预测C．如果抛掷硬币的初始高度保持稳定不变。则抛掷硬币的结果将仅由抛掷冲力决定D．对抛掷硬币结果的准确预测，要求极其精确地估计抛掷硬币的初始高度和冲力
阅读下列说明和C代码，回答问题 1 至问题 3，将解答写在答题纸的对应栏内。 【说明】 假币问题：有n枚硬币，其中有一枚是假币，己知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。 【分析问题】 将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 stdio.h 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;ifirst+(last-first)/2;i++){ firstSum+=coins[i]; } For(i=first+(last-first)/2+1;ilast+1;i++){ lastSum+=coins[i]; } If(firstSumlastSum){ return getCounterfeitCoin(coins,first,first+(last-first)/2-1); }else if(firstSumlastSum){ return getCounterfeitCoin(coins,first+(last-first)/2-1,last); }else{ Return( 3 ) } } }【问题一】 根据题干说明，填充C代码中的空（1）-（3） 【问题二】 根据题干说明和C代码，算法采用了（ ）设计策略。 函数getCounterfeitCoin的时间复杂度为（ ）（用O表示）。 【问题三】 若输入的硬币数为30，则最少的比较次数为（ ），最多的比较次数为（ ）。
阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】假币问题：有n枚硬币，其中有一枚是假币，已知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。【分析问题】将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] if((last - first + 1) % 2 ==0){ /*偶数枚硬币*/for(i = first;i lastSum){return getCounterfeitCoin(coins,first+(last-first)/2-1,last);}else{Return( 3 )}}}【问题一】（6分）根据题干说明，填充C代码中的空（1）-（3）【问题二】（4分）根据题干说明和C代码，算法采用了（ ）设计策略。函数getCounterfeitCoin的时间复杂度为（ ）（用O表示）。【问题三】（5分）若输入的硬币数为30，则最少的比较次数为（ ），最多的比较次数为（ ）。
桌子上放有2018枚硬币，小芳、小强两人轮流取走其中一些。当小芳取硬币时，只能取2枚或4枚；当小强取硬币时，只能取1枚或3枚，取走最后一枚硬币的人即为获胜者。假设两人均使用最佳策略，则（ ）能获胜。A.先取者B.后取者C.小芳D.小强
阅读下列说明和C代码，回答问题?1?至问题?3，将解答写在答题纸的对应栏内。【说明】假币问题：有n枚硬币，其中有一枚是假币，己知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分:(1)当n为偶数时，将前后两部分，即?1...n/2和n/2+1...0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币:(2)当n为奇数时，将前后两部分，即1..(n -1)/2和(n+1)/2+1...0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币；若两端重量相等，则中间的硬币，即第?(n+1)/2枚硬币是假币。【问题一】（6分）根据题干说明，填充C代码中的空（1）-（3）【问题二】（4分）根据题干说明和C代码，算法采用了（ ??）设计策略。【问题三】（4分）若输入的硬币数为30，则最少的比较次数为（ ?），最多的比较次数为（ ??）。
问答题编一个程序，把一张1元的钞票换成5分，2分和1分的硬币，要求每种至少一枚，并且所换硬币数不超过30枚。请问，有哪几种换法？