第五章算法实例的程序实现 本章小节课件（15张幻灯片）

课件15张PPT。第五章 本章小结枚举算法变形金刚装箱改进方案鸡兔同笼解析算法求解一元二次方程的解电阻计算电话费收费查找算法顺序查找对分查找排序算法插入排序选择排序冒泡排序递归算法求阶乘 n！求斐波那契数列要 点 回 顾1.枚举算法：确定可取值范围，判断是否满足条件。 例：百钱百鸡 应 用 举 例For a=0 to 20 For b=0 to 30 c=100-a-b If a*5+b*3+c/3=100 then2.解析算法：判断成立与不成立的所有条件情况。 例：一元二次方程If d > 0 then x1=(-b + sqr (d))/(2*a) x2=(-b – sqr (d))/(2*a) Else if d=0 then x1=x2 ‘两个相同的实数根’ else ‘无解’应 用 举 例应 用 举 例3.查找算法：以中间元素为界分为两个区间。 例：二分查找M=fix((i+j)/2)‘计算（i，j）的中间位置，进行折半查找’ If keyd(j+1) then ‘确定升序排序’ k=d(j): d(j)=d(j+1): d(j+1)=k ‘交换的d（j）与d(j+1)的值’应 用 举 例5.递归算法：把递归问题表达成一个公式或一组语句。 例：n! f(n)=n*f(n-1) (n>1) f(1)=1 (n=1)强化练习题：请同学们完成本节导学案！ 一、枚举算法：列举所有情况，逐个判断是否是问题的解。（鸡兔同笼、变形金刚等） 1.取1元、2元和5元的纸币各10张，使其总和为24元，输出所有不同的取法及个数。请将下面代码中的划线处填写完整：Private Sub Command1_Click()Dim sum As IntegerDim i As Integer, j As Integer, k As IntegerList1.ClearFor I = 1 To 10For j = 1 To 9For k = 1 To 4If_____ Then‘寻找满足条件的方案List1.AddItem ("1元：" + Str(i) + "张 2元：" + Str(j) + "张 5元：" + Str(k) + "张")sum = sum+1 ‘计算种数End IfNext kNext j_____Label1.Caption = "种数：" + Str(sum)End Sub i+j*2+k*5=24Next i强 化 练 习 题2.计算 的值。请将下面划线处的代码填写完整：Private Sub Command1_Click()Dim i As IntegerDim s As Doubles = 0For i = 1 To 50_____Next iText1.Text = Str(s)End Sub s = s + 1 / (2 * i - 1)二、解析算法：用公式直接求解问题的方式。（一元二次方程、电话收费等）三、查找算法：对分查找是一种效率较高的查找算法。 1.数组元素为：Alice、Byron、Duane、Elaine、Floyd、Gene、Herry、Iris，请回答：①哪个查找算法（顺序查找和对分查找）能比较快找到名字Gene? ②哪个查找算法（顺序查找和对分查找）能比较快找到名字Alice? ③当利用顺序查找算法查找名字Floyd时，查问了多少个数据？使用对分查找算法时，又要查问多少个数据？ (1)查找Gene：对分查找快，对分查找3次，顺序查找6次(2)查找 Alice：顺序查找快，顺序查找1次，对分查找4次(3)使用顺序查找Floyd，查找了5个数据，使用对分查找，查问了1个数据四、排序算法：调整数据在数组变量中的存储位置，使数组内的数据呈现某种次序。 1.如下程序段的功能是：随机产生10个1-100之间的正整数，按降序将10个数据排序输出。 为了实现这一目标，在划线处填入合适的语句或表达式。 Dim i as Integer , j as Integer, t as Integer , k as Integer n = 10 For i = 1 To n _____ Next i For i = 1 To n-1 k = i For j = i + 1 To n If _____Then k = j Next j If k<> i Then t = d(i): d(i) = d(k): d(k) = t End If Next id(i) = Int(Rnd*100) + 1d(j)>d(k)五、递归算法：一种直接或间接地调用自身的算法。 1.数列1，4，7，10，13，……的递归表达式为A . f(n)=n+3 ；f(1)=1 B. f(n)=n*2-1 ；f(1)=1C . f(n)=n*2+1 ；f(1)=1 D. f(n)=f(n-1)+3 ；f(1) ... ...