andalousie 发表于 2014-2-1 20:31:11

一个蛮力搜索的问题，缠了我好久

本帖最后由 andalousie 于 2014-2-1 20:32 编辑

我有个不太好的习惯，就是喜欢在全局一下儿把所有的变量声明完，其实有些变量在局部何以发挥作用。
这是一个找出假金币的算法。
输入示例5 3
2 1 2 3 4
<
1 1 4
=
1 2 5
=输出3
#include <iostream>

bool jd(int j, int *s, char c)
{
//Assuming that the j-th coin is fake
//and check the correctness of this hypothesis
//s is the weighing record, the first element is number of counterweight
//c is the result
int i, f;
int m = s << 1;
for(i=f=1; i<=m && f; )
{
    if(s == j)
      f = 0;
    else
      ++i;
}
//Judging whether coin j is included
if((!f && c == '=') || (f && c != '='))
    return 0;
return 1;
}

int main()
{
int num;
char s;                     //Input
int i, t, n, k, no, j;
std::cin >> n >> k;
for(i=0; i<k; ++i)
{
    std::cin >> num;
    for(j=1; j<=2*num; ++j)
      std::cin >> num;
    std::cin.get();
    std::cin >> s;
}

for(i=0, t=0; i<=n; ++i)            //Search all the cases
{
    for(j=0; j<k && jd(i, num, s); ++j);
                                    //Check
    if(j < k) continue;
    ++t;                              //t stores the possible cases
    if(t > 1) break;
    no = i;                           //not only one fake coin
}

if(t != 1)
    std::cout << 0;
else
    std::cout << no;
return 0;
}


未闻丶花名 发表于 2014-2-15 20:31:31

我只是路过打酱油的
页: [1]
查看完整版本: 一个蛮力搜索的问题，缠了我好久