新概念c语言程序设计ppt课件.ppt

《新概念c语言程序设计ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章算法设计策略4.1分治策略4.2回溯策略4.3贪心策略4.4分枝界定策略4.5动态规划算法设计策略4.1分治策略任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。直接求解一个规模较大的问题，往往是相当困难的。但是当问题的规模缩小到一定程度时，一个量变到质变的现象就可能发生，问题的求解变得比较容易。这时，如果能找到小规模的该类问题与大规模的该类问题之间的关系，就可以使用分治策略对大规模的问题进行求解了。分治法所能解决的问题一般具有以下几个特征：（1）该问题可以分解为若干个规模较小的相同问题。（2）各个子问题相互独立，子问题之间不包含公共的子

2、子问题。（3）该问题的规模缩小到一定的程度可以容易地求解。（4）利用该问题分解出的子问题的解可以合并为该问题的解。4.1.1二分查找4.1.2快速排序4.1.3自行车带人问题分治法往往要依靠递归过程，并且大致有如下三个步骤：·分解：将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题。·解决：若子问题规模较小而容易被解决则直接解决，否则递归地解决各个子问题。·合并：将各个子问题的解合并为原问题的解。这一节，介绍几种使用分治策略的例子。4.1.1二分查找一、问题描述在N个已排序（设为从小到大）的数据（数或字符串），查询某一个数据：如果找到了，就

3、指出其在N个数据中的位置；否则给出无该数据的信息，如给出“-1”。查询是在一个数据集中，查找给定数据的过程。查询的结果有两种情形：找到给定的数据，并给出其位置；找不到给定数据。二、算法分析采用二分法求解本问题的基本思路是：如图4.1所示，设数列为a1、a2、…an，被查找的数据为x，则查找首先对am(m=(1+n)/2)进行，于是得到如下3种情形：·若x>am，则x可能在区间[am+1,an]中。·若x

4、的搜索范围内按上述原则进行搜索，不断二分，直到得出结论（找到或找不到）为止。a1a2……amam＋1…x…an第1次smr第2次s’r’图4.1二分查询为了使算法更具一般性，设数列为as、as+1、…、ar、s为数列的起始元素序号（开始时为1），r为数列的终止元素序号（开始时为n），则利用二分查找法在其中找出元素x的递归函数binsrch（s,r,x）可描述为：binsrch（s,r,x）{m=(s+r)/2;if(x==am)打印找到信息后返回;elseif(s>=r)打印找不到信息,结束程序执行;elseif(x>am)调用函数binsrch（m+1

5、,r,x）;else调用函数binsrch（s,m-1,x）;}三、程序includefloata[10]={1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9};/*数组声明及初始化，外部数组*/voidmain(){floatx=2.3;ints=0,r=9;voidbinsrch(ints,intr,floatx);/*函数声明*/binsrch(s,r,x);/*函数调用*/}三、程序（续）voidbinsrch(ints,intr,floatx){intm;m=(s+r)/2;if(a[m]==x)

6、{printf("Theorderof%5.1fis%dinthissequence.",x,m+1);return;}elseif(s>=r){printf("%fisnotexistintheseguense.",x);exit(-1);}elseif(x>a[m])binsrch(m+1,r,x);/*递归调用*/elsebinsrch(s,m-1,x);/*递归调用*/}四、说明1.外部数组在本例中，声明语句floata[10]={1.1,1.3,1.5,1.7,1.9,2.1,2.3,2.5,2.7,2.9};定义在所有函数的外部，即不在任何一

7、个函数内。这种定义在函数外部的数组，称为外部数组。一般来说，定义在外部的变量称为外部变量。外部变量是在每一个函数中都可以使用的变量。相对而言，前面使用过的、定义在某一个函数内部的变量称为局部变量，它只能在所定义的局部使用。五、编程练习1.用二分法求一元方程式的根（提示：用二分迭代法）。2.用二分法计算xn的值（提示：当n为偶数时，使用xn=xp*xp；当n为奇数时，使用xn=x*xp*xp）。3.用二分法找出一个数组中的最大值和最小值。4.1.2快速排序一、快速排序的基本思想：快速排序（quicksort）是由著名计算机科学家C.A.R.Hoare根据分

8、治策略给出的一种高效率的排序方法。它的基本思想是：在待排序序列中选定一个元素X(