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

andalousie

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

1. 5 3
   
2. 2 1 2 3 4
   
3. <
   
4. 1 1 4
   
5. =
   
6. 1 2 5
   
7. =

复制代码

输出3

1. #include <iostream>
   
2. 
   
3. bool jd(int j, int *s, char c)
   
4. {
   
5.   //Assuming that the j-th coin is fake
   
6.   //and check the correctness of this hypothesis
   
7.   //s is the weighing record, the first element is number of counterweight
   
8.   //c is the result
   
9.   int i, f;
   
10.   int m = s[0] << 1;
    
11.   for(i=f=1; i<=m && f; )
    
12.   {
    
13.     if(s[i] == j)
    
14.       f = 0;
    
15.     else
    
16.       ++i;
    
17.   }
    
18.   //Judging whether coin j is included
    
19.   if((!f && c == '=') || (f && c != '='))
    
20.     return 0;
    
21.   return 1;
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.   int num[100][1001];
    
27.   char s[1000];                       //Input
    
28.   int i, t, n, k, no, j;
    
29.   std::cin >> n >> k;
    
30.   for(i=0; i<k; ++i)
    
31.   {
    
32.     std::cin >> num[i][0];
    
33.     for(j=1; j<=2*num[i][0]; ++j)
    
34.       std::cin >> num[i][j];
    
35.     std::cin.get();
    
36.     std::cin >> s[i];
    
37.   }
    
38. 
    
39.   for(i=0, t=0; i<=n; ++i)            //Search all the cases
    
40.   {
    
41.     for(j=0; j<k && jd(i, num[j], s[j]); ++j);
    
42.                                       //Check
    
43.     if(j < k) continue;
    
44.     ++t;                              //t stores the possible cases
    
45.     if(t > 1) break;
    
46.     no = i;                           //not only one fake coin
    
47.   }
    
48. 
    
49.   if(t != 1)
    
50.     std::cout << 0;
    
51.   else
    
52.     std::cout << no;
    
53.   return 0;
    
54. }

复制代码

未闻丶花名

我只是路过打酱油的