main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 91 行

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

  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);
}