分治算法--假币问题

将这n个硬币分成两等份，然后放到天平的两端，则假币在较轻的那一端；然后将较轻的那一端的硬币再分成2等份，然后再放到天平的两端进行比较，假币还是在较轻的那一段；直到最后只剩下两个硬币了，分别放到天平的两端，轻的哪一个就是假币。当然，最后也可能剩下3个硬币，我们可以将这3个硬币中任意拿出来一个，然后将剩下的两个放到天平的两端，如果天平是平的，则说明拿出来的那个硬币就是假币；如果天平不是平的，则轻的那一端是假币。（注：硬币币值一样）

#include<iostream>
using namespace std;

int find_false(int a[],int low,int high)
{
    int i=0;                        //作为遍历的计数器 
    int re=0;                       //re作为返回值
    int sum1,sum2,sum3;             //三个用来累加的变量
    sum1=sum2=sum3=0;
    int center=0;

    if(low+1==high)             //当遍历到最后两个元素的时候 
    {
        if(a[low]<a[high])
        {
            re=low;
            return re;
        }
        else
        {
            re=high;
            return re;
        }
    } 

    if((high-low+1)%2==0)               //当长度为偶数的时候
    {
        center = (high-low+1)/2;
        for(i=low;i<=center;i++)    //对前半段求和 
        {
            sum1+=a[i];
        }

        for(i=center+1;i<=high;i++) //对后半段求和 
        {
            sum2+=a[i];
        }

        if(sum1<sum2)               //假币在前半段 
        {
            re=find_false(a,low,center);
            return re;
        }
        else if(sum2<sum1)          //假币在后半段 
        {
            re=find_false(a,center+1,high);
            return re;  
        }   
    }
    else                        //当长度为奇数的时候 
    {
        center =low+(high-low)/2;
        for(i=low;i<center;i++) //对前半段求和
        {
            sum1+=a[i];
        }
        for(i=center+1;i<=high;i++)//对后半段求和
        {
            sum2+=a[i];
        }
        sum3=a[center];         //sum3用于存放中间数据 
        if(sum1<sum2)                   //假币在前半段 
        {
            re=find_false(a,low,center-1);
            return re; 
        }
        else if(sum2>sum1)
        {
            re=find_false(a,center+1,high);
            return re;
        }
        else if(sum1==sum2) //中间的那个就是假币！
        {
            re=center;
            return re;
        } 
    } 
} 
int main()
{
    int a[100];
    int n,i,re;
    cout<<"请输入硬币的个数(>1&&<100)：";
    cin>>n;
    if (n<1)
    {
        cout<<""<<endl;
    }

    cout<<"请分别输入这个"<<n<<"个硬币的重量："<<endl;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];  
    }

    for(i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";    
    }
    re=find_false(a,1,n);
    cout<<"假币是第"<<re<<"硬币"<<endl;
    return 0;   
}

---

[email protected]/4/25