算法与程序设计(备课)

1、算法的概念与程序设计刘启明第4节 算法的概念与程序设计【本章提要】 针对部分模块进行讨论，研究其教学内容、教学处理要点和教学中应注意的问题。 一、算法二、算法与程序三、重要的循环算法和递归算法四、排序问题五、常用算法 一、算法1算法：对特定问题的求解步骤。2算法复杂度3算法的特征：有穷性、确定性、可行性4计算方法：对求数值解的近似方法的研究【注意事项】计算机求解的问题：有两大类（数值和非数值）【例题】交换两个变量的值 算法atbba 算法main() float a,b,t; scanf(%f,%f,&a,&b); if(ab) t=a;a=b;b=t； printf(%5.2f,%5.2fn

2、,a,b); 二、算法与程序 【程序两要素】瑞士科学家沃思（Niklaus Wirth) 有 一个著明的公式 程序=算法(操作步骤)+数据结构（原料） 【说明】高级语言的数据类型非常丰富，如：字符型、整型、实型、逻辑型等。 【数组的概念】 一组 相关数据的集合，它在内存中开辟了若干个连续的存储单元，依次存储。算法与程序 算法表示：(1)自然语言(2)传统流程图(3)N-S结构图：又称纳萨施内德曼图 （Nassi-Sschneiderman). 结构化程序设计（三种基本结构）【例题】求3个数中最小数 main() int a,b,c,t; printf(请输入三个整数:); scanf(%d,%

3、d,%d,&a,&b,&c); if(ab) t=a;a=b;b=t; if(ac) t=a;a=c;c=t; printf(三个整数中最大得是%dn,a); a bYN交换a cYN交换a dYN交换i = 1 to n-1min ai YN交换 三、重要的循环算法和递归算法循环算法两类具有代表性的算法（穷举和迭代）循环控制的方法（计数标志）例如：迭代算法的教学（二分法牛顿切线）掌握知识与培养能力的统一主体与客体的统一【教案】用牛顿迭代法求下面方程在1.5附近的根。典型的递归算法Hanoi（汉诺）塔问题： 古代有一个梵塔，塔内有3个座A、B、C，开始时A座上有64个盘子，盘子大小不等，大的在

4、下，小的在上。有一个老和尚想把这64个盘子从A盘移到C座，但每次只允许移动一个盘子，且在移动过程中在3个座上都始终大盘在下，小盘在上。在移动过程中可以利用B座，要求编程序打印出移动步骤。 算法的演示图示如下所示：典型的递归算法ABC132 四、排序问题例如：排序问题（n个元素排队） 对数据进行排序有哪些方法可以实现？ 快速排序、 冒泡排序、 希尔排序、 插入排序、 归并排序采用冒泡排序方法对待排序的序列进行排序。 定义一个大小为6的数组a6 a1 a2 a3 a4 a5 a6初始 9 6 5 7 4 3一次后 6 9 5 7 4 3二次后 6 5 9 7 4 3三次后 6 5 7 9 4 3四

5、次后 6 5 7 4 9 3五次后 6 5 7 4 3 9第一趟冒泡排序最大值注：经过第一趟冒泡排序，我们找出了待排序序列中的最大值9，最大值9存放在了数组a的最后一个位置。 a1 a2 a3 a4 a5 a6初始 6 5 7 4 3 9一次后 5 6 7 4 3 9二次后 5 6 7 4 3 9三次后 5 6 4 7 3 9四次后 5 6 4 3 7 9 第二趟冒泡排序注：经过第二趟冒泡排序后，我们找到了次大值7，次大值7存放在数组a的倒数第二个位置a5次大值最大值流程图是用一些图框表示各种操作。用图形表示算法，直观形象、易于理解。 N-S流程图-全部的算法写在一个矩形框内，在框内还可以包含

6、其他的从属于它的框，或者说，由一些基本的框组成一个大的框。这种流程图又称为N-S结构化流程图。据此在这里我们可画出上述冒泡排序算法的N-S流程图 描述算法 输入n个数给a1到anfor i=1 to n-1for j=1 to n-iajaj+1真假ajaj+1输出a1到an冒泡排序算法N-S流程图N-S图描述算法依次对数据序列进行冒泡排序：第三趟冒泡排序结果 5-4-3-6-7-9第四趟冒泡排序结果 4-3-5-6-7-9第五趟冒泡排序结果 3-4-5-6-7-9最后我们得到从小到大的顺序序列为： 3-4-5-6-7-9对n个数据进行排序，需进行n-1趟的冒泡排序；每趟冒泡排序过程中，（第i趟冒泡排序中）两两数据比较进行了n-i次 程序如下所示：main() int a6; int i,j,t; printf(“input 6 numbers:n”); for(j=1;j=6;j+) scanf(“%d”,&ai); for(j=1;j6;j+) for(i=1;iai+1) t=ai;ai=ai+1;ai+1=t; printf(“the ordered numbers:n”); for(i=1;i=6;i+) printf(“%d”,ai);