我错了，我没有看到“或轻或重”这个条件

我觉得用数学推导出来最简单，让计算机去搜索是不是太慢了点啊。

用数学推导也不简单。

或者给出你的推导主要思路。

如果能解决下面这个问题，就能简单的用程序解决了：

用天平称过一次后（左右两边都有n个球），得到的结果是 左＞右  ，并提供了足够多的标准球作参考，在这样的前提下，至少要几次一定找出问题球。

我不知道最优算法是如何...
不过我想了一下,可以用递归做出来..
主要思路是
一个数组n个元素,分3部分A,B,C(A,B,C各元素数相同)
假如n%3==0,A和B比较,假如相等, 则C有坏球.递归
                         若不等,则坏球在A,B中, 拿A跟C比较..
                                               .若相等,B有坏球.递归
                                                  否则,A有坏球.递归
=========================================================================

假若n%3==1, A和B比较, 假若相等,拿A跟C比,  若相等,d是坏球
                                           否则,C有坏球.递归
                      若不等,拿A跟C比,    若相等,B有坏球.递归
                                          若不等,A有坏球.递归
===========================================================================
假若n%3==2, d和e比较, 若相等,递归(ABC)
                      若不等, d和A中其中一个数比较,若相等, e是坏球
                                                    否则,  d是坏球

[code=c]
int weight(int a[],int size)
{
    int sum = 0;
    for(int i = 0; i< size; ++i)
        sum += a[i];
    return sum;
}

int FindBad(int a[], int size, int A_first,int& depth)
{
    if(size == 1)
        return A_first;
    else if(size == 2)
    {
        ++depth;
        return (a[A_first] == 0? A_first+1:A_first);
    }
    else
    {
        int sub_size = size/3;                //一小组的元素数量
        int A_end = A_first + sub_size -1;    //A组结束index
        int B_first = A_end + 1;             //B组开头index
        int B_end = B_first + sub_size-1;   //B组结束index
        int C_first = B_end + 1;             //C组开头index
        int C_end = C_first + sub_size-1;    //C组结束index
        int d = C_end +1;              
        int e = d+1;
        int A_weight = weight(a+A_first,sub_size);    //A组重量
        int B_weight = weight(a+B_first,sub_size);    //B组重量
        int C_weight = weight(a+C_first,sub_size);    //C组重量
        switch(size%3)
        {
            case 0:
                ++depth;
                if(A_weight == B_weight)
                    return FindBad(a, sub_size, C_first, depth);
                else
                {
                    ++depth;
                    if(A_weight == C_weight)
                        return FindBad(a, sub_size, B_first, depth);
                    else
                        return FindBad(a, sub_size, A_first, depth);
                }    
                break;
            case 1:
                ++depth;
                if(A_weight == B_weight)
                {
                    ++depth;
                    if(A_weight == C_weight)
                        return d;
                    else
                        return FindBad(a, sub_size, C_first, depth);
                }
                else
                {
                    ++depth;
                    if(A_weight == C_weight)
                        return FindBad(a, sub_size, B_first, depth);
                    else    
                        return FindBad(a, sub_size, A_first, depth);
                }    
                break;
            case 2:
                ++depth;
                if(a[d] == a[e])
                    return FindBad(a, size-2, A_first, depth);
                else
                {
                    ++depth;
                    return (a[d] == a[A_first] ? e:d);
                }
                break;
        }
    }
}
[/code]

先赞一个：楼上给出的代码很整洁，思路很清晰，考虑的方面也很全！！！
楼上的方案确实可以找到问题球！！！

[quote][code=c]
else if(size == 2)
    {
        ++depth;
        return (a[A_first] == 0? A_first+1:A_first);//这里我觉得
                                                  //要适当的修改
        //意思差不多，只要找个标准球比较就行了
        //不过要用程序写出来还是比较麻烦的
    }
[/code][/quote]

还有个问题，如果一共只有2个球的情况，那是找不出问题球的（可以说任何一个都是问题球），所以最开始还要排除（不能放在FindBad函数内排除)这种情况；如果一共只有1个球的情况类似2个球的情况。

找球容易,关键是如何让称重次数最少

[quote]先赞一个：楼上给出的代码很整洁，思路很清晰，考虑的方面也很全！！！
楼上的方案确实可以找到问题球！！！

[quote][code=c]
else if(size == 2)
    {
        ++depth;
        return (a[A_first] == 0? A_first+1:A_first);//这里我觉得
                                                  //要适当的修改
        //意思差不多，只要找个标准球比较就行了
        //不过要用程序写出来还是比较麻烦的
    }
[/code][/quote]

还有个问题，如果一共只有2个球的情况，那是找不出问题球的（可以说任何一个都是问题球），所以最开始还要排除（不能放在FindBad函数内排除)这种情况；如果一共只有1个球的情况类似2个球的情况。




[/quote]

恩.是的..size<2的时候就不行了...可以加多个条件检验.当depth==0 && size<=2 就return error...

[quote]找球容易,关键是如何让称重次数最少[/quote]
假如在原来的思路上,改一下..假如在比较的过程中知道坏球是重 或者 是轻..然后用折3或者折2分来称(已知坏球是重或轻)...是否会减少一点比较次数..