周五的时候公司群发了这个推理题的图片，周六有同事尝试用python去解这个题，然后大家纷纷产生了兴趣要尝试一把。
用程序去解这个题，首先要判断下问题规模。整个卷子公有10个含有4选项的选择题，所以如果枚举每个可能选项，一共有4^10个，大概是10^6这个规模，比起上Ghz(10^9)的CPU，理应是在毫秒级完成遍历，加上每次还要进行条件判断，枚举解决应该最终时间是在毫秒级到秒级这个范围。所以这么看枚举法非常合适来解决这个问题。
于是首先用暴力枚举法来实现，语言采用C99
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#include <stdio.h> #include <stdlib.h> #include <sys/time.h> #define A 0 #define B 1 #define C 2 #define D 3 typedef int INT8; u_int32_t answer = 0; INT8 ans[11] = {0}; #define ANSWER(index) (((answer >> (((index) - 1) * 2)) % 4)) #define ANS(index) (ans[index]) int main() { struct timeval t_val; gettimeofday(&t_val, NULL); printf("start, now, sec=%ld m_sec=%d \n", t_val.tv_sec, t_val.tv_usec); long sec = t_val.tv_sec; time_t t_sec = (time_t)sec; printf("date:%s", ctime(&t_sec)); for(answer = 0; answer < (1 << 20); answer++) { // 计算每个答案的值 for(int i = 1; i <= 10; i++) { ans[i] = ANSWER(i); } // 判断第2题 switch(ANS(2)) { case A: if(ans[5] != C) { continue; } break; case B: if(ans[5] != D) { continue; } break; case C: if(ans[5] != A) { continue; } break; case D: if(ans[5] != B) { continue; } break; default: {} } // 判断第3题 switch(ANS(3)) { case A: if(ans[3] == ANS(6) || ans[3] == ANS(2) || ans[3] == ANS(4)) { continue; } break; case B: if(ans[6] == ANS(3) || ans[6] == ANS(2) || ans[6] == ANS(4)) { continue; } break; case C: if(ans[2] == ANS(3) || ans[2] == ANS(6) || ans[2] == ANS(4)) { continue; } break; case D: if(ans[4] == ANS(3) || ans[4] == ANS(6) || ans[4] == ANS(2)) { continue; } break; default: {} } // 判断第4题 switch(ANS(4)) { case A: if(ANS(1) != ANS(5)) { continue; } break; case B: if(ANS(2) != ANS(7)) { continue; } break; case C: if(ANS(1) != ANS(9)) { continue; } break; case D: if(ANS(6) != ANS(10)) { continue; } break; default: {} } // 判断第5题 switch(ANS(5)) { case A: if(ans[5] != ANS(8)) { continue; } break; case B: if(ans[5] != ANS(4)) { continue; } break; case C: if(ans[5] != ANS(9)) { continue; } break; case D: if(ans[5] != ANS(7)) { continue; } break; default: {} } // 判断第6题 switch(ANS(6)) { case A: if(ans[8] != ANS(2) || ans[8] != ANS(4)) { continue; } break; case B: if(ans[8] != ANS(1) || ans[8] != ANS(6)) { continue; } break; case C: if(ans[8] != ANS(3) || ans[8] != ANS(10)) { continue; } break; case D: if(ans[8] != ANS(5) || ans[8] != ANS(9)) { continue; } break; default: {} } // 计数ABCD的选项个数 int num[4] = {0}; for(int i = 1; i <= 10; i++) { num[ANS(i)]++; } // 判断第7题 switch(ANS(7)) { case A: if(num[A] < num[C] || num[B] < num[C] || num[D] < num[C]) { continue; } break; case B: if(num[A] < num[B] || num[C] < num[B] || num[D] < num[B]) { continue; } break; case C: if(num[B] < num[A] || num[C] < num[A] || num[D] < num[A]) { continue; } break; case D: if(num[A] < num[D] || num[B] < num[D] || num[C] < num[D]) { continue; } break; default: {} } // 判断第8题 switch(ANS(8)) { case A: if(abs(ans[7] - ANS(1)) == 1) { continue; } break; case B: if(abs(ans[5] - ANS(1)) == 1) { continue; } break; case C: if(abs(ans[2] - ANS(1)) == 1) { continue; } break; case D: if(abs(ans[10] - ANS(1)) == 1) { continue; } break; default: {} } // 判断第9题 switch(ANS(9)) { case A: if(((ANS(1) == ANS(6)) ^ (ans[6] == ANS(5))) == 0) { continue;} break; case B: if(((ANS(1) == ANS(6)) ^ (ans[10] == ANS(5))) == 0) { continue;} break; case C: if(((ANS(1) == ANS(6)) ^ (ans[2] == ANS(5))) == 0) { continue;} break; case D: if(((ANS(1) == ANS(6)) ^ (ans[9] == ANS(5))) == 0) { continue;} break; default: {} } // 计算numMax和numMin int numMax = 0, numMin = 10; for(int i = 0; i < 4; i++) { if(num[i] > numMax) { numMax = num[i]; } if(num[i] < numMin) { numMin = num[i]; } } // 判断第10题 switch(ANS(10)) { case A: if((numMax - numMin) != 3) { continue; } break; case B: if((numMax - numMin) != 2) { continue; } break; case C: if((numMax - numMin) != 4) { continue; } break; case D: if((numMax - numMin) != 1) { continue; } break; default: {} } // 输出结果 for(int i = 1; i <= 10; i++) { printf("%c ", ANS(i) + 65); } printf("\n"); } struct timeval t_val_end; gettimeofday(&t_val_end, NULL); struct timeval t_result; timersub(&t_val_end, &t_val, &t_result); double consume = t_result.tv_sec + (1.0 * t_result.tv_usec)/1000000; printf("end.elapsed time= %fs \n", consume); return 0; } |
然后用mac默认的gcc带O3优化编译，输出结果
|
1 2 3 4 |
start, now, sec=********** m_sec=793932 date: *********** 2018 B C A C A C D A B A end.elapsed time= 0.008570s |
看来运行时间在8ms左右。这么看其实结果也不错，因为在很短的时间里就把这个问题解决了，而且代码量比较少。
但是事情还没有结束。公司群里各位同学纷纷开始比拼优化的时间，有同学通过深度优先搜索加剪枝，优化到0ms的执行时间。于是我也打算试试看怎么实现。通过查看这位同学的代码，搞懂了原理：就是在深度优先搜索的过程中，如果在当前分支不满足条件，则不用继续搜索下去。所以按照这个思路，实现了搜索版的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 |
#include <stdio.h> #include <stdlib.h> #include <sys/time.h> #define A 0 #define B 1 #define C 2 #define D 3 typedef int8_t INT8; INT8 ans[11] = {0}; #define ANS(index) (ans[index]) // 条件不匹配，返回非0 INT8 checkAnswer(INT8 index) { // 如果该题目的相关选项的序号不超过n，则可在n的规模内判定，并在不匹配时不再继续搜索当前分支 switch(index) { case 5: { // 判断知道1~5题答案就能确认是否还要继续搜索的情况 // 判断第2题 switch(ANS(2)) { case A: if(ans[5] != C) { return -1; } break; case B: if(ans[5] != D) { return -1; } break; case C: if(ans[5] != A) { return -1; } break; case D: if(ans[5] != B) { return -1; } break; default: {} } } break; case 6: { // 判断知道1~6题答案就能确认是否还要继续搜索的情况 // 判断第3题 switch(ANS(3)) { case A: if(ans[3] == ANS(6) || ans[3] == ANS(2) || ans[3] == ANS(4)) { return -1; } break; case B: if(ans[6] == ANS(3) || ans[6] == ANS(2) || ans[6] == ANS(4)) { return -1; } break; case C: if(ans[2] == ANS(3) || ans[2] == ANS(6) || ans[2] == ANS(4)) { return -1; } break; case D: if(ans[4] == ANS(3) || ans[4] == ANS(6) || ans[4] == ANS(2)) { return -1; } break; default: {} } } break; case 9: { // 判断知道1~9题答案就能确认是否还要继续搜索的情况 // 判断第5题 switch(ANS(5)) { case A: if(ans[5] != ANS(8)) { return -1; } break; case B: if(ans[5] != ANS(4)) { return -1; } break; case C: if(ans[5] != ANS(9)) { return -1; } break; case D: if(ans[5] != ANS(7)) { return -1; } break; default: {} } } break; case 10: { // 判断知道1~10题答案就能确认是否还要继续搜索的情况 // 判断第4题 switch(ANS(4)) { case A: if(ANS(1) != ANS(5)) { return -1; } break; case B: if(ANS(2) != ANS(7)) { return -1; } break; case C: if(ANS(1) != ANS(9)) { return -1; } break; case D: if(ANS(6) != ANS(10)) { return -1; } break; default: {} } // 判断第6题 switch(ANS(6)) { case A: if(ans[8] != ANS(2) || ans[8] != ANS(4)) { return -1; } break; case B: if(ans[8] != ANS(1) || ans[8] != ANS(6)) { return -1; } break; case C: if(ans[8] != ANS(3) || ans[8] != ANS(10)) { return -1; } break; case D: if(ans[8] != ANS(5) || ans[8] != ANS(9)) { return -1; } break; default: {} } // 判断第8题 switch(ANS(8)) { case A: if(abs(ans[7] - ANS(1)) == 1) { return -1; } break; case B: if(abs(ans[5] - ANS(1)) == 1) { return -1; } break; case C: if(abs(ans[2] - ANS(1)) == 1) { return -1; } break; case D: if(abs(ans[10] - ANS(1)) == 1) { return -1; } break; default: {} } // 判断第9题 switch(ANS(9)) { case A: if(((ANS(1) == ANS(6)) ^ (ans[6] == ANS(5))) == 0) { return -1;} break; case B: if(((ANS(1) == ANS(6)) ^ (ans[10] == ANS(5))) == 0) { return -1;} break; case C: if(((ANS(1) == ANS(6)) ^ (ans[2] == ANS(5))) == 0) { return -1;} break; case D: if(((ANS(1) == ANS(6)) ^ (ans[9] == ANS(5))) == 0) { return -1;} break; default: {} } // 计数ABCD的选项个数 int num[4] = {0}; for(int i = 1; i <= 10; i++) { num[ANS(i)]++; } // 判断第7题 switch(ANS(7)) { case A: if(num[A] < num[C] || num[B] < num[C] || num[D] < num[C]) { return -1; } break; case B: if(num[A] < num[B] || num[C] < num[B] || num[D] < num[B]) { return -1; } break; case C: if(num[B] < num[A] || num[C] < num[A] || num[D] < num[A]) { return -1; } break; case D: if(num[A] < num[D] || num[B] < num[D] || num[C] < num[D]) { return -1; } break; default: {} } // 计算numMax和numMin int numMax = 0, numMin = 10; for(int i = 0; i < 4; i++) { if(num[i] > numMax) { numMax = num[i]; } if(num[i] < numMin) { numMin = num[i]; } } // 判断第10题 switch(ANS(10)) { case A: if((numMax - numMin) != 3) { return -1; } break; case B: if((numMax - numMin) != 2) { return -1; } break; case C: if((numMax - numMin) != 4) { return -1; } break; case D: if((numMax - numMin) != 1) { return -1; } break; default: {} } // 输出结果 for(int i = 1; i <= 10; i++) { printf("%c ", ANS(i) + 65); } printf("\n"); } break; default: {} } return 0; } void dfs(INT8 index) { // 判断条件 if(checkAnswer(index)) { return; } // 进行下一层搜索 if(index < 10) { for(INT8 i = A; i <= D; i++) { // 赋值 ans[index + 1] = i; dfs(index + 1); } } } int main() { struct timeval t_val; gettimeofday(&t_val, NULL); printf("start, now, sec=%ld m_sec=%d \n", t_val.tv_sec, t_val.tv_usec); long sec = t_val.tv_sec; time_t t_sec = (time_t)sec; printf("date:%s", ctime(&t_sec)); dfs(0); struct timeval t_val_end; gettimeofday(&t_val_end, NULL); struct timeval t_result; timersub(&t_val_end, &t_val, &t_result); double consume = t_result.tv_sec + (1.0 * t_result.tv_usec)/1000000; printf("end.elapsed time= %fs \n", consume); } |
跑了一下，时间的确短了
|
1 2 3 4 |
start, now, sec=********** m_sec=804044 date:***************** 2018 B C A C A C D A B A end.elapsed time= 0.001366s |
大概是在1ms左右。看来搜索+剪枝确实比较有效，而且实际代码量没有增加太多。
这样这个问题通过暴力枚举/深度优先搜索+剪枝两种方法解决，还是挺有意思的~