学步园

       下面是在《算法之道》上看到的思维题，感觉很简单，就敲了敲，没写算法题也有一段时间了。现在又做做算法题，感觉真的很喜欢搞算法。大牛曾说，程序是蓝色的诗，算法是诗的灵魂。

        给出一堆球的质量，已知有一个与众不同为所有中最轻的，其余质量相等。给出一个天平，称出这个。由于只给出了天平，就不能直接一次循环挑选出其中的最小值。可以尝试二分‘、三分。下面直接贴个程序：

#include<iostream>
#include<ctime>
using namespace std;

const int MAXN=10000;
int nCount;
int wei[MAXN],sum[MAXN];


int threeDfs(int left,int right)
{
	nCount++;
	if(0==right-left)
		return left;
	else if(1==right-left)
		return wei[left]<wei[right]?left:right;
	int n=right-left+1;
	int lMid=left+n/3;
	if(2==n%3)
		lMid++;
	int rMid=lMid+n/3;
	if(2==n%3)
		rMid++;
	int lSum;
	if(0==left)
		lSum=sum[lMid-1];
	else lSum=sum[lMid-1]-sum[left-1];
	int mSum=sum[rMid-1]-sum[lMid-1];
	int rSum=sum[right]-sum[rMid-1];
	if(lSum>mSum)
		return threeDfs(lMid,rMid-1);
	else if(lSum<mSum)
		return threeDfs(left,lMid-1);
	return threeDfs(rMid,right);
}

int twoDfs(int left,int right)
{
	nCount++;
	if(0==right-left)
		return left;
	else if(1==right-left)
		return wei[left]<wei[right]?left:right;
	int n=right-left+1;
	int lSum;
	int rSum;
	int mid=left+n/2;
	if(0==left)
	   	lSum=sum[mid-1];
	else lSum=sum[mid-1]-sum[left-1];
	rSum=sum[right]-sum[mid-1];
	if(1==n%2)
		rSum-=wei[right];
	if(lSum>rSum)
		return twoDfs(mid,right);
	else if(lSum<rSum)
		return twoDfs(left,mid-1);
	return right;
}


void solve(int n)
{
	sum[0]=wei[0];
	for(int i=1;i<n;i++)
		sum[i]=sum[i-1]+wei[i];
	
	cout<<endl<<"二分法结果如下："<<endl;
	nCount=0;
    int ans=twoDfs(0,n-1);
	cout<<"经过"<<nCount<<"次，找到最轻的一个是第"<<ans<<"个，重为"<<wei[ans]<<endl;

	cout<<endl<<"三分法结果如下："<<endl;
	nCount=0;
	ans=threeDfs(0,n-1);
	cout<<"经过"<<nCount<<"次，找到最轻的一个是第"<<ans<<"个，重为"<<wei[ans]<<endl;


}

void init(int n)
{
	for(int i=0;i<n;i++)
		wei[i]=10;
	int id=rand()%n;
	wei[id]=5;
	cout<<"最轻的一个是第"<<id<<"个，重为"<<wei[id]<<endl;
}

int main()
{
	int n;
	srand((unsigned int)(time(NULL)));
	do
	{
		n=rand()%MAXN;
	}
	while(0==n);
	cout<<"总共有"<<n<<"个球"<<endl;
	init(n);
	solve(n);
	return 0;
}

下面是运行结果：