Bài tập về Đệ quy | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Bài tập về Đệ quy | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội. Tài liệu được biên soạn giúp các bạn tham khảo, củng cố kiến thức, ôn tập và đạt kết quả cao kết thúc học phần. Mời các bạn đọc đón xem!

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
| 1/3

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