减治法-假币问题.doc

假币问题
减治法的设计思想就是规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：
（1）原问题的解只存在于其中一个较小规模的子问题中；
（2）原问题的解与其中一个较小规模的解之间存在某种对应关系。
由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。一旦建立了这种关系，我们既可以从顶至下（递归地），也可以从底至上（非递归地）地来运用该关系。减治法有3种主要的变种：
a)减去一个常量；
b)减去一个常量因子；
c)减去的规模是可变的。
减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式：

所以，通常来说，应用减治法处理问题的效率是很高的，一般是O()数量级。
本文主要讲的是假币问题。这是一个经典的数学谜题，曾在Beasley(1990)及赵文敏(1995)所著的趣味数学书中介绍过，其本质与Bundy(1996)所讨论的Odd Ball Problem属同类问题，但三人的解法不一样。在识别假币问题的多种版本中，我们考虑最能够体现出减常因子策略的那个版本——单假币问题。
在n枚外观相同的硬币中，有一枚是假币，并且已知假币较轻。可以通过一架天平来任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少。我们的问题是，要求设计一个高效的算法来检测出这枚假币。该问题的一个较简单的版本——就是我们这里所讨论的——假设假币比真币重还是比真币轻是已知的（我们假设假币较轻）。它的复杂版本我们会在后面做详细的介绍。
解决这个简化版假币问题的最自然的思路是把n枚硬币分成两堆，每堆有枚硬币，如果n为奇数的话，就留下一枚额外的硬币，然后把两堆硬币放在天平上。如果两堆硬币重量相同，那么放在旁边的硬币就是假币；否则我们可以用同样的方式对较轻的一堆硬币进行处理，这堆硬币中一定包含那枚假币。注意，即使我们把硬币分成了两个子集，但在每次称重之后，我们只需要解决一个规模为原来一半的问题。所以，根据我们对设计技术的分类，它是一个减（减半）治算法而不是一个分治算法。
算法伪代码如下：
Check_Coin_2(a[n])
//实现用来查找数组中假币位置的算法
//输入：一个整数数组a[n]
//输出：假币所在的数组位置i；
if(n>1)
if(n为偶数)
把n分成两堆数量相等的硬币；
把两堆硬币称重，对重量较轻的那堆进行Check_Coin_2处理；
else
留下一个额外硬币，再把n-1分成两堆数量相等的硬币；
把两堆硬币称重，
如果两堆重量相等，返回额外硬币的位置i；
如果两堆重量不相等，对重量较轻的那堆进行Check_Coin_2处理；
if(n==1)
return最后一个硬币的位置i；
我们对算法用C语言进行实现：
#include <stdio.h>
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_2(int a[],int from,int to)
{
int i,n=to-from+1;
if(n==1)
return from;
else
{
if(n%2==0)
{
if(sum_coin(a,from,from+n/2-1)==sum_coin(a,to-n/2+1,to))
return from-1;
else
{
if(sum_coin(a,from,from+n/2-1)<sum_coin(a,to-n/2+1,to))
check_coin_2(a,from,from+n/2-1);
else
check_coin_2(a,to-n/2+1,to);
}
}
else
check_coin_2(a,from+1,to);
}
}
main()
{
int a[100];
int i,n,p;
printf("please input n:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
p=check_coin_2(a,0,n-1);
printf("the false coin is %d\n",p);
system("pause");
}

该算法的时间性能有这样一个递推式：

应用扩展递归技术求解这个递推式，得到T(n)=O()。
这个递推式基本上和最坏情况下折半查找的比较次数的递推式是相同的（所不同的是初始条件）。这种相似性并不令人惊讶，因为这两种算法都是基于相同的设计技术，把问题的减半。
目前为止，这些内容看上去都是很初级，实际上，该算法并不是最高效的解法。考虑不是把硬币分成两组，而是分成三组，前两组有组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组进行处理；如果前两组的重量不同，则假币一定在较轻的那一组中，用同样的方法对较轻的那组硬币进行处理。所以，根据我们对设计技术的分类，它是一个减治算法而且是三分法。
算法伪代码如下：
Check_Coin_3(a[n])
//实现用来查找数组中假币位置的算法
//输入：一个整数数组a[n]
//输出：假币所在的数组位置i；
if(n==1)
return 假币的位置i;
else
把n分成、、n-2三堆硬币；
把前两堆硬币称重，
如果两堆硬币重量相等，对等三堆硬币进行Check_Coin_3处理；
如果两堆硬币重量不相等，对重量较轻的那堆进行Check_Coin_3处理；
我们对算法用C语言实现：
#include <stdio.h>
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_3(int a[],int from,int to)
{
int i,mid1,mid2,n=to-from+1;
if(n==1)
return from;
else
{
if(n%3==0)
i=n/3;
else
i=n/3+1;
mid1=from+i-1;
mid2=mid1+i;
if(sum_coin(a,from,mid1)==sum_coin(a,mid1+1,mid2))
check_coin_3(a,mid2+1,to);
else
{
if(sum_coin(a,from,mid1)<sum_coin(a,mid1+1,mid2))
check_coin_3(a,from,mid1);
else
check_coin_3(a,mid1+1,mid2);
}
}
}
main()
{
int a[100];
int i,n,p;
printf("please input n:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
p=check_coin_3(a,0,n-1);
printf("the false coin is %d\n",p);
system("pause");
}

该算法的时间性能有这样一个递推式：

应用扩展递归技术求解这个递推式，得到T(n)=O()。虽然这两个算法的时间复杂度都是对数级别的，但是一个是，一个是的，当n很大时，三分法明显比减半法要好的多。
接下来我们考虑假币问题的一个更复杂的版本——不知道假币与真币相比较轻还是较重。我们来举一个例子，假设有八枚硬币，其中有一枚硬币是假币。但是我们不知道假币是比真币重还是轻。先把八枚硬币编号，分别表示为a，b，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<d＋e＋f
若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为较轻的假币；不可能出现a<h的情况。（为什么？很简单，因为我们判断了a，d中有一个假币那么e，b都是真币，则e＝d。而a＋e>d＋b可以推出a>d，所以不管a是真是假都不可能出现a<h情况出现）
② a＋e＝d＋b：此时天平两端由不平衡变为平衡，表明假币一定在去掉的两枚硬币c，f中，同样用一枚真币（例如h）和c进行比较，若c>h，则c是较重的假币；若c＝h，则f为较轻的假币；不可能出现c<h的情况。
③ a＋e<d＋b：此时表明由于两枚硬币b，e的对换，引起了两端轻重关系的改变，那么可以肯定b或e中有一枚是假币，同样用一枚真币（例如h）和b进行比较，若b>h，则b是较重的假币；若b＝h，则e为较轻的假币；不可能出现b<h的情况。
算法伪代码：
Check_coin(a[8])
//实现查找8枚硬币中的假币位置，并且判断假币比真币重还是轻
//输入一个整数a[8]
//输出假币在数组的位置i，并且输出Leigh or Heavy
如果两个硬币进行比较，H保留较重硬币的下标，L保留较轻下标
拿较重硬币与真币进行比较：
如果比真币重，则返回这个硬币下标，并且返回Heavy;
否则返回另一个硬币下标，并且返回Light;
我们对上述例子用C语言实现：
#include <stdio.h>
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("a[%d]=",i);
scanf("%d",&a[i]);
}
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("the false coin is Heavy.\n");
else
printf("the false coin is Light.\n");
printf("the false coin is %d.\n",p);
system("pause");
}

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

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