减治法-假币问题(2)

c，d，e，f，g，h，从八枚硬币中任取六枚a，b，c，d，e，f，在天平两端各放三枚进行比较。假设a，b，c三枚放在天平的一端，d，e，f三枚放在天平的另一端，可能出现三种比较结果：

⑴ a＋b＋c>d＋e＋f ⑵ a＋b＋c＝d＋e＋f ⑶ a＋b＋c

若a＋b＋c>d＋e＋f，可以肯定这六枚硬币中必有一枚为假币，同时也说明g，h为真币。这时可将天平两端各去掉一枚硬币，假设去掉c和f，同时将天平两端的硬币各换一枚，假设硬币b，e作了互换，然后进行第二次比较，比较的结果同样可能有三种：

① a＋e>d＋b：这种情况表明天平两端去掉硬币c，f且硬币b，e互换后，天平两端的轻重关系保持不变，从而说明了假币必然是a，d中的一个，这时我们只要用一枚真币（例如h）和a进行比较，就能找出假币。若a>h，则a是较重的假币；若a＝h，则d为较轻的假币；不可能出现ad＋b可以推出a>d，所以不管a是真是假都不可能出现a

② a＋e＝d＋b：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若c>h，则c是较重的假币；若c＝h，则f为较轻的假币；不可能出现c

③ a＋eh，则b是较重的假币；若b＝h，则e为较轻的假币；不可能出现b

算法伪代码： Check_coin(a[8])

//实现查找8枚硬币中的假币位置，并且判断假币比真币重还是轻 //输入一个整数a[8]

//输出假币在数组的位置i，并且输出Leigh or Heavy

如果两个硬币进行比较，H保留较重硬币的下标，L保留较轻下标 拿较重硬币与真币进行比较：

如果比真币重，则返回这个硬币下标，并且返回Heavy; 否则返回另一个硬币下标，并且返回Light; 我们对上述例子用C语言实现：

#include int flag=0;

int sum_coin(int a[],int from,int to) {

int i,sum=0;

for(i=from;i<=to;i++) sum+=a[i]; return sum; }

int check_coin(int a[],int from,int to)

{

int i,H,L; i=(to+1)%8; if(a[from]>a[to]) {

H=from; L=to; } else {

H=to; L=from; }

if(a[H]>a[i]) {

flag=1; return H; } else {

flag=-1; return L; } }

main() {

int a[8]; int i,p;

for(i=0;i<8;i++) {

printf(\ scanf(\ }

if(sum_coin(a,0,2)==sum_coin(a,3,5)) p=check_coin(a,6,7); else {

if(sum_coin(a,0,2)>sum_coin(a,3,5)) { if((a[0]+a[4])>(a[3]+a[1])) p=check_coin(a,0,3); else { if((a[0]+a[4])==(a[3]+a[1]))

p=check_coin(a,2,5); else p=check_coin(a,1,4); } } else {

if((a[0]+a[4])>(a[3]+a[1])) p=check_coin(a,1,4); else { if((a[0]+a[4])==(a[3]+a[1])) p=check_coin(a,2,5); else p=check_coin(a,0,3); } } }

if(flag==1)

printf(\ else

printf(\ printf(\ system(\}??

通过这个例子，我们可以看出：在最好的情况下，我们只要判断最后两个硬币的真假。在最坏的情况下也只是判断了三次(相当于log2)。我们根据上述的例子画出我们在求解过程中用到的判断树，如下图所示

n

虽然问题变得复杂了，我们通过减治法还是可以达到O(logn2)的效率。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库减治法-假币问题(2)在线全文阅读。