减治法-假币问题减治法-假币问题.docVIP

假币问题 减治法的设计思想就是规模为n的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系： （1）原问题的解只存在于其中一个较小规模的子问题中； （2）原问题的解与其中一个较小规模的解之间存在某种对应关系。 由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。减治法只对一个子问题求解，并且不需要进行解的合并。应用减治法（例如减半法）得到的算法通常具有如下递推式： 所以，通常来说，应用减治法处理问题的效率是很高的，一般是O()数量级。 该算法的时间性能有这样一个递推式： 应用扩展递归技术求解这个递推式，得到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;in;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()。虽然这两个算法的时间复杂度都是对数级别的，但一个是 通过这个例子，我们可以看出：在最好的情况下，我们只要判断最后两个硬币的真假。在最坏的情况下也只是判断了三次(相当于)。我们根据上述的例子画出我们在求解过程中用到的判断树，如下图所示 虽然问题变得复杂了，我们通过减治法还是可以达到O()的效率。