蓝桥杯培训教程.doc

蓝桥杯培训教程 一、逻辑推理 2 二、排序 8 三、图形(矩阵) 10 四、数字变幻 16 五、数字组合与拆解 21 六、字符串 34 七、数制转换 38 八、排列组合 43 九、其它 43 十、数据结构 60 一、逻辑推理 1、谁是窃贼： 公安人员审问四名窃贼嫌疑犯。已知，这四人当中仅有一名是窃贼，还知道这四人中每人要么是诚实的，要么总是说谎。在回答公安人员的问题中： 甲说：“乙没有偷，是丁偷的。” 乙说：“我没有偷，是丙偷的。” 丙说：“甲没有偷，是乙偷的。” 丁说：“我没有偷” 请根据这四人的谈话判断谁是盗窃者 *问题分析与算法设计 假设A、B、C、D分别代表四个人，变量的值为1代表该人是窃贼。 由题目已知：四人中仅有一名是窃贼，且这四个人中的每个人要么说真话，要么说假话，而由于甲、乙、丙三人都说了两句话：“X没偷，X偷了”，故不论该人是否说谎，他提到的两人中必有一人是小偷。故在列条件表达式时，可以不关心谁说谎，谁说实话。这样，可以列出下列条件表达式： 甲说：”乙没有偷，是丁偷的。” B+D=1 乙说：“我没有偷，是丙偷有。” B+C=1 丙说：“甲没有偷，是乙偷的。” A+B=1 丁说：“我没有偷。” A+B+C+D=1 其中丁只说了一句话，无法判定其真假，表达式反映了四人中仅有一名是窃贼的条件。 #includestdio.h void main() { int i,j,a[4]; for(i=0;i4;i++) /*假定只有第i个人为窃贼*/ { for(j=0;j4;j++) /*将第i个人设置为1表示窃贼，其余为0*/ if(j==i) a[j]=1; else a[j]=0; if(a[3]+a[1]==1a[1]+a[2]==1a[0]+a[1]==1) /*判断条件是否成立*/ { printf(The thief is ); /*成立*/ for(j=0;j=3;j++) /*输出计算结果*/ if(a[j]) printf(%c.,j+A); printf(\n); } } } 2、谁说假话： 张三说李四在说谎，李四说王五在说谎，王五说张三和李四都在说谎。现在问：这三人中到底谁说的是真话，谁说的是假话？ *问题分析与算法设计 分析题目，每个人都有可能说的是真话，也有可能说的是假话，这样就需要对每个人所说的话进行分别判断。假设三个人所说的话的真假用变量A、B、C表示，等于1表示该人说的是真话； 表示这个人说的是假话。由题目可以得到： *张三说李四在说谎 张三说的是真话：a==1b==0 或 张三说的是假话：a==0b==1 *李四说王五在说谎 李四说的是真话：b==1c==0 或 李四说的是假话：b==0c==1 *王五说张三和李四都在说谎 王五说的是真话：c==1a+b==0 或 王五说的是假话：c==0a+b!=0 上述三个条件之间是“与”的关系。将表达式进行整理就可得到C语言的表达式： (a!b||!ab)(b!c||!bc)(ca+b==0||!ca+b!=0) 穷举每个人说真话或说假话的各种可能情况，代入上述表达式中进行推理运算，使上述表达式均为“真”的情况就是正确的结果。 *程序说明与注释 #includestdio.h int main() { int a,b,c; for(a=0;a=1;a++) for(b=0;b=1;b++) for(c=0;c=1;c++) if((a!b||!ab)(b!c||!bc)(ca+b==0||!ca+b!=0)) { printf(Zhangsan told a %s.\n,a?truth:lie); printf(Lisi told a %s.\n,b?truch:lie); printf(Wangwu told a %s.\n,c?truch:lie); } } *运行结果 Zhangsan told a lie (张三说假话) Lisi told a truch. (李四说真话) Wangwu told a lie. (王五说假话) 3、诚实族和说谎族： 诚实族和说谎族是来自两个荒岛的不同民族，诚实族的人永远说真话，而说谎族的人永远说假话。迷语博士是个聪明的人，他要来判断所遇到的人是来自哪个民族的。 迷语博士遇到三个人，知道他们可能是来自诚实族或说谎族的。为了调查这三个人是什么族的，博士分别问了他们的问题，这是他们的对话： 问第一个人：“你们是什么族？”，答：“我们之中有两个来自诚实族。”第二个人说：“不要胡说，我们三个人中只有一个是诚实族的。”第三个人听了第二个人的话后说：“对，就是只有一个诚实族的。” 请根据他的回答判断他们分别是哪个族的。 *问题分析与算法设计 假设这三个人分别为A、B、C