! Hình thức thi: BTL

" Nhóm 4 SV

! Cách tính điểm:

CẤU TRÚC DỮ LIỆU Khoa Công nghệ thông tin Email: trinhxuan@gmail.com Thời lượng: 60 tiết – LT Web: //sites.google.com/site/trinhxuan

" Đ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

Mục đích môn học

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 1(cid:1) 2(cid:1)

*Tài liệu học tập:

# Hiểu được khái niệm CTDL và Thuật toán

! Giáo trình bắt buộc

# Biết cách đánh giá độ phức tạp của một thuật toán

" Giáo trình Cấu trúc dữ liệu – Khoa CNTT,

Viện ĐH Mở HN – Lưu hành nội bộ

# Nắm đượ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:

! Giáo trình tham khảo

Hàng đợi, Ngăn xếp, Cây, Đồ thị

" Đỗ Xuân Lôi, “Cấu trúc dữ liệu và giải

# Hiểu và áp dụng được một số thuật toán cơ bản:

thuật”, NXB Khoa học và kỹ thuật.

Tìm kiếm, Sắp xếp, …

" Introduction to Algorithms – The cormen

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 3(cid:1) 4(cid:1)

*Nội dung môn học

STT

NỘI DUNG GIẢNG DẠY

Ghi chú

SỐ TIẾT

Y/C Đọc TL

1

5

Đánh giá Thuật Toán - Phân công BTL

2

5

x

TK và SX

3

5

x

TK và SX

4

5

x

Thực hành mảng - Test

5

5

x

DSLK Đơn

6

5

x

Thực hành DSLK Đơn - Test

7

5

x

Danh sách liên kết đôi

Các buổi Thực hành có thể mang máy tính cá nhân đi thực hành

8

5

x

Stack - Queue

9

5

x

Cây

10

5

x

Cây - Test

11

5

x

Đồ thị

12

5

x

Test BTL – Đánh giá sơ bộ - TH

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 5(cid:1) 6(cid:1)

Lưu ý sử dụng Phòng máy

Yêu cầu kiến thức cần có

!  Xem và tổng hợp lại ngôn ngữ C !  Nội dung cần tổng hợp lại:

! 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í tính trên 1 sinh viên: 10.000đ/3 buổi

! Lớp trưởng thu giúp

! Cách thức thực hiện:

" Buổi 1: Thu thập nguyên vọng sử dụng điều hòa " Buổi 2+3: Thu tiền sử dụng điều hòa

! Nguyên tắc số ít theo số nhiều

"  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 "  …

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 7(cid:1) 8(cid:1)

I. Giới thiệu

! Các bước để xây dựng bài toán tin học trong máy tính

Lập trình

Thiết kế

#include …

Bài toán thực tế Yêu cầu

CHƯƠNG I: CÁC KHÁI NIỆM CƠ BẢN

Chương trình

Giải thuật Thuật toán

• Ngôn ngữ lập trình: • PASCAL, • C/C++, • JAVA, • Visual Basic •  …

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

1. Xác định bài toán

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 9(cid:1) 10(cid:1)

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 toán $ các thao

Tìm CTDL biểu diễn bài toán

tác cần thực hiện

Tìm thuật toán

Lập trình

#  Các bài toá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í.

Kiểm thử

Tối ưu chương trình

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 11(cid:1) 12(cid:1)

2. Tìm CTDL biểu diễn bài toán

3. Tìm thuật toán

%  Xác định hệ thống chặt chẽ và rõ ràng các quy tắc để

%  Xác định input và output của bài toán

từ Input có được Output

%  Input: dữ liệu đầu vào %  Output: Kết quả mong muốn đạt được

%  Xác định dãy thao tác trên CTDL đầu vào để giải

quyết yêu cầu bài toá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

Đảm bảo

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

#  Mỗi bước thao tác rõ ràng #  Không được rơi vào quá 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

4. Lập trình

5. Kiểm thử

#  Xác định ngôn ngữ lập trình được sử dụng

#  Kiểm tra lỗi chương trình #  Lỗi cơ bản

#  Thông thường ta không nên cụ thể hóa ngay toàn bộ

&  Lỗi cú pháp &  Lỗi cài đặt &  Lỗi thuật toán

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

#  Nguyên tắc xây dựng bộ test

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 đã

&  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 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

&  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

nhỏ hơn để lại tiếp tục với những công việc nhỏ hơn đó.

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 13(cid:1) 14(cid:1)

6. Tối ưu chương trình

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 15(cid:1) 16(cid:1)

III. CTDL và Thuật toán

! Xây dựng một bài toán cần: " Xác định Cấu trúc dữ liệu

! Đối tượng dữ liệu dùng trong bài toán $ Tổ chức biểu

#  Đặ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

diễn được đối tượng " Xác định Thuật toán

! Các yêu cầu xử lý trên đối tượng đó $ Xác định và

#  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 soát.

xây dựng thao tác xử lý trên đối tượng

CTDL + Thuật toán = Chương trình Structure Data + Algorithm = Program

#  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 CTDL – Khoa CNTH – Viện ĐH Mở HN 17(cid:1) 18(cid:1)

a. Cấu trúc dữ liệu – Structure Data

!  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 toán tử (thao tác) thực hiện trên kiểu dữ liệu đó

! 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 toá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 tiêu chuẩn đánh giá một CTDL:

! Các kiểu cấu trúc dữ liệu cơ bản:

"  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:

" Mảng, Bản ghi " Danh sách liên kết, Ngăn xếp, Hàng đợi " Cây " Đồ thị

"  Thực hiện nhiều phép toán, "  Sử dụng càng ít tài nguyên, "  Thời gian xử lý và không gian bộ nhớ tốt

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 19(cid:1) 20(cid:1)

b. Thuật toán - Algorithm:

* Tính chất của thuật toán

! Thuật toá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)

! Tính 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

Thuật toán

Output

Input

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 21(cid:1) 22(cid:1)

a. Độ phức tạp không gian:

IV. Đánh giá độ phức tạp thuật toán

! Các tiêu chí lựa chọn thuật toán:

! 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. 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 toán cần ít bộ nhớ "  4. Thuật toán chạy nhanh

! => để đánh giá thuật toán dựa vào độ phức tạp

! Chi phí bộ nhớ gồm:

thuật toán

! Độ phức tạp thuật toán được thể hiện qua:

" Lưu dữ liệu vào - input " Lưu dữ liệu ra - output " Lưu các kết quả trung gian - temp

"  Không gian "  Thời gian

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 23(cid:1) 24(cid:1)

VD: Xác định độ phức tạp thuật toán

b. Độ phức tạp thời gian:

!  là tổng thời gian cần thiết để hoàn thành thuật toán !  Được đá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

No time 1 Unit 1 Unit

!  Các thao tác được xem xét:

n Unit (n Comparison)

2 x (n-1) Unit

2 x (n-1) Unit

1 Unit

int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; }

"  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"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1""

tạp tính toán (độ phức tạp thời gian)

*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

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 25(cid:1) 26(cid:1)

5"

39"

5 3 10 13 6 9 15 21 12 8 61 39

Best Case

Worst Case

Average Case

int Sum (int n) { int sum ; sum =0; for ( int i =0 ; i

%  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 toá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 toá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.!

VD: Xác định độ phức tạp thuật toán (O-lớn)

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 27(cid:1) 28(cid:1)

c. Ký hiệu O:

!  Để ướ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:

No time 1 Unit 1 Unit

n Unit (n Comparison)

2 x (n-1) Unit

2 x (n-1) Unit

"  Giả sử T(n) và g(n) là các hàm của đối số nguyên n. "  Ta nói (cid:2)T(n) là ô lớn của g(n) (cid:1)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.

1 Unit

int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; }

!  Giả sử f(n) = 5n3 + 2n2 + 13n + 6, ta có:

T"(n)"="1+1+n+2*(n+1)+2*(n+1)+1"="5n"+"1""

T"(n)"="O(n)"

<="5n"+"1n" <="6n""

f(n) = 5n3 + 2n2 + 13n + 6 <= 5n3 + 2n3 + 13n3 + 6n3 <= 26n3 f(n) = O(n3).

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 29(cid:1) 30(cid:1)

*Một số trường hợp ký tự O-lớn đặc biệt

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 )

O(1)

No time 1 Unit

%  Vòng lặp đơn (for, while, do-while)

3n + 2 Unit

4 *n Unit

O(n)

1 Unit

int Sum (int n) { int sum ; sum = 0; for ( int i =1 ; i<=n; i++) { sum = sum + i*i*i; } return sum; }

for ( int i = 0; i

T"(n)"="O(n)"

Câu lệnh s1, s2, … có dạng O(1)

T"(n)"="1"+"3n"+"2"+"4*n"+"1"="7n"+"4"" <="7n"+"4n" <="11n""

%  Lưa chọn (if-else, switch) if ( condition ) {

%  Vòng lặp lồng nhau (for, while, do-while) for ( int i = 0; i

s1, s2,………, sk

for ( int j = 0; j

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 31(cid:1) 32(cid:1)

O(1)

O(n2)

} else {

}

s1, s2,………, sk

{ s1, s2,………sk }

} Câu lệnh s1, s2, … có dạng O(1)

Câu lệnh s1, s2, … có dạng O(1)

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 33(cid:1) 34(cid:1)

Ký hiệu ô lớn

Tên gọi

O(n)

O(1)

hằng

%  Tổng hợp (tuần tự, for, while, do-while) for( int k =0 ; k

O(logn)

logarit

s1, s2, ………, sk

O(1)

O(n)

tuyến tính

O(n2)

O(nlogn)

nlogn

for ( int i = 0; i

for ( int j = 0; j

O(n2)

bình phương

O(n3)

lập phương

O(n2)

}

O(2n)

mũ

{ s1, s2,………sk } Câu lệnh s1, s2, … có dạng O(1)

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 35(cid:1) 36(cid:1)

V. Biểu diễn thuật toán

* Sử dụng lưu đồ khối

! Liệt kê theo bước ! Sơ đồ khối – flow chart ! Mã giả - Pseudocode

! Là công cụ rất trực quan để diễn đạt các thuật toán ! Là 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

" Dùng ngôn ngữ C để cài đặt thuật toán

! Các thành phần của lưu đồ khối:

VD: Xây dựng sơ đồ thuật toán sau

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 37(cid:1) 38(cid:1)

VI. Giải thuật đệ quy (recursion)

Begin

! Khái niệm ! Bài toán ! Lời giải và giải thuật đệ quy

Sum = 0; i = 1;

Sai

i < n

return sum;

Đúng

sum = sum + i

End

int sum (int n) { int sum, i ; sum = 0; i = 1; while (i < n) { sum = sum + i; i = i+ 1; } return sum; }

i = i + 1

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 39(cid:1) 40(cid:1)

1. Giải thuật đệ quy

! Định 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 toá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

! 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(cid:2) khác có dạng giống như P, P(cid:2) phải (cid:3)nhỏ(cid:4) hơn P ! Ví dụ:

" Tính giai thừa " Tính tổng các số nhỏ hơn hoặc bằng n

! xác định những bài toán con đã có và bài toán cần giải thực hiện gọi đệ quy giải những bài toán con đó, ! để giải bài toán thì phối hợp các các bài toán con đã có lời giải lại với nhau theo nguyên tắc xác định

# Ví dụ: Tính giai thừa & Phần tử neo: n = 1 & Phần đệ quy: Giai thừa (n) = n * Giai thừa (n-1)

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 41(cid:1) 42(cid:1)

3. Kỹ thuật tìm giải thuật đệ quy

2. Phân loại hàm đệ quy

#  Thông số hóa bài toán

# Đệ quy tuyến tính Trong thân hàm gọi 1 lần chính nó

#  Tìm các điều kiện biên (điều kiện chặn)

# Đệ quy nhị phân

Thân hàm gọi 2 lần chính nó

&  Lời giải với giá trị cụ thể

# Đệ quy phi tuyến Thân hàm lặp gọi nhiều lần chính nó

&  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

# Đệ quy tương hỗ Hai hàm đệ quy gọi nhau

huống bị chặn

long G( int n );

#  Thực hiện cài đặt

long G( int n )

int Giaithua ( int n ) {

&  Viết chương trình theo đúng thứ tự công thức đệ quy

{ if (n<8) return n-3;

{

return U(n-1) + G(n-2);

S = S + Tong( n-i );

long Tong ( int n ) { long Fibonaci ( int n ) long U ( int n) if (n<6) return n; { long S = 0; if (n==1) return 1; if (n<=2) return 1; for ( int i = 5; i > 0; i-- ) else return Fibonaci( n – 2 ) + Fibonaci( n – 1 ); return n * Giaithua ( n-1 ); if (n<5) return n; }

}

return U(n-1) + G(n-2);

}

return S;

}

}

VD: TÍNH TỔNG N PHẦN TỬ CỦA MẢNG A

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 43(cid:1) 44(cid:1)

Thông số hóa: int a[ ], int n

Điều kiện biên: Mảng 0 phần tử thì tổng bằng 0.

Ví dụ: Thực hiện giải bài toán tính tổng các số nguyên nhỏ hơn hoặc bằng n bằng đệ quy (n là số nguyên dương)

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

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ử

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 45(cid:1) 46(cid:1)

Cài đặt thuật toán

int Sum ( int a[ ], int n) {

n=1

if ( n == 0 ) return 0; else return ( a[n-1] + Sum (a, n-1) );

!  Điều kiện biên: Mảng 1 phần tử thì trị lớn nhất là a[0]. !  Giải 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] , a[n-1] > Max(a, n-1)? a[n-1] : Max(a,n-1)

}

Sv tự viết

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 47(cid:1) 48(cid:1)

Cài đặt đệ quy tìm phần tử lớn nhất trong mảng

BÀI TẬP VỀ NHÀ

! Giải bài toán tìm phần tử lớn nhất của mảng

float Max ( float a[ ], int n ) {

a gồm n số nguyên bằng đệ quy

! Yêu cầu:

if (n==1) return a[0]; else return ((a[n-1] > Max(a, n-1))? a[n-1] : Max(a,n-1));

}

" Viết bằng tay đầy đủ các bước để giải " Đầu giờ sau nộp lại cho GV

Tóm lược bài học

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 49(cid:1) 50(cid:1)

Bài tập về nhà

Các khái niệm CTDL và thuật toán

Đánh giá độ phức tạp thuật toán

Biểu diễn thuật toán

!  Làm theo nhóm !  Trình 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 yêu cầu: "  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

Các bước thiết kế thuật toán

!  Yêu cầu:

Giải thuật đệ quy

"  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)

Bài tập viết hàm đệ quy

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 51(cid:1) 52(cid:1)

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ính tổng các phần tử của mảng a gồm n số

nguyên

HÀM ĐỆ QUY: Vừa tốn bộ nhớ vừa chạy chậm vì gọi hàm nhiều

! BTVN: 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 CTDL – Khoa CNTH – Viện ĐH Mở HN 54(cid:1) 68(cid:1)

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.

! Ý tưởng: Lưu lại các trị của các lần tính toán trước làm dữ liệu cho việc tính toán của lần sau.

!  Chưa có giải pháp cho việc chuyển đổi này một

! Đi từ điều kiện biên đi tới điều kiện kết thúc.

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

toán.

" Mã hóa giải thuật đệ quy. " Khử đệ quy để có giải thuật không-đệ-quy.

Thí dụ: Hàm tính giai thừa của n

Thí dụ hàm tính trị thứ n của dãy Fibonacci: 1 1 2 3 5 8...

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 69(cid:1) 70(cid:1)

Trị cần lưu

t3=t1+t2

t 1

long Fibo(int n) { if (n<=2) return 1; // hai chặn return Fibo(n-2) + Fibo (n-1); }

t 2 t1

t2

t3

long GiaiThua( int n) { if (n<2) return 1; return n * GiaiThua(n-1); }

Điều kiện biên

t1

t2

t3

t1

t2

t3

i = 3 4 5 6

long GiaiThua( int n) { long K=1; for (int i =2; i<=n;i++)

K chính là kết qủa của trị giai thừa trước đó

K=K*i; return K; }

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; }

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 toán tìm kiếm (tuyến tính và nhị phân) " Thuật toán sắp xếp (selection, insertion ) " Mỗi thuật toán xác định:

! Ý tưởng ! Các bước thực hiện ! Đánh giá độ phức tạp thuật toán ! Lấy ví dụ minh họa

CTDL – Khoa CNTH – Viện ĐH Mở HN CTDL – Khoa CNTH – Viện ĐH Mở HN 71(cid:1) 72(cid:1)

CTDL – Khoa CNTH – Viện ĐH Mở HN 77(cid:1)