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!
Môn: Cấu trúc dữ liệu và giải thuật (ET2100)
Trường: Đại học Bách Khoa Hà Nội
Thông tin:
Tác giả:
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