/***********************************************************************************

  28. ｎ枚銀幣 C1,C2,...,Cn, 其中有一塊不合格,不合格的銀幣比正常的要重。現用
 一天平找出不合格的一塊，要求在最壞的情況下，用的天平次數最少。

  分析:每次稱量都將銀幣平均分成三分(至多相差一枚)進行稱量,可使稱量次數達到最小

***********************************************************************************/

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

int *C;
int n;
int counter = 0;

int metage(int s,int t)
{
	int i,k,lw,rw;
	if(s == t)
		return s;
	else
	{
		counter ++;
		if((t-s+1)%3 == 0)
		{
			k = (t-s+1)/3;
			lw = 0,rw = 0;
			for(i=0; i<k; i++)
				lw += C[i+s];
			for(i=0;i<k;i++)
				rw += C[s+k+i];
			if(lw == rw)
				return metage(s+2*k,t);
			else if(lw < rw)
				return metage(s+k,s+2*k-1);
			else return metage(s,s+k-1);
			
		}
		else if((t-s+1)%3 == 1) 
		{
			k = (t-s+1)/3;
			lw = 0,rw = 0;
			for(i=0; i<k; i++)
				lw += C[s+k+1+i];
			for(i=0;i<k;i++)
				rw += C[s+2*k+1+i];
			if(lw == rw)
				return metage(s,s+k);
			else if(lw < rw)
				return metage(s+2*k+1,t);
			else return metage(s+k+1,s+2*k);
		}
		else 
		{
			k = (t-s+1)/3;
			lw = 0,rw = 0;
			for(i=0; i<k+1; i++)
				lw += C[s+i];
			for(i=0;i<k+1;i++)
				rw += C[s+k+1+i];
			if(lw == rw)
				return metage(s+2*(k+1),t);
			else if(lw < rw)
				return metage(s+k+1,s+2*k+1);
			else return metage(s,s+k);
		}
	}
	return -1;
}

void main()
{
	int i;
	printf("請輸入銀幣的數量n: ");
	scanf("%d", &n);
	C = (int*)malloc(n*sizeof(int));
	for(i=0; i<n; i++)
		C[i] = 10;
	srand(time(0));
	C[rand()%n] += 1;

	for(i=0; i<n; i++)
		printf("%3d",C[i]);
	printf("\n");

	printf("不合格的銀幣是第%d塊!\n",metage(0,n-1)+1);
	printf("稱量次數是%d次\n",counter);
}