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 root(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

Preview text:

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