常用的数据结构和算法2.ppt

专业教程 理论讲解部分 Ver3.1 第017课 算法及数据结构 概述： 穷举算法 递归算法 重点： 难点： 递归算法 穷举算法 递归算法 第017课 算法及数据结构 1 穷举 依次查询所有可能情况,以获得目标值. 利用计算机计算速度快的特点,在备选项目不是特别多的情况下可以使用 查询过程要无遗漏,不重复 穷举并不是说不要任何地优化，在有明显得条件可以优化的前提下还是应该尽量优化程序 例:利用穷举法在1-100的自然数中找出所有的素数 第017课 算法及数据结构 public class Qiongju { private int[] result; public Qiongju(){ result = new int[40]; } public void deal(){ int point = 0; result[point++] = 2; for(int i = 3;i100;i+=2){ if(isPrimeNumber(i)){ result[point++] = i; } } } 1 穷举 第017课 算法及数据结构 public boolean isPrimeNumber(int n){ for(int i = 2;iMath.sqrt(n)+1;i++){ if(n%i == 0){ return false; } } return true; } public static void main(String[] args) { // TODO Auto-generated method stub Qiongju qj = new Qiongju(); qj.deal(); for(int i =0;iqj.result.length;i++){ System.out.println(qj.result[i]); } } } 1 穷举 第017课 算法及数据结构 主要思想: 对所有可能为素数的数进行检验. 在能够简化的情况下要尽量的简化 首先要保证不遗漏,保证每一个可能的数都要检验到 1 穷举 第017课 算法及数据结构 2 递归 在程序设计中,函数直接或者间接调用其自身的方法叫做递归调用,简称递归.其设计方法被应用到很多特殊问题的解决上 函数A 函数B 函数C 第017课 算法及数据结构 递归要点： 每次递归调用都要使问题简单化 当递归达到某种程度后能够的到一个已知解以结束递归调用 2 递归 据说毕达哥拉斯理论家，又称一群在毕达哥拉斯(以毕达哥拉斯理论闻名)领导下工作的古希腊的数学家，发现了在数字序列1，3，6，10，15，21， ．．(省略号说明这个序列无限地继续下去) 中有一种奇特的联系。你能知道这个序列的下一个数字是什么吗? 例: 第017课 算法及数据结构 2 递归 第017课 算法及数据结构 这个数列中的第n项是由第n—1项加M得到的。由此，第二项是由第一顶(U加上2，得3。第三项是由第二项(3)加上3得到6*依此类推。 这个序列户的数字被称为三角数字，因为它们可以被形像化地表示成对象的一个三角形排列. 分析: 2 递归 第017课 算法及数据结构 2 递归 第017课 算法及数据结构 以Sn代表第n项的值,有如下表示: Sn = Sn-1+n 当n=1时 当n1时 Sn=1 2 递归 第017课 算法及数据结构 public int triangle(int num){ if(num == 1){ return 1; }else{ return triangle(num-1)+num; } } 代码表示如下: 当n = 1时,Sn = 1; 当n1时,Sn = Sn-1+n 2 递归 小结： 穷举算法 递归算法 第017课 算法及数据结构 1、简述穷举的要点 小测验： 第017课 算法及数据结构 2、简述递归的要点 封面 * * 这里主要思想是对所有可能为素数的数进行检验,如果成功就放入result[]中.在1—100中,1肯定不是素数,2一定是素数.其后的所有偶数均不是素数,基于以上分析则直接将2填入数组,后从3开始只取奇数进行检验.使每个可能的数都检验一次. 注意:首先要保证不遗漏,保证每一个可能的数都要检验到. 其次在能够简化的情况下要尽量的简化.穷举不是做无谓的运算. 如果直接从1—100每个去检验,这当然能够保证无一遗漏,但是这样的运算比较多.很明显除2外,所有偶数均不可能为素数,所以应该充分利用这个条件进行删减,