java程序设计-5-算法设计基础

《java程序设计-5-算法设计基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Java程序设计第五章：算法设计基础1Java程序设计学习目标：掌握求解素数的方法掌握顺序查找方法和折半查找方法掌握插入排序方法、冒泡排序法、选择排序法掌握递归的基本概念及设计方法2Java程序设计5.1求解素数什么是素数素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如：2，3，5，7，11等。Java程序设计3求解素数算法验证一个正整数n(n>3)是否为素数，一个最直观的方法是看在2～n/2中能否找到一个整数m能将n整除。若m存在，则n不是素数；若找不到m,则n为素数。这是一个循环验证算法。这个循环结构用下列表达式控制：初值：m=2；循环条

2、件：m<=n/2；修正：m++；注：它的作用是穷举2～n/2中的各m值。循环体是判断n是否可以被m整除。4Java程序设计publicclassPrimeApp{publicstaticvoidmain(String[]args){intm,n;//变量n为要判断的数字System.out.println("100以内的素数有：");A:for(n=2;n<=100;n++){for(m=2;m

3、1：求解100以内的全部素数5.2查找Java程序设计6什么是查找查找指在一个数据元素集合中查找关键字或等于某个给定关键字数据元素的过程，是对数据进行操作或处理时经常使用的操作。在计算机应用系统中使用查找的地方有很多，比如高考学生成绩管理系统中的高考学生成绩表中查找考生号码等于某个号码的考生成绩，或是从一批图书中找出某一本图书等。5.2.1顺序查找Java程序设计7查找最简单的方法是“顺序查找法”，即一个一个数据查找，看是否是所需的数据。例如5-2的程序在运行时查找从命令行输入的参数是否在数组中。程序5-2顺序查找Java程序设计8publicclassSequenceSearchAp

4、p{publicstaticvoidmain(String[]args){String[]arr={"张三","李四","王五","赵六"};Stringtemp=args[0];for(inti=0;i

5、个，则需要取数据和比较数据1000次，对n个数据的取数和比较的平均次数为n/2次。5.2.2折半查找折半查找法是一种效率较高的查找方法；用折半查找法的前提是：数据已按一定的规则（升序或降序）排列好。其基本思路是：先检索居中的一个数据，看它是否为所需的数据，如果不是，则判断要找的数据是在居中数的哪一边，下次就在这个范围内查找。Java程序设计10折半查找算法-111Java程序设计假如有一组数为：8，13，21，28，35，41，52，63，71，76，81，95，101，150，164要找21这个数。为了直观，把这15个数画成如图5-2所示的倒立的树形。“树”的根在上面，“树枝”和“树

6、叶”在下面，每一个数据称了一个“结点”。树根结点是15个数中居中的数（63），它有两个“子结点”，左边的比它小，右边的比它大，以下逐级都是按这个规律。可按以下步骤查找：折半查找算法-2先将要找的数21与数列中“树根结点”比较，由于21<63，因此，21显然在63左面的范围内，而且是第1个数到第7个数之间的一个数（由于21<63，所以已知道不可能是第8个数）。再找1～7个数中居中位置的一个数（第4个数），即28，将21与28相比，由于21<28，因此，所找的数必然在第1～3个数范围内。再找第1～3个数的居中位置的一个数13（即第2个数）,将21与13相比，由于21>13，因此，21必然在

7、13的右面。由于21下面不再分支，因此下一次就直接找到21。以上一共查找了四次（即树的深度或树的层次），就找到所需的数。12Java程序设计程序5.3折半查找-1Java程序设计13publicclassBinaraySearchApp{publicstaticvoidmain(String[]args){intmid,low,high;int[]arr={8,13,21,28,35,41,52,63,71,76,81,95,101,150,1