第四章归纳与递回-大叶大学.ppt

Ch4-* Example 5. Search x in a1, a2,…,an by Linear Search Sol : Alg. 5 procedure search (i, j, x: integers) if ai = x then location := i else if i = j then location := 0 else search(i+1, j, x) 從ai,ai+1,…aj 中找 x call search(1, n, x) (跳過) Ch4-* Example 6. Search x from a1,a2,…,an by binary search (recursive version). Sol : Alg. 5 procedure binary_search (x , i , j: integers) m := ?(i+j) / 2? if x = am then location := m else if (x am and i m) then binary_search(x, i, m-1) else if (x am and j m) then binary_search(x, m+1, j) else location := 0 call binary_search(x, 1, n) search x from ai, ai+1, …, aj 表示左半邊 ai, ai+1, …, am-1 至少還有一個元素 (跳過) Ch4-* Example 1. Give the value of n!, n?Z+ Sol : Note : n! = n ? (n-1)! Alg. 1 (Recursive Procedure) procedure factorial (n: positive integer) if n = 1 then factorial (n) := 1 else factorial (n) := n ? factorial (n-1) Alg. (Iterative Procedure) procedure iterative_factorial (n : positive integer) x := 1 for i := 1 to n x := i ? x { x = n! } (跳過) Ch4-* ※ iterative alg. 的計算次數通常比 recursive alg.少 ※ Find Fibonacci numbers (Note : f0=0, f1=1, fn=fn-1+fn-2 for n?2) Alg. 7 (Recursive Fibonacci) procedure Fibonacci (n : nonnegative integer) if n = 0 then Fibonacci (0) := 0 else if n = 1 then Fibonacci (1) := 1 else Fibonacci (n) := Fibonacci (n-1)+Fibonacci (n-2) (跳過) Ch4-* Alg.8 (Iterative Fibonacci) procedure iterative_fibonacci (n: nonnegative integer) if n = 0 then y := 0 // y = f0 else begin x := 0 y := 1 // y = f1 for i := 1 to n-1 begin z := x + y x := y y := z end end {y is fn } Exercise : 11, 35 i = 1 i = 2 i = 3 z f2 f3 f4 x f1 f2 f3 y f2 f3 f4 (跳過) * * * * * * * * * * * * *