C++寫的一個簡單的兩個邏輯推理題求解算法

CNIU

有C++和python兩個版本的，前一個是C++的
http://www.72891.cn/thread-976470-1-1.html

dorainm

這兩道題目我不會做幫我看看 python的代碼我弄不出來清華附中有四位同學(xué)中的一位做了好事，不留名，表揚(yáng)信來了之后，校長問這四位是誰做的好事。
A說：不是我。
B說：是C。
C說：是D。
D說：他胡說。
        已知三個人說的是真話，一個人說的是假話�，F(xiàn)在要根據(jù)這些信息，找出做了好事的人。

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. }
    

復(fù)制代碼

這個可以嗎？

static int test( int std, int statu, int condition )；
函數(shù) test用來測試，描述的學(xué)生和他的狀態(tài)（做了還是沒做)是否與假設(shè)的條件成立；如果成立返回１，不然返回０！


主函數(shù)用for( guess=0; guess<TOTAL_NUM; guess++ )來依次做假設(shè)
然后為每次假設(shè)進(jìn)行４個人說話的判斷

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說：他胡說。

然后判斷當(dāng)前假設(shè)是否是３個真話（即一個假話)，是的話則打印出假設(shè)

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

程序就結(jié)束了

編譯運(yùn)行

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 發(fā)表
第二題：某地刑偵大隊(duì)對涉及六個嫌疑人的一樁疑案進(jìn)行分析：
A、B 至少有一人作案；
A、E、F 三人中至少有兩人參與作案；
A、D 不可能是同案犯；
B、C 或同時作案，或與本案無關(guān)；
C、D 中有且僅有一人作案；
如果 D 沒有參與作案，則 E 也不可能參與作案。
試編一程序，將作案人找出來

比較笨，用的是窮舉��！

跟上題一樣，排列出所有可能的罪犯組合類型，
我們用一個int來表達(dá)，最低位為A，依次升高為B、C、D、E、F
(既A是第0位、B第1位、C2、D3、E4、F5)
如果A、B、D是罪犯的話，那表達(dá)出來就是

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

現(xiàn)在列舉所有的罪犯組合，只需要循環(huán)，從0到(2^6-1)

思想是這個樣子的，把所有一切都轉(zhuǎn)化成數(shù)目的思考！
比如X、Y同犯，則表明數(shù)目是２
要判斷罪犯列表中X、Y是否是同犯，
只要把X、Y的組合與整體的罪犯組合與運(yùn)算后，
２進(jìn)制中依然能數(shù)出來２個１，則確定X、Y是同犯成立

statu2int函數(shù)就是屬狀態(tài)碼的２進(jìn)制中數(shù)有多少個罪犯數(shù)目的
static int statu2int( int statu )

check則用要判斷的罪犯列表、他們的關(guān)系數(shù)量，與輸入的假設(shè)犯罪組合進(jìn)行比較，如果成立返回１，否則返回０
static int check( int men, int num, int condition )


main中，循環(huán)所有組合，依次判斷題目中的條件，
如果不符合，就continue；如果都符合，則打印出當(dāng)前罪犯組合

下面看具體代碼

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或同時作案，或與本案無關(guān)*/
    
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. }
    

復(fù)制代碼

編譯運(yùn)行

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 編輯 ]