一、枚举算法
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);
}
}
}
4、原理分析
从运行结果上看,张三和王五在说谎,李四没有说谎。
(1)首先依次枚举a、b、c的候选解,候选解只有两种取值0和1,0表示没有说谎,1表示说谎
(2)然后分别假设张三没说谎,并验证结果。
(3)假设李四没说谎,并验证结果。
(4)再假设王五没说谎,并验证结果 。
参考文献:《The Function and Algorithm of Program Language C/C++》
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)