C++写的一个简单的两个逻辑推理题求解算法

CNIU

有C++和python两个版本的，前一个是C++的
http://bbs.chinaunix.net/thread-976470-1-1.html

dorainm

这两道题目我不会做帮我看看 python的代码我弄不出来清华附中有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。
A说：不是我。
B说：是C。
C说：是D。
D说：他胡说。
        已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。

1. 
   
2. #include <stdio.h>
   
3. 
   
4. #define TOTAL_NUM 4
   
5. #define CORRECT_NUM 3
   
6. 
   
7. enum std_id { STD_A=0, STD_B, STD_C, STD_D };
   
8. enum std_statu { DONOT=0, DO };
   
9. 
   
10. static int test( int std, int statu, int condition )
    
11. {
    
12.         if( (statu && std==condition) || (!statu && std!=condition) )
    
13.                 return 1;
    
14.         else
    
15.                 return 0;
    
16. };
    
17. 
    
18. 
    
19. int main( void )
    
20. {
    
21.         int guess, correct_time;
    
22. 
    
23.         for( guess=0; guess<TOTAL_NUM; guess++ )
    
24.         {
    
25.                 correct_time = test( STD_A, DONOT, guess );
    
26.                 correct_time += test( STD_C, DO, guess );
    
27.                 correct_time += test( STD_D, DO, guess );
    
28.                 correct_time += test( STD_D, DONOT, guess );
    
29.                 if( CORRECT_NUM==correct_time )
    
30.                 {
    
31.                         printf( "the student is %c\n", ('A'+guess) );
    
32.                 }
    
33.         };
    
34. 
    
35.         return 0;
    
36. }
    

复制代码

这个可以吗？

static int test( int std, int statu, int condition )；
函数 test用来测试，描述的学生和他的状态（做了还是没做)是否与假设的条件成立；如果成立返回１，不然返回０！


主函数用for( guess=0; guess<TOTAL_NUM; guess++ )来依次做假设
然后为每次假设进行４个人说话的判断

test( STD_A, DONOT, guess );  //A说：不是我。
test( STD_C, DO, guess );     //B说：是C。
test( STD_D, DO, guess );     //C说：是D。
test( STD_D, DONOT, guess );   //D说：他胡说。

然后判断当前假设是否是３个真话（即一个假话)，是的话则打印出假设

if( CORRECT_NUM==correct_time )
{
        printf( "the student is %c\n", ('A'+guess) );
}

程序就结束了

编译运行

dorainm@lfs ~/workroom/c/conseq $ gcc -o conseq conseq.c
dorainm@lfs ~/workroom/c/conseq $ ./conseq
the student is C
dorainm@lfs ~/workroom/c/conseq $

[ 本帖最后由 dorainm 于 2007-9-3 05:36 编辑 ]

dorainm

原帖由 rubee 于 2007-8-14 22:10 发表
第二题：某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：
A、B 至少有一人作案；
A、E、F 三人中至少有两人参与作案；
A、D 不可能是同案犯；
B、C 或同时作案，或与本案无关；
C、D 中有且仅有一人作案；
如果 D 没有参与作案，则 E 也不可能参与作案。
试编一程序，将作案人找出来

比较笨，用的是穷举！！

跟上题一样，排列出所有可能的罪犯组合类型，
我们用一个int来表达，最低位为A，依次升高为B、C、D、E、F
(既A是第0位、B第1位、C2、D3、E4、F5)
如果A、B、D是罪犯的话，那表达出来就是

(1<<0)+(1<<1)+(1<<3) = 1+2+8 = 13

现在列举所有的罪犯组合，只需要循环，从0到(2^6-1)

思想是这个样子的，把所有一切都转化成数目的思考！
比如X、Y同犯，则表明数目是２
要判断罪犯列表中X、Y是否是同犯，
只要把X、Y的组合与整体的罪犯组合与运算后，
２进制中依然能数出来２个１，则确定X、Y是同犯成立

statu2int函数就是属状态码的２进制中数有多少个罪犯数目的
static int statu2int( int statu )

check则用要判断的罪犯列表、他们的关系数量，与输入的假设犯罪组合进行比较，如果成立返回１，否则返回０
static int check( int men, int num, int condition )


main中，循环所有组合，依次判断题目中的条件，
如果不符合，就continue；如果都符合，则打印出当前罪犯组合

下面看具体代码

1. 
   
2. #include <stdio.h>
   
3. #include <math.h>
   
4. 
   
5. #define NUM 6
   
6. 
   
7. int statu = 0;
   
8. enum man { A=0, B, C, D, E, F };
   
9. 
   
10. 
    
11. static int statu2int( int statu )
    
12. {
    
13.         int i, retval = 0;
    
14. 
    
15.         for( i=0; i<NUM; i++ )
    
16.                 if( (statu>>i)&0x01 ) retval++;
    
17. 
    
18.         return (retval);
    
19. };
    
20. 
    
21. 
    
22. static int check( int men, int num, int condition )
    
23. {
    
24.         if( num==statu2int(men&condition) )
    
25.                 return 1;
    
26.         else
    
27.                 return 0;
    
28. };
    
29. 
    
30. 
    
31. int main( void )
    
32. {
    
33.         int guess, i;
    
34. 
    
35.         for( guess=0; guess<pow(2,NUM); guess++ )
    
36.         {
    
37.                 /*A和B至少有１个人作案*/
    
38.                 if( !( check( (1<<A)+(1<<B), 1, guess ) || check( (1<<A)+(1<<B), 2, guess ) ) )    continue;
    
39. 
    
40.                 /*A、E、F至少有２个人作案*/
    
41.                 if( !( check( (1<<A)+(1<<E)+(1<<F), 2, guess ) || check( (1<<A)+(1<<E)+(1<<F), 3, guess ) ) ) continue;
    
42. 
    
43.                 /*A、D不可能是同犯*/
    
44.                 if( check( (1<<A)+(1<<D), 2, guess ) )  continue;
    
45. 
    
46.                 /*B、C或同时作案，或与本案无关*/
    
47.                 if( !( check( (1<<B)+(1<<C), 0, guess ) || check( (1<<B)+(1<<C), 2, guess ) ) )    continue;
    
48. 
    
49.                 /*C、D 中有且仅有一人作案*/
    
50.                 if( !check( (1<<C)+(1<<D), 1, guess ) )        continue;
    
51. 
    
52.                 /*如果 D 没有参与作案，则 E 也不可能参与作案*/
    
53.                 if( check( (1<<D), 0, guess ) )
    
54.                         if( !check( (1<<E), 0, guess ) )       continue;
    
55. 
    
56.                 for( i=0; i<NUM; i++ )
    
57.                 {
    
58.                         if( (guess>>i)&0x01 ) fputc( 'A'+i, stdout );
    
59.                 }
    
60.                 printf( "\n" );
    
61.         }
    
62. 
    
63.         return 0;
    
64. }
    

复制代码

编译运行

dorainm@lfs ~/workroom/c/conseq $ gcc -o conseq2 conseq2.c
dorainm@lfs ~/workroom/c/conseq $ ./conseq2
ABCF
dorainm@lfs ~/workroom/c/conseq $

犯罪列表出来了：）

[ 本帖最后由 dorainm 于 2007-9-3 05:28 编辑 ]