穷举算法是最简单的一种算法,其依赖于计算机的强大计算能力,来穷尽每一种可能的穷狂,从而达到求解问题的目的。穷举算法效率并不高,但是适合于一些没有显示规律可循的场合。使用场景如(密码暴力破解)
一、穷举算法基本思想
穷举算法的基本思想就是从所有可能的情况中搜索正确的答案,其执行步骤如下:
- 1.对于一种可能的情况,计算其结果。
- 2.判断结果是否满足要求,如果不满足则执行上一步来搜索下一个可能的情况;如果满足要求,则表示寻找到了一个正确答案。
在使用穷举算法是,需要明确问题答案的范围,这样才可以在指定范围内搜索答案。指定范围之后,就可以使用循环语句和条件判断语句逐步验证候选答案的正确性,从而得到需要的正确答案。
二、穷举算法实例
穷举法是最基本的算法思想,下面通过一个简单的例子来分析穷举算法的应用。鸡兔同笼问题最早记载中1500年前的《孙子算经》,这是我国古代一个非要有名的问题。鸡兔同笼问题的原文如下:
今天鸡兔同笼,上有三十五个头,下有九十四足,问鸡兔各几何?
这个问题的大致意思是:在一个笼子里关着若干只鸡和若干只兔,从上面看共有35个头;从下面数共有94只脚。问笼中鸡和兔的数量各是多少?
1、穷举算法
通过分析可以知道鸡的数量应该为0~35之间的数。这样可以使用穷举法来逐个判断是否符合。
public static int qiongju(int head, int foot){ int i,j,re; re=0; for (i = 0; i <= head; i++) { j = head-1; if (i*2+j*4 == foot) { re = 1; chicken = i; rabbit = j; } } return re;}
2、穷举算法求解鸡兔同笼问题
public class mian1 { /** * 今天鸡兔同笼,上有三十五个头,下有九十四足,问鸡兔各几何? */ static int chicken,rabbit; public static int qiongju(int head, int foot){ int i,j,re; re=0; for (i = 0; i <= head; i++) { j = head-i; //2x+4y =94; if (i*2+j*4 == foot) { re = 1; chicken = i; rabbit = j; } } return re; } public static void main(String[] args) {// System.out.println("穷举法求解鸡兔同笼问题");// System.out.print("请输入头数:");// Scanner scanner = new Scanner(System.in);// int head = scanner.nextInt();// System.out.print("请输入脚数:");// int food = scanner.nextInt();// re=qiongju(head,food); int re; re=qiongju(35,94); if(re == 1){ System.out.println("鸡有多少只"+chicken+";兔有多少只"+rabbit); }else{ System.out.println("无解"); } }}
效果如下:
鸡有多少只23;兔有多少只12