Bài giảng Cấu trúc dữ liệu: Chương 1 - Trịnh Xuân
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.03 MB, 10 trang )
! Hình
CẤU TRÚC DỮ LIỆU
tính điểm:
CC: 10%
" Điểm GK: 20%
" Điểm thi: 70%
! Bài tập lớn
! Test Bài tập lớn
" Điểm
Web: //sites.google.com/site/trinhxuan
1
*Tài liệu học tập:
! Giáo
# Hiểu
trình bắt buộc
# Biết
trình Cấu trúc dữ liệu – Khoa CNTT,
Viện ĐH Mở HN – Lưu hành nội bộ
được khái niệm CTDL và Thuật toán
được các CTDL cơ bản: Mảng, Danh sách
# Hiểu
và vận dụng được một số CTDL đặc biệt:
Hàng đợi, Ngăn xếp, Cây, Đồ thị
" Đỗ
Xuân Lôi, “Cấu trúc dữ liệu và giải
thuật”, NXB Khoa học và kỹ thuật.
" Introduction to Algorithms – The cormen
# Hiểu
và áp dụng được một số thuật tốn cơ bản:
Tìm kiếm, Sắp xếp, …
3
*Nội dung môn học
CTDL – Khoa CNTH – Viện ĐH Mở HN
2
cách đánh giá độ phức tạp của một thuật tốn
# Nắm
trình tham khảo
CTDL – Khoa CNTH – Viện ĐH Mở HN
CTDL – Khoa CNTH – Viện ĐH Mở HN
Mục đích mơn học
" Giáo
! Giáo
4 SV
! Cách
Khoa Công nghệ thông tin
Email:
Thời lượng: 60 tiết – LT
CTDL – Khoa CNTH – Viện ĐH Mở HN
thức thi: BTL
" Nhóm
5
CTDL – Khoa CNTH – Viện ĐH Mở HN
4
STT
SỐ
TIẾT
NỘI DUNG GIẢNG DẠY
1
5
Đánh giá Thuật Toán - Phân công BTL
2
5
TK và SX
x
3
5
TK và SX
x
4
5
Thực hành mảng - Test
x
5
5
DSLK Đơn
x
6
5
Thực hành DSLK Đơn - Test
x
7
5
Danh sách liên kết đôi
x
8
5
Stack - Queue
x
9
5
Cây
x
10
5
Cây - Test
x
11
5
Đồ thị
x
12
5
Test BTL – Đánh giá sơ bộ - TH
x
CTDL – Khoa CNTH – Viện ĐH Mở HN
Y/C
Đọc TL
Ghi chú
Các buổi
Thực hành có
thể mang máy
tính cá nhân
đi thực hành
6
Lưu ý sử dụng Phòng máy
Yêu cầu kiến thức cần có
! Xem
! Sử
dụng điều hịa: Phải đăng ký và mất phí
! Tổng số buổi thực hành: 03 buổi
! Tổng phí phải nộp: 600.000đ (200.000/1 buổi)
" Phí
! Lớp
! Nội
Cấu trúc chương trình
Khai báo biến
" Nhập/xuất dữ liệu
" Cấu trúc điều khiển
" Mảng
" Chuỗi
" Chương trình con – hàm
" Cấu trúc
" Con trỏ
" File
" …
"
"
tính trên 1 sinh viên: 10.000đ/3 buổi
trưởng thu giúp
! Cách
thức thực hiện:
" Buổi
" Buổi
1: Thu thập nguyên vọng sử dụng điều hòa
2+3: Thu tiền sử dụng điều hòa
! Nguyên
và tổng hợp lại ngôn ngữ C
dung cần tổng hợp lại:
tắc số ít theo số nhiều
CTDL – Khoa CNTH – Viện ĐH Mở HN
7
CTDL – Khoa CNTH – Viện ĐH Mở HN
8
I. Giới thiệu
! Các
CHƯƠNG I:
bước để xây dựng bài toán tin học trong máy tính
Bài tốn
thực tế
u cầu
CÁC KHÁI NIỆM
CƠ BẢN
Giải thuật
Thuật toán
Xây dựng một bài toán tin
học thực chất là chuyển một
bài toán thực tế thành một
bài toán giải quyết được
bằng máy tính
CTDL – Khoa CNTH – Viện ĐH Mở HN
9
#include
…
Lập trình
Thiết kế
Chương trình
• Ngơn ngữ lập trình:
• PASCAL,
• C/C++,
• JAVA,
• Visual Basic
• …
CTDL – Khoa CNTH – Viện ĐH Mở HN
10
1. Xác định bài tốn
II. Các bước xây dựng chương trình
Xác định bài toán
# Xác định xem ta phải giải quyết vấn đề gì?
# Xác định yêu cầu cần thực hiện của bài tốn $ các thao
tác cần thực hiện
Tìm CTDL biểu diễn bài tốn
Tìm thuật tốn
# Các bài tốn tin học cần phải chỉ ra lời giải tốt nhất bởi
vì nếu khơng lời giải đó có thể địi hỏi nhiều thời gian và
chi phí.
Lập trình
Kiểm thử
Tối ưu chương trình
CTDL – Khoa CNTH – Viện ĐH Mở HN
11
CTDL – Khoa CNTH – Viện ĐH Mở HN
12
2. Tìm CTDL biểu diễn bài tốn
3. Tìm thuật tốn
% Xác định input và output của bài toán
% Input: dữ liệu đầu vào
% Output: Kết quả mong muốn đạt được
% Xác định hệ thống chặt chẽ và rõ ràng các quy tắc để
từ Input có được Output
% Xác định dãy thao tác trên CTDL đầu vào để giải
quyết yêu cầu bài tốn
Các tiêu chuẩn:
# Biểu diễn đầy đủ các thơng tin nhập và xuất của bài toán
# Phải phù hợp với các thao tác của thuật toán mà ta lựa
chọn để giải quyết bài toán
# Cài đặt được trên máy tính với một ngơn ngữ lập trình
xác định
CTDL – Khoa CNTH – Viện ĐH Mở HN
Đảm bảo
# Mỗi bước thao tác rõ ràng
# Khơng được rơi vào q trình vơ hạn
# Sau khi thực hiện các bước phải cho kết quả đúng
# Phải đảm bảo cài đặt được chương trình
13
4. Lập trình
# Kiểm tra lỗi chương trình
# Lỗi cơ bản
& Lỗi cú pháp
& Lỗi cài đặt
& Lỗi thuật tốn
# Thơng thường ta khơng nên cụ thể hóa ngay tồn bộ
chương trình mà nên tiến hành theo phương pháp tinh
chế từng bước
# Lập bộ test để kiểm thử
# Nguyên tắc
% Ban đầu, thể hiện thuật toán với các bước tổng thể, mỗi bước
nêu lên một công việc phải thực hiện
% Một công việc đơn giản hoặc là một đoạn chương trình đã
được học thuộc thì ta tiến hành viết mã lệnh ngay bằng ngơn
ngữ lập trình
% Một cơng việc phức tạp thì ta lại chia thành những công việc
nhỏ hơn để lại tiếp tục với những cơng việc nhỏ hơn đó.
# Ngun tắc xây dựng bộ test
& Bắt đầu với bộ test nhỏ, đơn giản,
& Tiếp theo vẫn là các bộ test nhỏ, nhưng chứa các giá
trị đặc biệt hoặc tầm thường.
& Các bộ test phải đa dạng, tránh sự lặp đi lặp lại
& Có một vài bộ test lớn
15
CTDL – Khoa CNTH – Viện ĐH Mở HN
16
III. CTDL và Thuật toán
6. Tối ưu chương trình
! Xây
# Đặt mục tiêu viết chương trình sao cho đơn giản, làm
sao chạy ra kết quả đúng, sau đó ta xem lại những chỗ
nào viết chưa tốt thì tối ưu lại mã lệnh để chương trình
ngắn hơn, chạy nhanh hơn
dựng một bài toán cần:
định Cấu trúc dữ liệu
" Xác
! Đối
tượng dữ liệu dùng trong bài toán $ Tổ chức biểu
diễn được đối tượng
" Xác
# Không nên viết tới đâu tối ưu tới đó, bởi chương trình
có mã lệnh tối ưu thường phức tạp và khó kiểm sốt.
định Thuật tốn
! Các
u cầu xử lý trên đối tượng đó $ Xác định và
xây dựng thao tác xử lý trên đối tượng
# Tiêu chuẩn tối ưu
& Tính tin cậy
& Tính uyển chuyển
& Tính trong sáng
& Tính hữu hiệu
CTDL – Khoa CNTH – Viện ĐH Mở HN
14
5. Kiểm thử
# Xác định ngơn ngữ lập trình được sử dụng
CTDL – Khoa CNTH – Viện ĐH Mở HN
CTDL – Khoa CNTH – Viện ĐH Mở HN
CTDL + Thuật toán = Chương trình
Structure Data + Algorithm = Program
17
CTDL – Khoa CNTH – Viện ĐH Mở HN
18
a. Cấu trúc dữ liệu – Structure Data
! Cấu
trúc dữ liệu là một cách để tổ chức và
lưu thông tin các đối tượng bài tốn (thực tế)
vào trong máy tính sao cho nó có thể được sử
dụng một cách hiệu quả
! Các kiểu cấu trúc dữ liệu cơ bản:
" Mảng, Bản ghi
" Danh sách liên kết, Ngăn xếp, Hàng đợi
" Cây
" Đồ thị
CTDL – Khoa CNTH – Viện ĐH Mở HN
19
b. Thuật tốn - Algorithm:
chính xác
! Tính rõ ràng
! Tính khách quan
! Tính phổ dụng
! Tính kết thúc
Output
CTDL – Khoa CNTH – Viện ĐH Mở HN
21
CTDL – Khoa CNTH – Viện ĐH Mở HN
22
a. Độ phức tạp không gian:
IV. Đánh giá độ phức tạp thuật tốn
! Các
tiêu chí lựa chọn thuật toán:
Thuật toán đơn giản, dễ hiểu.
" 2. Thuật toán dễ cài đặt (dễ viết chương trình)
" 3. Thuật tốn cần ít bộ nhớ
" 4. Thuật tốn chạy nhanh
! Là
tổng số chi phí về mặt khơng gian (bộ
nhớ) cần thiết sử dụng cho thuật toán $
đánh giá dựa vào tổng số bộ nhớ khai báo
cho các biến
" 1.
! =>
để đánh giá thuật tốn dựa vào độ phức tạp
thuật tốn
! Chi
phí bộ nhớ gồm:
dữ liệu vào - input
" Lưu dữ liệu ra - output
" Lưu các kết quả trung gian - temp
" Lưu
! Độ
phức tạp thuật toán được thể hiện qua:
gian
" Thời gian
" Khơng
CTDL – Khoa CNTH – Viện ĐH Mở HN
20
! Tính
tốn, cịn gọi là giải thuật
" là một bộ các qui tắc hay qui trình cụ thể nhằm
giải quyết một vấn đề nào đó trong một số bước
hữu hạn,
" hoặc cho ra một kết quả (output) từ một tập hợp
của các dữ liệu đưa vào (input)
Thuật toán
CTDL – Khoa CNTH – Viện ĐH Mở HN
* Tính chất của thuật tốn
! Thuật
Input
Các yếu tố xác định một kiểu CTDL:
" Tên kiểu CTDL
" Miền giá trị
" Kích thước lưu trữ
" Tập các tốn tử (thao tác) thực hiện trên kiểu dữ liệu đó
! Các tiêu chuẩn đánh giá một CTDL:
" Phản ảnh đúng thực tế
" Phù hợp với thao tác xử lý
" Tiết kiệm tài nguyên hệ thống
! Một cấu trúc dữ liệu được thiết kế tốt cho phép:
" Thực hiện nhiều phép toán,
" Sử dụng càng ít tài ngun,
" Thời gian xử lý và khơng gian bộ nhớ tốt
!
23
CTDL – Khoa CNTH – Viện ĐH Mở HN
24
b. Độ phức tạp thời gian:
VD: Xác định độ phức tạp thuật toán
int sum (int n)
{
int sum, i ;
sum = 0;
i = 1;
! là
tổng thời gian cần thiết để hoàn thành thuật toán
đánh giá dựa vào số lượng các thao tác được sử
dụng trong thuật toán dựa trên bộ dữ liệu đầu vào
! Các thao tác được xem xét:
" Phép so sánh
" Phép cộng, trừ, nhân, chia, …
" Phép toán thay đổi
" Phép gán
" Phép trả lại giá trị
" …
! Khi xét độ phức tạp thuật toán chỉ tập trung vào độ phức
tạp tính tốn (độ phức tạp thời gian)
! Được
CTDL – Khoa CNTH – Viện ĐH Mở HN
n Unit (n Comparison)
while (i < n)
{
sum = sum + i;
i = i+ 1;
}
return sum;
}
2 x (n-1) Unit
2 x (n-1) Unit
1 Unit
T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1""
25
CTDL – Khoa CNTH – Viện ĐH Mở HN
26
*Phân loại đánh giá:
VD: Xác định độ phức tạp không gian và thời gian thuật toán
5"
int Sum (int n)
{
int sum ;
sum =0;
5
3
10 13
Best Case
for ( int i =0 ; i
}
No time
1 Unit
1 Unit
6
9
15 21 12
8
61 39
39"
Worst Case
Average Case
% Thời gian chạy trong trường hợp tốt nhất (best-case running time)
Là thời gian chạy nhỏ nhất (1 lần chạy) của thuất tốn đó trên tất cả dữ liệu vào
cùng cỡ
return sum;
% Thời gian chạy trong trường hợp xấu nhất (worst-case running time)
Là thời gian chạy lớn nhất của thuật toán đó trên tất cả các dữ liệu vào cùng cỡ,
% Thời gian chạy trung bình (average running time)
Là số trung bình cộng của thời gian chạy của thuật tốn đó trên tất cả các dữ
liệu vào cùng cỡ n.
Ký hiệu thời gian : T(n), trong đó n là cỡ của dữ liệu vào.!
CTDL – Khoa CNTH – Viện ĐH Mở HN
27
c. Ký hiệu O:
!
!
"
!
int sum (int n)
{
int sum, i ;
sum = 0;
i = 1;
Giả sử T(n) và g(n) là các hàm của đối số ngun n.
Ta nói T(n) là ơ lớn của g(n) và viết là: T(n) = O(g(n))
nếu tồn tại các hằng số dương c và n0 sao cho T(n) <= c.g(n)
với mọi n >= n0.
Giả sử f(n) = 5n3 + 2n2 + 13n + 6,
ta có:
f(n) = 5n3 + 2n2 + 13n + 6 <= 5n3 + 2n3 + 13n3 + 6n3 <= 26n3
f(n) = O(n3).
CTDL – Khoa CNTH – Viện ĐH Mở HN
28
VD: Xác định độ phức tạp thuật toán (O-lớn)
Để ước lượng độ phức tạp của một thuật toán ta thường
dùng khái niệm O - lớn
Định nghĩa:
"
CTDL – Khoa CNTH – Viện ĐH Mở HN
29
}
while (i < n)
{
sum = sum + i;
i = i+ 1;
}
return sum;
T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1""
<="5n"+"1n"
<="6n""
CTDL – Khoa CNTH – Viện ĐH Mở HN
No time
1 Unit
1 Unit
n Unit (n Comparison)
2 x (n-1) Unit
2 x (n-1) Unit
1 Unit
T"(n)"="O(n)"
30
VD: Xác định ký hiệu O –lớn của thuật toán
% Các câu lệnh thông thường
s1, s2,………, sk (i = 1; i = i*i )
int Sum (int n)
{
int sum ;
sum = 0;
}
*Một số trường hợp ký tự O-lớn đặc biệt
O(1)
No time
1 Unit
3n + 2 Unit
for ( int i =1 ; i<=n; i++)
{
sum = sum + i*i*i;
}
return sum;
for ( int i = 0; i
s1, s2,………, sk
}
4 *n Unit
1 Unit
T"(n)"="1"+"3n"+"2"+"4*n"+"1"="7n"+"4""
<="7n"+"4n"
<="11n""
% Vòng lặp đơn (for, while, do-while)
T"(n)"="O(n)"
O(n)
Câu lệnh s1, s2, … có dạng O(1)
CTDL – Khoa CNTH – Viện ĐH Mở HN
31
% Lưa chọn (if-else, switch)
CTDL – Khoa CNTH – Viện ĐH Mở HN
32
% Vòng lặp lồng nhau (for, while, do-while)
if ( condition )
{
s1, s2,………, sk
}
else
{
s1, s2,………, sk
}
for ( int i = 0; i
for ( int j = 0; j
s1, s2,………sk
}
}
O(1)
Câu lệnh s1, s2, … có dạng O(1)
O(n2)
Câu lệnh s1, s2, … có dạng O(1)
CTDL – Khoa CNTH – Viện ĐH Mở HN
33
CTDL – Khoa CNTH – Viện ĐH Mở HN
34
% Tổng hợp (tuần tự, for, while, do-while)
for( int k =0 ; k
s1, s2,………sk
}
O(n)
s1, s2, ………, sk
O(1)
for ( int i = 0; i
for ( int j = 0; j
s1, s2,………sk
}
}
Ký hiệu ô lớn
O(n2)
O(n2)
Câu lệnh s1, s2, … có dạng O(1)
CTDL – Khoa CNTH – Viện ĐH Mở HN
35
Tên gọi
O(1)
hằng
O(logn)
logarit
O(n)
tuyến tính
O(nlogn)
nlogn
O(n2)
bình phương
O(n3)
lập phương
O(2n)
mũ
CTDL – Khoa CNTH – Viện ĐH Mở HN
36
V. Biểu diễn thuật toán
* Sử dụng lưu đồ khối
! Là
công cụ rất trực quan để diễn đạt các thuật tốn
hệ thống các nút có hình dạng khác nhau, thể
hiện các chức năng khác nhau và được nối bởi các
cung
! Các thành phần của lưu đồ khối:
! Liệt
kê theo bước
! Sơ đồ khối – flow chart
! Mã giả - Pseudocode
" Dùng ngôn ngữ C để cài đặt thuật toán
CTDL – Khoa CNTH – Viện ĐH Mở HN
! Là
37
}
while (i < n)
{
sum = sum + i;
i = i+ 1;
}
return sum;
! Khái
niệm
toán
! Lời giải và giải thuật đệ quy
Begin
! Bài
Sum = 0;
i = 1;
i
38
VI. Giải thuật đệ quy (recursion)
VD: Xây dựng sơ đồ thuật toán sau
int sum (int n)
{
int sum, i ;
sum = 0;
i = 1;
CTDL – Khoa CNTH – Viện ĐH Mở HN
Sai
return sum;
Đúng
sum = sum + i
End
i=i+1
CTDL – Khoa CNTH – Viện ĐH Mở HN
39
CTDL – Khoa CNTH – Viện ĐH Mở HN
40
1. Giải thuật đệ quy
! Định
! Giải
thuật đệ quy là lời giải một bài toán P
được thực hiện bằng lời giải của bài toán P
khác có dạng giống như P, P phải nhỏ
hơn P
! Ví dụ:
nghĩa một giải thuật đệ quy:
" phần
neo (anchor)
! Chỉ
ra lời giải đơn giản của bài tốn $ trường hợp đơn giản
! Có thể giải trực tiếp chứ không cần phải nhờ đến một bài toán
con nào khác
" phần
đệ quy
! xác
định những bài toán con đã có và bài tốn cần giải thực hiện gọi
đệ quy giải những bài tốn con đó,
! để giải bài tốn thì phối hợp các các bài tốn con đã có lời giải lại
với nhau theo nguyên tắc xác định
" Tính
giai thừa
" Tính tổng các số nhỏ hơn hoặc bằng n
# Ví
dụ: Tính giai thừa
tử neo: n = 1
& Phần đệ quy: Giai thừa (n) = n * Giai thừa (n-1)
& Phần
CTDL – Khoa CNTH – Viện ĐH Mở HN
41
CTDL – Khoa CNTH – Viện ĐH Mở HN
42
3. Kỹ thuật tìm giải thuật đệ quy
2. Phân loại hàm đệ quy
# Đệ quy tuyến tính Trong thân hàm gọi 1 lần chính nó
# Đệ quy nhị phân
Thân hàm gọi 2 lần chính nó
# Đệ quy phi tuyến
Thân hàm lặp gọi nhiều lần chính nó
# Đệ quy tương hỗ
Hai hàm đệ quy gọi nhau
long Tong
( int
long
G( nint) n );
{ Fibonaci
int long
Giaithua
( int
(nint
)U (nint
) n)
long G( int n )
long
if (n<6) return n;
{ {
{ if (n<8) return n-3;
{
long
S =1;
0;
ifif(n<=2)
(n==1)
return
return
1;
for
(
int
i
=
5;
i
>
0;
i-)
if (n<5) return
else
return
return
n *Fibonaci(
Giaithua
n( n-1
– 2n;);
) + Fibonaci(
n –U(n-1)
1 ); + G(n-2);
return
S = S + Tong( n-i );
} }
return U(n-1) + G(n-2); }
return S;
}
}
CTDL – Khoa CNTH – Viện ĐH Mở HN
#
Thơng số hóa bài tốn
#
Tìm các điều kiện biên (điều kiện chặn)
&
Lời giải với giá trị cụ thể
&
Tìm giải thuật cho các tình huống này
#
Tìm giải thuật tổng quát theo hướng đệ quy lui dần về tình
huống bị chặn
#
Thực hiện cài đặt
&
43
Viết chương trình theo đúng thứ tự công thức đệ quy
CTDL – Khoa CNTH – Viện ĐH Mở HN
44
VD: TÍNH TỔNG N PHẦN TỬ CỦA MẢNG A
Thơng số hóa: int a[ ], int
Ví dụ: Thực hiện giải bài tốn tính tổng các
số ngun nhỏ hơn hoặc bằng n bằng đệ quy
(n là số nguyên dương)
n
Điều kiện biên: Mảng 0 phần tử thì tổng bằng 0.
Giải thuật tổng quát
Sum (a, n) = a[0] + a[1] + a[2] + ... + a[n-2] + a[n-1]
Sum(a, n-1)
Sum (a, n) = 0
nếu n=0
a[n-1] + Sum (a, n-1) với n>=1
CTDL – Khoa CNTH – Viện ĐH Mở HN
45
CTDL – Khoa CNTH – Viện ĐH Mở HN
46
VD: TÍNH TỔNG N PHẦN TỬ CỦA MẢNG A (tiếp)
VD2: Tìm trị lớn nhất của mảng a gồm n phần tử
Cài đặt thuật toán
! Điều
kiện biên: Mảng 1 phần tử thì trị lớn nhất là a[0].
thuật chung:
Max(a,n) = a[0] , a[1] , a[2] , ... , a[n-2] , a[n-1]
Max(a, n-1 )
Max (a,n) = a[0] ,
n=1
a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1)
! Giải
int Sum ( int a[ ], int n)
{
if ( n == 0 ) return 0;
else return ( a[n-1] + Sum (a, n-1) );
}
Sv tự viết
CTDL – Khoa CNTH – Viện ĐH Mở HN
47
CTDL – Khoa CNTH – Viện ĐH Mở HN
48
BÀI TẬP VỀ NHÀ
Cài đặt đệ quy tìm phần tử lớn nhất trong mảng
float Max ( float a[ ], int n )
{
if (n==1) return a[0];
else return ((a[n-1] > Max(a, n-1))? a[n-1] : Max(a,n-1));
}
CTDL – Khoa CNTH – Viện ĐH Mở HN
! Giải
bài tốn tìm phần tử lớn nhất của mảng
a gồm n số nguyên bằng đệ quy
! Yêu cầu:
" Viết
bằng tay đầy đủ các bước để giải
" Đầu giờ sau nộp lại cho GV
49
Tóm lược bài học
CTDL – Khoa CNTH – Viện ĐH Mở HN
50
Bài tập về nhà
! Làm
theo nhóm
bày đầy đủ - chi tiết các bước để giải quyết bài toán
! Bài toán: cho thơng tin của hàng hóa gồm: mã hàng hóa,
tên hàng hóa, số lượng và đơn giá. Viết chương trình
quản lý hàng hóa với các u cầu:
! Trình
Các khái niệm CTDL và thuật toán
Đánh giá độ phức tạp thuật toán
Nhập vào một danh sách hàng hóa
In lại danh sách hàng hóa
" In danh sách hàng hóa có đơn giá trên 50000
" Tính tổng tiền của tất cả các hàng hóa
" Đếm số hàng hóa có số lượng dưới 20
"
"
Biểu diễn thuật toán
Các bước thiết kế thuật toán
! Yêu
Giải thuật đệ quy
CTDL – Khoa CNTH – Viện ĐH Mở HN
cầu:
Cài đặt code
" Làm báo cáo chi tiết các bước để giải bài toán (viết tay hoặc đánh
máy)
"
51
Bài tập viết hàm đệ quy
CTDL – Khoa CNTH – Viện ĐH Mở HN
52
5. Nhận xét về hàm đệ quy
! Tính
tổng các số nguyên nhỏ hơn hoặc bằng n
tổng các phần tử của mảng a gồm n số
nguyên
! Tính
! BTVN:
HÀM ĐỆ QUY: Vừa tốn bộ nhớ
vừa chạy chậm vì gọi hàm nhiều
Bài tập viết hàm đệ quy
Giải thuật đệ quy đẹp (gọn gàng), dễ chuyển
thành chương trình.
" Tính
số Fibonaci thứ n
" Tìm phần tử lớn nhất của mảng a gồm n phần tử
Nhiều ngôn ngữ không hỗ trợ giải thuật đệ quy
(Fortran).
Nhiều giải thuật rất dễ mô tả dạng đệ quy nhưng
lại rất khó mơ tả với giải thuật khơng-đệ-quy.
CTDL – Khoa CNTH – Viện ĐH Mở HN
54
CTDL – Khoa CNTH – Viện ĐH Mở HN
68
7. Khử đệ quy
!
!
!
*Khử đệ quy bằng vòng lặp
Là quá trình chuyển đổi 1 giải thuật đệ quy thành
giải thuật khơng đệ quy.
Chưa có giải pháp cho việc chuyển đổi này một
cách tổng quát.
Cách tiếp cận:
" Dùng quan điểm đệ quy để tìm giải thuật cho bài
tốn.
" Mã hóa giải thuật đệ quy.
" Khử đệ quy để có giải thuật khơng-đệ-quy.
CTDL – Khoa CNTH – Viện ĐH Mở HN
! Ý
tưởng: Lưu lại các trị của các lần tính tốn
trước làm dữ liệu cho việc tính tốn của lần sau.
! Đi từ điều kiện biên đi tới điều kiện kết thúc.
69
Thí dụ: Hàm tính giai thừa của n
long GiaiThua( int n)
{ if (n<2) return 1;
return n * GiaiThua(n-1);
}
long GiaiThua( int n)
{ long K=1;
for (int i =2; i<=n;i++)
K=K*i;
return K;
}
long Fibo(int n)
{
if (n<=2) return 1; // hai chặn
return Fibo(n-2) + Fibo (n-1);
}
long Fibo(int n)
{
if (n<=2) return 1; // hai chặn
long t1=1, t2=1;
for (int i=3; i<=n;i++)
{ t3=t1+t2;
t1=t2;
t2= t3;
}
return t3;
}
Điều kiện biên
K chính là kết qủa của
trị giai thừa trước đó
71
BTVN
! Làm
bài tập về nhà số 01, viết ra giấy, đầu
giờ buổi sau thu
! Đọc và nghiên cứu trước giáo trình phần:
" Thuật
tốn tìm kiếm (tuyến tính và nhị phân)
tốn sắp xếp (selection, insertion )
" Mỗi thuật toán xác định:
" Thuật
! Ý
tưởng
bước thực hiện
! Đánh giá độ phức tạp thuật tốn
! Lấy ví dụ minh họa
! Các
CTDL – Khoa CNTH – Viện ĐH Mở HN
70
Thí dụ hàm tính trị thứ n của dãy Fibonacci:
Trị cần lưu
CTDL – Khoa CNTH – Viện ĐH Mở HN
CTDL – Khoa CNTH – Viện ĐH Mở HN
77
CTDL – Khoa CNTH – Viện ĐH Mở HN
1 1 2 3 5 8...
t
1
i =
t
2
t1
t3=t1+t2
t2
t3
t1
t2
t3
t1
t2
4
5
3
t3
6
72
