위조 화폐 문제

본 제 는 분 치 법 을 사 용 했 기 때문에 먼저 분 치 법의 사상 을 소개 하 겠 습 니 다.
분 치 법의 기본 사상 은 하나의 규모 가 n 인 문 제 를 k 개의 규모 가 작은 서브 문제 로 분해 하 는 것 이다. 이런 서브 문 제 는 서로 독립 되 고 원래 의 문제 와 같다. 재 귀 적 으로 이런 서브 문 제 를 해결 한 다음 에 각 서브 문제 의 해 제 를 합병 하여 원래 의 문 제 를 해결 하 는 것 이다.
(사실은 큰 문 제 를 끊임없이 나 누 어 하나씩 해결 하 는 것 이다)
제목: 16 개의 동전 이 설치 되 어 있 는데 그 중 하 나 는 위 폐 이 고 진짜 화폐의 무 게 는 똑 같 습 니 다. 위 폐 의 질 은 진짜 화폐 보다 가 볍 습 니 다. 지금 그 위 폐 를 찾 아야 합 니 다.
분석: 16 개의 동전 을 우 리 는 두 조로 나 누 어 질 이 작은 쪽 을 계산 한 다음 에 계속 나 누 어 마지막 에 이 위 폐 를 찾 을 수 있 기 때문에 우 리 는 분 치 법 으로 구 할 수 있다.
다음은 코드 입 니 다.
핵심 코드

//        ...
#include < stdio.h >
#include < stdlib.h >
#include < time.h >

#define ARRAY_SIZE 16
#define TRUE       1
#define FALSE      0

int CallTimes = 0;
int t;

//      '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 )//kb   ,ke   
{
  int LWeight, RWeight;
  CallTimes++;
  printf( "<   %d     > 
", CallTimes );

//        
  LWeight=CalcCoinTotalWeight(ArrayData,kb,(kb+ke)/2);
  RWeight=CalcCoinTotalWeight(ArrayData,(kb+ke+1)/2,ke);
 
  if(LWeight<RWeight){
	     ke=(kb+ke)/2;
	     if(kb==ke)
		 {
			 t=(kb+ke)/2; 
			 return t;
		 }
		 FindFakeCoin(ArrayData,kb,ke);
	 }
  else if(LWeight>RWeight){
		 kb=(kb+ke+1)/2;
		 if(kb==ke)
		 {
			 t=(kb+ke)/2; 
			 return t;
		 }
		 FindFakeCoin(ArrayData,kb,ke);
		 
	 }

  return t;

}

// ####################################################################### //
//                                                                         // 
//                                                                 // 
//                                                                         // 
// ####################################################################### //

void 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
", ArrayData[ i ] );
  printf( "
" );
  printf( "<   %d      > 
", ( k + 1 ) );
  printf( "
" );

  //             ...
  FakeCoinPos = FindFakeCoin( ArrayData, 0, ARRAY_SIZE - 1 );

  printf( "<     %d      > 
", ( FakeCoinPos + 1 ) );
  printf( "
" );

  //              ...
  system( "PAUSE" );
}

우 리 는 왼쪽 의 질량 과 오른쪽 의 질량 을 계산 해 냈 다. kb 는 왼쪽 경계의 하 표 이 고 ke 는 오른쪽 경계의 하 표 이다. 만약 에 왼쪽 의 질량 이 작 으 면 위 폐 는 왼쪽 에 있다. 우 리 는 오른쪽 경 계 를 중간 으로 옮 기 고 반대로 왼쪽 경 계 를 중간 으로 옮 기 며 계속 진행한다. 맨 뒤에 왼쪽 경계 와 오른쪽 경계 가 같다 는 것 을 알 고 이것 은 동전 이 하나 밖 에 남지 않 았 다 는 것 을 설명 한다.이 동전 은 바로 우리 가 찾 는 위조지폐 다.