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!

53 27 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

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:

3 trang 6 tháng trước

Tác giả:

Profile Thùy Dương
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
| | Tải xuống

Có thể bạn quan tâm:

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