转载 特别感谢 ：https://blog.csdn.net/weixin_42061805/article/detail/80291662

分治法——见名知意，即分而治之，从而得到我们想要的最终结果。分治法的思想是将一个规模为N的问题分解为k个较小的子问题，这些子问题遵循的原则就是互相独立且与原问题相同。

下面我们就用具体的例子来理解分治法的算法思想。

例题：一个装有 16 枚硬币的袋子，16 枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻。现有一台可用来比较两组硬币重量的仪器，请使用分治法设计一个算法，可以找出那枚伪造的硬币。

我们简单的分析一下这个问题，我们采用一个五五开的思想（类似于二分法）

我们先将16枚硬币分为左右两个部分，各为8个硬币，分别称重，必然得出一半儿轻一半儿重，而我们要的就是轻的那组，重的舍去。接下来我们继续对轻的进行五五分，直至每组剩下一枚或者两枚硬币，这时我们的问题自然就解决了，下面用一张图进行更好的理解。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
 
#define ARRAY_SIZE 16 
#define TRUE       1
#define FALSE      0
 
int CallTimes = 0;
int TrueCoinWeight, FakeCoinWeight;
 
// 生成包含 'N' 个硬币重量的数组( 含 1 枚伪币 ), 并返回伪币位置 ...
int CreateRandomCoinWeightArray( int *p, int N )
{
  int i, kt;
  
  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 )    //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;//初始化重量为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;
  CallTimes++;
  printf( "< 第 %d 次查找 > \n", CallTimes );
  // 请将下面的代码补充完毕, 使程序可以正确运行 ...
  // ......
  //左边重量和 
  LWeight=CalcCoinTotalWeight(ArrayData,kb,kb+(ke-kb)/2);
  //右边重量和 
  RWeight=CalcCoinTotalWeight(ArrayData,kb+(ke-kb)/2+1,ke);
  //取右边子数组
  if((TrueCoinWeight*((ke-kb)/2+1))==LWeight)
  {
  	if(RWeight==FakeCoinWeight)
  	{
		printf("< Success! >\n"); 
		//返回假币位置 
		return ke;  	
    }
    else 
  	FindFakeCoin(ArrayData,kb+(ke-kb)/2+1,ke);
  }
  //取左边子数组 
  else                                        
  {
  	if(LWeight==FakeCoinWeight)
  	{
		printf("< Success! >\n"); 
		//返回假币位置 
		return kb; 	
    }
    else 
  	FindFakeCoin(ArrayData,kb,kb+(ke-kb)/2);
  }  
}

int main()
{
  int ArrayData[ ARRAY_SIZE ];
  int i, k, FakeCoinPos;
 
  // 生成包含 'N' 个硬币重量的数组( 含 1 枚伪币 ), 并返回伪币位置 ...
  k = CreateRandomCoinWeightArray( ArrayData, ARRAY_SIZE );
 
  // 输出随机数组内容 ...
  printf( "< 生成的硬币重量数组值为( 含 1 枚伪币 ) > : \n" );
  for( i = 0; i < ARRAY_SIZE; i++ )
    printf( "第%d枚硬币重量：%d\n",i+1, ArrayData[ i ] );
  printf( "\n" );
  printf( "< 第 %d 枚为伪币 > \n", ( k + 1 ) );
  printf( "\n" );
 
  // 采用分治法找到伪币位置 ...
  FakeCoinPos = FindFakeCoin( ArrayData, 0, ARRAY_SIZE - 1 );
 
  printf( "< 找到第 %d 枚为伪币 > \n", ( FakeCoinPos + 1 ) );
  printf( "\n" );
 
  // 等待用户输入任意一键返回 ...
  system( "PAUSE" );
}

1. 问题描述

• 输入：n片芯片，其中好芯片至少比坏芯片多1片
• 问题：设计一种测试方法，通过测试从n片芯片中挑出1片好芯片
• 要求：使用最少的测试次数

2. 解题思路

1. 判定芯片A的好坏

• 问题：给定芯片A，判定A的好坏
• 方法：用其余n-1片芯片对A测试
  

2. 蛮力算法

• 算法思想：任取1片测试，如果是好芯片，则测试结束；如果是坏芯片，则抛弃，再从剩下芯片中任取1片测试，直到得到1片好芯片
• 时间估计：O($n^2$)
  • 若第1片为坏芯片，则最多测试n-2次
  • 若第2片为坏芯片，则最多测试n-3次;
  • …

3. 分治算法

• 算法思想：假设n为偶数，将n片芯片两两一组做测试淘汰，剩下芯片构成子问题，进入下一轮分组淘汰
  • 淘汰规则
    • “好，好”——任留1片，进入下轮
    • 其他情况——全部抛弃
  • 递归出口：n $\le$ 3
    • 若为3片芯片（2好1坏），则1次测试可得到好芯片
    • 若为1或2片芯片（必为好），不再需要测试
  • 命题：当n是偶数时，在上述淘汰规则下，经过一轮淘汰，剩下的好芯片比坏芯片至少多1片
    
• 算法思想：若n为奇数时，按上述处理可能会出问题
  
  • 解决办法：当n为奇数时，增加一轮对轮空芯片的单独测试。
    • 若该芯片为好芯片，则算法结束
    • 若该芯片为坏芯片，则淘汰该芯片
• 伪码描述
  

3. 时间复杂度分析

• 设输入规模为n，每轮淘汰后，芯片数至少减半，测试次数（含轮空处理）：O(n)
• 时间复杂度： W(n) = W(n/2) + O(n) , W(3)=1, W(2)=W(1)=0, 可得，W(n)=O(n)