穷举法,或称为暴力破解法(名字来源于对于密码的破译方法,即将密码进行逐个推算直到找出真正的密码为止)是程序设计中使用得最为普遍(并不是在被逼无奈时最后的狂吼)之一,它利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检查,从中找出符合要求的答案。
用穷举算法解决问题,通常可以从两个方面进行分析:
一、问题所涉及的情况:问题所涉及的情况有哪些,情况的种数可不可以确定,候选答案的集合是一个计算机必须能够承受的。
二、答案需要满足的条件:分析出来的这些情况,需要满足什么条件,才成为问题的答案。把这些条件描述出来。
只要把这两个方面分析好了,问题自然会迎刃而解。
只要把这两个方面分析好了,问题自然会迎刃而解。
例 1 :
36 块砖, 36 人搬。男搬 4 ,女搬 3 ,两个小儿抬一砖。要求一次全搬完。问需男、女、小儿各若干?
分析 :
题目要我们找出符合条件的男生、女生和小孩的人数。答案显然是一组数据。首先分析一下问题所涉及的情况。
对于男生来说,至少要有一人;每个男生可以搬4块砖,那么36块砖最多9个男生足够,共有9种不同取值。同样,女生有12种不同取值。两个小孩抬一块砖,至少要有两个小孩,最多36个,并且小孩的人数必须是个偶数,所以小孩的人数可以取18种不同的值。
最坏情况下,男生、女生和小孩的人数可以是 9 × 12 × 18 = 1944 种不同组合。
知道了问题所涉及的情况有1944种,是个确定的数。接下来就要把它描述出来。
假设男生人数为 x ,女生人数为 y ,小孩人数为 z 。可以构建一个三重循环, x 、 y 、 z 的值必须要同时满足两个条件:
①总的工作量是 36 块砖,即: 4x+3y+z/2=36 ;
②需要的总人数是 36 人,即: x+y+z=36 。
把它描述出来就是: 4x+3y+z/2=36 and x+y+z=36 。
满足这个条件的 x 、 y 、 z 的值就是问题的答案。我们可以在循环体里面对这个条件进行判断,源程序如下:
public class Meiju{
public static void main(String[] args){
for(int x=1;i<=9;i++)
for(int y=1;i<=12;i++)
for(int z=2;z<=36;i+=2)
if((4*x+3*y+z/2==36)&&(x+y+z==36)
System.out.println("男生="+x+" 女生="+y+" 小孩="+z);
}
}
运行:
男生=3 女生=3 小孩=30
例2:
下面是一个填写数字的模板,其中每个字都代表数字中的”0~9“,那么要求我们输入的数字能够满足此模板。
思路:首先拿到这个题,蛋还是比较疼的,因为找不到好的解题思路,最后只好"暴力"了
public class MeijuTest {
public static void main(String args[]) {
String father = null;
String mother = null;
String son = null;
int[] a = { 111111, 222222, 333333, 444444, 555555, 666666, 777777, 888888, 999999 };
int[] b = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
father = a[i] / b[j] + "";
mother = b[j] + "";
son = a[i] + "";
if ((father.charAt(0) == mother.charAt(0)) && (father.charAt(4) == son.charAt(0)) && (father.length() == 5)) {
System.out.println(" " + father);
System.out.println("X " + mother);
System.out.println("-------");
System.out.println(son);
System.out.println();
System.out.println("费了:" + ((i + 1 - 1) * 9 + (j + 1)) + "次,TMD终于找出来了!");
}
}
}
}
}
运行结果:
79365
X 7
-------
555555
费了:43次,TMD终于找出来了!
下载源码。
- 大小: 3.5 KB
分享到:
相关推荐
数据结构与算法_枚举(穷举)算法(视频),Dev-C++语言环境!信息学奥赛基础算法!
MATLAB优化算法案例分析与应用(进阶篇)1-10章程序下载
算法系列 数据结构与算法_1.4 枚举(穷举)算法 (1)
数据结构与算法_1.4 枚举(穷举)算法 (2)
我几乎找遍了网络上差不多所有的穷举算法,都不是很满意。然后自己研究了差不多一下行的时候,把现在的代码进行了注释和部分优化。 这个穷举算法,可以自定义起始位,终止位,还可以自定义密码字符。差不多是我觉得...
c语言描述的推销员问题的穷举算法。含程序运行时间计算函数。已经经过测试。
枚举算法又称穷举算法。 基本思想:有序地去尝试每一种可能。 接下来我们去解决一个问题:将1~9填入到9个空位,每个数只能用一次,满足三位数加三位数等于三位数。
此后,在后方Cramer-Rao下界(PCRLB)的基础上,穷举枚举算法采用了一种精确的选择方案,以优化WSN的跟踪性能。 仿真表明,在具有挑战性的环境中,能量平衡具有有效的跟踪性能,与其他传感器相比,某些传感器在间隔...
1.4.枚举(穷举)算法.wmv 3.2.网状关系:图(2).wmv 3.2.网状关系:图(1).wmv 3.1.层次关系结构:树(3).wmv 3.1.层次关系结构:树(2).wmv 3.1.层次关系结构:树(1).wmv 2.3.后进先出结构:栈.wmv 2.1.最简单的结构:...
资源名称:数据结构与算法视频课程(59集)资源目录:【】mysql...数据结构与算法_1.3递推算法【】数据结构与算法_1.4枚举(穷举)算法【】数据结构与算法_1.5 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
1.4.枚举(穷举)算法.wmv 1.5.递归算法.wmv 1.6.分治算法.wmv 1.7.贪婪算法.wmv 1.8.试探法算法.wmv 1.9.模拟算法.wmv 1.10.算法的评价.wmv 2.1.最简单的结构:线性表(1).wmv 2.1.最简单的结构:线性表(2).wmv 2.2....
培养算法思维,掌握枚举算法、分治策略、递归与迭代、选择与交换排序等经典算法模型; 培养实践能力,掌握在存储空间和时间开销受限情况下的程序设计方法; 培养理论思维,掌握复杂问题的算法设计与分析方法。
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
目录解空间的穷举搜索与Google方程式解空间的穷举搜索解空间的定义穷举解空间的策略Google方程式解决策略算法实现运行致谢 解空间的穷举搜索与Google方程式 解空间的穷举搜索 解空间又称为状态空间,是所有可能是解...
1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 1.8 试探法算法 1.9 模拟算法 4.1 排序概述 4.2 冒泡排序法 4.3 快速排序法 4.4 简单选择排序法 4.5 堆排序法 4.6 直接插入排序法 4.7 ...
1.3 递推算法 1.4 枚举(穷举)算法 1.5 递归算法 1.6 分治算法 1.7 贪婪算法 1.8 试探法算法 1.9 模拟算法 4.1 排序概述 4.2 冒泡排序法 4.3 快速排序法 4.4 简单选择排序法 4.5 堆排序法 4.6 直接插入排序法 4.7 ...
穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。 要解决的问题只有有限种可能,在没有更好算法时总可以用穷举搜索的办法解决,即逐个的检查所有...
1.4 枚举(穷举)算法 1.5 递归算法 等等工九章 .... 共9章 下面给大家放第一章的几个代码 程序1-1.c #include int main() { int oldprice,price=0,i=0; printf("请首先设置商品的真实价格:"); scanf("%d",&...
本书旨在探讨如何优化算法效率,详细阐述了经典算法和特殊算法的实现、应用...第 15 章 穷举 176 15 1 激光路径 176 15 2 精确覆盖 179 15 3 数独 184 15 4 排列枚举 186 15 5 正确计算 188 调试工具 191 参考文献 192