BÀI T P VỀỀ Đ Ậ QUY Ệ
Bài 1: Lập mã giả đ quy và kh ệ đ ử quy cho hàm Fibonacci ệ Lời giải Input: n: N* MÃ GIẢ ĐỆ QUY FUNCTION: F[n](n: N*): N F[1] = F[2] = 1 if n <= 2 then return 1 return F[n] = F[n-1] + F[n-2] MÃ GIẢ KHỬ Đ QUY Ệ FUNCTION: F[n](n: N): N F[0] := 0, F[1] := 1 if n <= 1 then return 1 for i = 2 to n do F[i] := F[0] + F[1] F[0] := F[1] F[1] := F[i] return F[n] Output: F[n] Bài 2: L p mã gi ậ đ ả quy và kh ệ đ ử quy c ệ a hàm tm nghi ủ m gầần đúng r ệ oot(f,a,b) L i gi ờ ải
Input: f(x): function of x, a: R, b: R MÃ GI Đ Ả QUY Ệ
FUNCTION: root(f(x): function of x; a, b: R) = c[i]: R a := c[1], b := c[2]
if f(a)*f(b) > 0 then return “không có nghi m trong kho ệ ng (a,b)” ả if f(a)*f(b) = 0 then if f(a) = 0 then return c[1] return c[2] for i >=3 to n do c[i] := (c[i-2] + c[i-1])/2
If f(c[i-2])*f(c[i]) < 0 then c[i-2] := c[i-1] := a, c[i] := b
c[i] := c[i-1] := a, c[i-1]: = c[i] := b return c[n] MÃ GI KH Ả Ử Đ QUY Ệ
FUNCTION: root(f(x): function of x; a, b: R) = c: R
if f(a)*f(b) > 0 then return “không có nghi m trong kho ệ ng (a,b)” ả if f(a)*f(b) = 0 then if f(a) = 0 then return a return b while f(a)*f(b) < 0 do c := (a+b)/2
if f(a)*f(c) < 0 then c := b c := a Output: c