装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。我们要找出这个伪造的硬币。我们有一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同.
第一种方法：比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。
第二种方法：（利用分治算法）
首先，随机选择8个硬币作为为A组，剩下的8个硬币作为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。其次，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。
利用分治策略来解决该问题的话，
#include<stdio.h> #include<stdlib.h> #include<time.h> #define ARRAY_SIZE 16 #define TRUE 1 #define FALSE 0 int CallTimes = 0; // 生成包含 'N' 个硬币重量的数组( 含 1 枚伪币 ), 并返回伪币位置 ... int CreateRandomCoinWeightArray( int *p, int N ) { int i, kt; int TrueCoinWeight, FakeCoinWeight; int IsStop; // 生成随机数种子 ... srand( ( unsigned )time( NULL ) ); // 生成随机真币重量值( 在 50 至 100 之间 ) ... TrueCoinWeight = 50 + rand( ) % ( 100 - 50 ); // 生成随机伪币位置( 在 0 ~ N-1 之间 ) ... kt = rand( ) % N; // 设置真币重量 ... for( i = 0; i < N; i++ ) if ( i != kt ) *( p + i ) = TrueCoinWeight; // 生成 1 个比真币略轻的伪币重量值 ... IsStop = FALSE; while( !IsStop ) { FakeCoinWeight = 50 + rand( ) % ( 100 - 50 ); // 设置满足条件的伪币重量值 ... if ( ( TrueCoinWeight > FakeCoinWeight ) && ( TrueCoinWeight - FakeCoinWeight <= 5 ) ) { IsStop = TRUE; *( p + kt ) = FakeCoinWeight; } } // 返回伪币位置 ... return kt; } // 计算数组中硬币重量和 ... int CalcCoinTotalWeight( int ArrayData[], int kb, int ke ) { int i, TotalWeight = 0; for( i = kb; i <= ke; i++ ) TotalWeight += ArrayData[ i ]; return TotalWeight; } // 采用分治法找到伪币( 假定伪币一定存在且只有 1 枚 ) // kb - (子)数组左边界( begin ) // ke - (子)数组右边界( end ) int FindFakeCoin( int ArrayData[], int kb, int ke ) { int LWeight, RWeight; int flag = 0; CallTimes++; printf( '< 第 %d 次查找 > ', CallTimes ); printf('kb= %d,ke=%d ',kb,ke); LWeight = CalcCoinTotalWeight(ArrayData,kb,kb+(ke-kb)/2); RWeight = CalcCoinTotalWeight(ArrayData,(kb+(ke-kb)/2) + 1,ke); printf('LWeight = %d ', LWeight); printf('RWeight = %d ', RWeight); if(LWeight > RWeight ) { if( ke == kb + 1) { return ke; } printf('RF(%d,%d) ',kb+(ke-kb)/2+ 1,ke); return FindFakeCoin(ArrayData,(kb+(ke-kb)/2) + 1,ke); } else { if(ke == kb +1) { return kb; } printf('LF(%d,%d) ',kb,kb+(ke-kb)/2); return FindFakeCoin(ArrayData,kb,kb+(ke-kb)/2); } } int main(void) { int ArrayData[ ARRAY_SIZE ]; int i, k, FakeCoinPos; // 生成包含 'N' 个硬币重量的数组( 含 1 枚伪币 ), 并返回伪币位置 ... k = CreateRandomCoinWeightArray( ArrayData, ARRAY_SIZE ); // 输出随机数组内容 ... printf( '< 生成的硬币重量数组值为( 含 1 枚伪币 ) > : ' ); for( i = 0; i < ARRAY_SIZE; i++ ) printf( '[%d]-%d ', i+1,ArrayData[ i ] ); printf( ' ' ); printf( '< 第 %d 枚为伪币 > ', ( k + 1 ) ); printf( ' ' ); // 采用分治法找到伪币位置 ... FakeCoinPos = FindFakeCoin( ArrayData, 0, ARRAY_SIZE - 1 ); printf( '< 找到第 %d 枚为伪币 > ', ( FakeCoinPos + 1 ) ); printf( ' ' ); // 等待用户输入任意一键返回 ... system( 'PAUSE' ); return 0; }
问答百科
