第五章算法与数据结构 程序是建立在数据结构基础上使用计算机语 描述的算法,因此简单地讲,程序也可以 表示成:算法十数据结构。 介绍算法的概念及常用算法。并通过数组、 链表、栈、队列等数据结构以及]ava对象容 器,讨论算法的应用及算法的]ava程序实现
Java程序设计大学教程 第五章 算法与数据结构 程序是建立在数据结构基础上使用计算机语 言描述的算法，因此简单地讲，程序也可以 表示成：算法＋数据结构。 介绍算法的概念及常用算法。并通过数组、 链表、栈、队列等数据结构以及Java对象容 器，讨论算法的应用及算法的Java程序实现
5.1算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序列 的规则集合。一个算法应该具有以下五个重要的特征: 确切性( No ambiguity)算法的每一步骤必须有确切的定 义。而不应该有二文性,例如,在算法中不能出现诸如“赋值为 100或1000”。 输入( Input)有0个或多个输入,用于初始化运算对象。所 谓0个输入是指无需输入条件,而算法本身定出了初始条件。 输出( Output)没有输出的算法是毫无意义的。一个算法应 该有一个或多个输出,以反映对输入数据加工后的结果。 可行性( Feasibility)算法原则上能够精确地运行,而且对 于算法中的每种运算,在原理上人们应该能用笔和纸做有限次运 算后完成 有穷性( Finite)算法必须保证执行有限步之后结束。只具有 前面四个特征的规则集合,称不上算法。例如,尽管操作系统能 完成很多任务,但是它的计算过程并不终止,而是无穷无尽的执 行、等待执行,所以操作系统不是算法
Java程序设计大学教程 5.1 算法 算法是为了求解某一问题在有限步骤内、定义了具体操作序列 的规则集合。一个算法应该具有以下五个重要的特征 ： ◼ 确切性（No ambiguity） 算法的每一步骤必须有确切的定 义。而不应该有二义性，例如，在算法中不能出现诸如“赋值为 100或1000”。 ◼ 输入（Input） 有0个或多个输入，用于初始化运算对象。所 谓0个输入是指无需输入条件，而算法本身定出了初始条件。 ◼ 输出（Output） 没有输出的算法是毫无意义的。一个算法应 该有一个或多个输出，以反映对输入数据加工后的结果。 ◼ 可行性（Feasibility） 算法原则上能够精确地运行，而且对 于算法中的每种运算，在原理上人们应该能用笔和纸做有限次运 算后完成。 ◼ 有穷性（Finite） 算法必须保证执行有限步之后结束。只具有 前面四个特征的规则集合，称不上算法。例如，尽管操作系统能 完成很多任务，但是它的计算过程并不终止，而是无穷无尽的执 行、等待执行，所以操作系统不是算法
5.1.1算法的描述 伪代码描述的算法: Java代码实现: 1.X←0 2 ttt xyz 000 3.z←0 4. while x< 100 Whe(x<100){ X=X+1 4.1dox←X+1 y =x+y 4.2y←x+y for(int t=0 t<=10, t++)t 4.3fort←0to10 Z=(z+X*y)/100; 4.3.1doz←(z+X*y) do i 4.3.2 repeat 4.3.2.1y←y+1 Z=Z- yi 4.3.2.2z←z-y }Whe(z<0); 4.3.3. until z<0 Z=X y 4.4.z←X*y 5.y←y/2 y=y/2;
Java程序设计大学教程 5.1.1 算法的描述 1、伪代码描述 : 伪代码（Pseudo-code）是一种算法描述语 言。使用伪代码的目的是为了使被描述的算 法可以容易地以任何一种编程语言（如 Pascal、C、Java等）实现。因此，伪代码 必须结构清晰，代码简单，可读性好，并且 类似自然语言。 伪代码描述的算法： 1. x ← 0 2. y ← 0 3. z ← 0 4. while x < 100 4.1 do x ← x + 1 4.2 y ← x + y 4.3 for t ← 0 to 10 4.3.1 do z ← ( z + x * y ) / 100 4.3.2 repeat 4.3.2.1 y ← y + 1 4.3.2.2 z ← z - y 4.3.3. until z < 0 4.4. z ← x * y 5. y ← y / 2 Java代码实现： int x = 0; int y = 0; int z = 0; while ( x < 100 ) { x = x + 1; y = x + y; for ( int t = 0 ,t <= 10 , t++ ) { z = ( z + x * y ) / 100; do { y = y + 1; z = z - y; } while (z < 0); }; z = x * y; } y = y / 2;
5.1.1算法的描述 2、图形描述: 程序设计中,能够用来表示算法基本概念的 图主要有:PAD图、N\S盒图、流程图 端点符 三处理 判断 预定义处 连接符三 处理 处理1 条件 处理 否、 处理1 处理2 条件 处理2 条 否 while-do) 顺序结构 选择结构 循环结构 程序流程图常用图形符号及控制结构图例
Java程序设计大学教程 5.1.1 算法的描述 2、图形描述 : 程序设计中，能够用来表示算法基本概念的 图主要有：PAD图、N\S盒图、流程图。 处理1 处理2 处理1 处理2 处理 条件 否 、 是 条 件 处理 是 条件 否 、 端点符 处理 判断 预定义处 理 连接符 顺序结构 选择结构 (while-do) (repeat-until) 循环结构 程序流程图常用图形符号及控制结构图例
Java语言实现: 2. import java. io. 3. public class Max i 4. public static void main(String[] args) throws IOException t 5 /初始化 6 Buffered Reader input new Buffered Reader (new InputStream Reader (system. in); 8 int largest=0; 9 int counter=0 10 int theInteger=0 11 ∥/循环比较 2, while( counter 10)t 13 //输入被比较的数 14 counter++;//计数 System. out printIn("请输入第"+ counter+"个被比较的数:") 16 String inputstring input readline i theInteger Integer. parseInt(inputstring; 18 /大值比较 19 if (theInteger> largest) largest=theInteger; 20 3// while 21 System. out. printin("求出最大数是:"+ argest); 22.} 23. 24.}
Java程序设计大学教程 5.1.2 常用算法 ◼ 基本算法大 都比较简单， 是其他算法 的基础。这 类算法在程 序中应用非 常普遍，如： 累加求和、 累乘求积、 求最大和最 小值等。 从10个数中求最大值算法 的例子 开始 初始化，将largest和counter设为0 计数器判断 counter <10 ? 否 、 是 while-do 循环 largest←theInteger 大值比较 theInteger>larges? 否 、 是 返回largest 结束 输入被比较的数theInteger 计数：counter←counter+1 伪代码描述算法： FindLargest Input: 10 positive integers 1. largest←0 2. counter←0 3. while(counter < 10) 3.1 Input theInteger 3.2 if (theInteger > largest) then 3.2.1 largest←theInteger end if 3.3 counter←counter+1 end while 4. Return largest End 1. Java语言实现： 2. import java.io.*; 3. public class Max { 4. public static void main(String[] args) throws IOException { 5. //初始化 6. BufferedReader input = new BufferedReader 7. (new InputStreamReader(System.in)); 8. int largest=0; 9. int counter=0; 10. int theInteger=0; 11. //循环比较 12. while(counter < 10) { 13. //输入被比较的数 14. counter++;//计数 15. System.out.println("请输入第"+counter+"个被比较的数:"); 16. String inputString = input.readLine(); 17. theInteger = Integer.parseInt(inputString); 18. //大值比较 19. if (theInteger > largest) largest=theInteger; 20. }// while 21. System.out.println("求出最大数是："+largest); 22. } 23. 24.}