3 trang 59 lượt tả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

118

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) 133 tài liệu

Trường: Đại học Bách Khoa Hà Nội 2.8 K tài liệu

Tác giả:

Profile

Thùy Dương

1 năm trước
Danh sách Quiz
/3
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

Tài liệu khác của Đại học Bách Khoa Hà Nội

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

Tài liệu liên quan: