C语言经典枚举算法之谁在说谎（详解）

怼烎@ 2023-01-10 14:35 35阅读 0赞

### 文章目录 ###

*   *  一、枚举算法
     *  二、谁在说谎问题

## 一、枚举算法 ##

**1、枚举**  
枚举算法是我们在日常中使用到的最多的一个算法，它的核心思想就是:枚举所有的可能。  
枚举法的本质就是从所有候选答案中去搜索正确的解。

**2、使用枚举算法需要满足两个条件**  
(1)可预先确定候选答案的数量；(2)候选答案的范围在求解之前必须有一个确定的集合。

**3、枚举的优点**  
枚举算法简单粗暴，他暴力的枚举所有可能，尽可能地尝试所有的方法。虽然枚举算法非常暴力，而且速度可能很慢，但确实我们最应该优先考虑的！因为枚举法变成实现最简单，并且得到的结果总是正确的。

**4、枚举的缺点**  
运算量比较大，解题效率不高。如果枚举范围太大，在时间就难以承受。枚举算法的优点:思路简单，程序编写和调试方便。在竞赛中，时间有限的，我们竞赛的最终目标就是求出问题解。因此，如果题目的规模不是很大，在满足规定的时间和空间要求下能够求出解，那么我们最好是采用枚举法，而不需要大在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

## 二、谁在说谎问题 ##

**1、问题**  
张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。

**2、问题分析**  
这是一个逻辑推理题，用正常的推理无法得出答案。利用反证法，我们可以先假设一个条件，然后根据这个条件进行推理，如果得出的结果不与条件矛盾，则说明条件成立 ，如果推出的结果与已知条件矛盾说明条件是错误的。

**3、C语言找出谁在说谎**

#include <stdio.h>
    void 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==0)  //如果张三没有说谎 
    				{ 
    					if(b==1)  //如果李四在说谎 
    						if(c==0)  //如果王五没有说谎 
    							if(a==1 && b==1)
    								printf("%3d,%3d,%3d\n", a, b, c);
    				}
    				if(b==0)  //如果李四没说谎 
    				{ 
    					if(a==1 && c==1)  //如果张三和王五在说谎 
    						if(a==0 || b==0)
    							printf("%3d,%3d,%3d\n", a, b, c);
    				}
    				if(c==0)  //如果王五没有说谎 
    				{ 
    					if(a==1 && b==1)  //如果张三和李四在说谎 
    						if(b==0)
    							printf("%3d,%3d,%3d\n", a, b, c);
    				}
    			}
    }

![01][]

**4、原理分析**  
从运行结果上看，张三和王五在说谎，李四没有说谎。  
（1）首先依次枚举a、b、c的候选解，候选解只有两种取值0和1，0表示没有说谎，1表示说谎  
（2）然后分别假设张三没说谎，并验证结果。  
（3）假设李四没说谎，并验证结果。  
（4）再假设王五没说谎，并验证结果 。

参考文献：《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/c44e3b1a408b4b419858b6990c3d10fb.png