Xem mẫu
- BỘ LAO ĐỘNG - THƯƠNG BINH VÀ XÃ HỘI
TỔNG CỤC DẠY NGHỀ
DỰ ÁN GIÁO DỤC KỸ THUẬT VÀ DẠY NGHỀ (VTEP)
GIÁO TRÌNH
Môn học : PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
Mã số : ITPRG3_12
Nghề : LẬP TRÌNH MÁY TÍNH
Trình độ (lành nghề)
Đà Lạt - 2007
- Phân tích thiết kế thuật toán
Tuyên bố bản quyền :
Tài liệu này thuộc loại sách giáo trình
Cho nên các nguồn thông tin có thể được
phép dùng nguyên bản hoặc trích dùng
cho các mục đích về đào tạo và tham khảo .
Mọi mục đích khác có ý đồ lệch lạc hoặc
sử dụng với mục đích kinh doanh thiếu
lành
mạnh sẽ bị nghiêm cấm.
Tổng Cục Dạy nghề sẽ làm mọi cách để
bảo vệ bản quyền của mình.
Tổng Cục Dạy Nghề cám ơn và hoan
nghênh các thông tin giúp cho việc tu sửa
và hoàn thiện tốt hơn tàI liệu này.
Địa chỉ liên hệ:
Dự án giáo dục kỹ thuật và nghề nghiệp
Tiểu Ban Phát triển Chương trình Học
liệu
………………………………………………
................................................................
2
- Phân tích thiết kế thuật toán
LỜI TỰA
Đây là tài liệu được xây dựng theo chương trình của dự án giáo dục kỹ thuật và dạy nghề, để
có đươc giáo trình này dự án đã tiến hành theo hai giai đoạn.
Giai đoạn 1 : Xây dựng chương trình theo phương pháp DACUM, kết quả của gian đoạn
này là bộ khung chương trình gồm 230 trang cấp độ 2 và 170 trang cấp độ 3.
Giai đoạn 2 : 29 giáo trình và 29 tài liệu hướng dẫn giáo viên cho nghề lập trình máy tính 2
cấp độ.
Để có được khung chương trình chúng tôi đã mời các giáo viên, các chuyên gia đang làm
việc trong lĩnh vực công nghệ thông tin cùng xây dựng chương trình.
Trong giai đoạn viết giáo trình chúng tôi cũng đã có những sự điều chỉnh để giáo trình có
tính thiết thực và phù hợp hơn với sự phát triển của lĩnh vực công nghệ thông tin.
Trong quá trình biên soạn, mặc dù đã cố gắng tham khảo nhiều tài liệu và giáo trình khác
nhưng tác giả không khỏi tránh được những thiếu sót và hạn chế. Tác giả chân thành mong đợi
những nhận xét, đánh giá và góp ý để cuốn giáo trình ngày một hoàn thiện hơn.
Tài liệu này được thiết kế theo từng mô đun/ môn học thuộc hệ thống mô đun/môn học
của một chương trình, để đào tạo hoàn chỉnh nghề Lập trình máy tính ở cấp trình độ lành nghề và
được dùng làm Giáo trình cho học viên trong các khoá đào tạo, cũng có thể được sử dụng cho
đào tạo ngắn hạn hoặc cho các công nhân kỹ thuật, các nhà quản lý và người sử dụng nhân lực
tham khảo.
Đây là tài liệu thử nghiệm sẽ được hoàn chỉnh để trở thành giáo trình chính thức trong hệ
thống dạy nghề.
Đà lạt ,Tháng 10 năm 2007
3
- Phân tích thiết kế thuật toán
MỤC LỤC
TÊN BÀI TRANG
1. BàI1 :TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN 5
2. Bài2 :CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG 20
3. Bài3 :CÁC CẤU TRÚC DỮ LIỆU CƠ BẢN 51
4. Bài4 :PHƯƠNG PHÁP CHIA ĐỂ TRỊ 109
5. Bài5 :PHƯƠNG PHÁP THAM LAM 116
6. Bài6 :PHƯƠNG PHÁP QUAY LUI 124
7. Bài7 :QUY HOẠCH ĐỘNG 135
8. Bài7(tiếp theo) :NÉN DỮ LIỆU 145
9. Bài 8 :LỚP BÀI TOÁN NP ĐẦY ĐỦ 159
10.CÁC BÀI THỰC HÀNH 172
11. TÀI LIỆU THAM KHẢO 185
4
- Phân tích thiết kế thuật toán
BÀI 1 : TỔNG QUAN VỀ PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
Mã bài : ITPRG3_12.1
Giới thiệu
Phân tích thiết kế thuật toán là một khâu quan trọng quyết định sự thành công của một chương
trình máy tính. Nó giúp chúng ta lựa chọn, xây dựng và đánh giá các thuật toán trước khi viết mã
chương trình. Chúng ta chỉ có thể có được một chương trình máy tính tốt nếu và chỉ nếu có một
thuật toán tốt. Phân tích thiết kế thuật toán còn có một ý nghĩa vô cùng quan trọng trong trường
hợp làm việc theo nhóm (cho phép chia sẻ công việc và đảm bảo sự thống nhất giữa các lập trình
viên) và bảo trì, nâng cấp hệ thống chương trình sau này.
Trong phần này chúng ta sẽ làm quen với các khái niệm cơ bản về phân tích thiết kế thuật
toán, các phương pháp biểu diễn và đánh giá thời gian thực hiện thuật toán.
Mục tiêu thực hiện
Học xong bài này học viên sẽ có khả năng:
Nắm được các khái niệm cơ bản và tầm quan trọng của việc phân tích và thiết kế thuật
toán trong việc xây dựng chương trình máy tính.
Sử dụng các phương pháp sử dụng sơ đồ khối và ngôn ngữ giả trong việc đặc tả dữ liệu
và thuật toán trong thiết kế chương trình.
Đánh giá độ phức tạp của thuật toán, so sánh độ phức tạp của thuật toán ứng với từng lời
giải của bài toán.
.1. Thuật toán (Algorithm)
.1.1 Định nghĩa
Thuật toán (hay còn gọi là giải thuật) là khái niệm cơ bản trong máy tính và lập trình máy tính.
Có thể hiểu thuật toán là phương pháp giải một bài toán bằng cách chia nhỏ bài toán thành
những thao tác đơn giản, dễ thực hiện và có trình tự hợp lý. Người ta đã đưa ra những định nghĩa
về thuật toán như sau :
5
- Phân tích thiết kế thuật toán
"Thuật toán là tập hợp đặc trưng các trình tự logic và toán học đơn giản, được xác định rõ ràng
để theo đó giải quyết một vấn đề với một số bước nhất định ". (L. Nyhof & S. Leestma)
Một định nghĩa khác :
"Thuật toán là một hệ thống chặt chẽ và rõ ràng với các qui tắc nhằm xác định một dãy các
thao tác trên những đối tượng sao cho sau một số hữu hạn bước thực hiện các thao tác ta đạt
được mục tiêu định trước". (B.W. Kernighan)
.1.2 Các đặc trưng cần phải có của thuật toán
Khi xây dựng một thuật toán máy tính phải đáp ứng các yêu cầu sau :
Thuật toán phải kết thúc sau một số bước hữu hạn - tính kết thúc
Mỗi thao tác thực hiện phải rõ ràng, cụ thể và duy nhất - tính xác định.
Các thao tác phải khả thi (có thể thực hiện được) - tính hiệu quả.
Có thể giải bất kỳ bài toán nào trong một lớp các bài toán - tính phổ dụng.
Miền xác định của thuật toán: là tập hợp bộ dữ liệu mà thuật toán có thể sử dụng và cho ra kết quả - Đại lượng
vào/ra.
Lưu ý rằng việc giải quyết một bài toán có thể tồn tại nhiều thuật toán khác nhau. Mỗi thuật
toán có thể có hiệu quả như nhau cho một lớp các bài toán.
6
- Phân tích thiết kế thuật toán
.1.3 Công cụ trình bày thuật toán
Quá trình xử lý
Chương trình con
Bắt đầu / Kết thúc
Điều kiện rẽ nhánh
Nhập xuất dữ liệu
Điều kiện lựa chọn
Đĩa từ
Các hướng xử lý
Có hai công cụ phổ biến để trình bày thuật toán: bằng sơ đồ khối (Flowchart) và ngôn ngữ giả
(pseudo language).
Sơ đồ khối là sơ đồ biểu diễn các hình ký hiệu đặc trưng cho các thao tác cần thực hiện.
Ngôn ngữ giả là ngôn ngữ tự nhiên kết hợp với một ngôn ngữ lập trình được chọn để viết chương trình. Đây là
công cụ thường được sử dụng để trình bày thuật toán.
Trong sơ đồ thuật toán, các hình được nối, liên kết với nhau bởi các mũi tên chỉ ra trình tự thực
hiện các thao tác.
Các khối cơ bản
Các cấu trúc cơ bản
Sơ đồ thuật toán
7
Cấu trúc tuần tự Cấu trúc điều kiện Cấu trúc vòng lặp
- Phân tích thiết kế thuật toán
Sơ đồ thuật toán của bất kỳ bài toán nào cũng có thể được xây dựng trên cơ sở các phần tử
và các cấu trúc trên. Về cơ bản, các sơ đồ được tạo lập từ các khối sau:
1. Khối thao tác
Là khối hình chữ nhật trong đó ghi các lệnh cần thực hiện
a := a + b a:=5
i= i + 1
2. Khối điều kiện
Là khối hình thoi hoặc elip bên trong ghi các điều kiện cần kiểm tra
.T. .T.
a=1 i
- Phân tích thiết kế thuật toán
Ta có thể biểu diễn như sau
Ví dụ : Dùng sơ đồ khối để biểu diễn thuật toán giải bài toán tìm nghiệm của phương trình bậc
1 : ax + b = 0.
Begin
a, b
Đ x :=-b/a
a0 Nghiệm x
S
Đ PT vô nghiệm
b0
S
Vô số nghiệm
End
Ưu điểm của cách biểu diễn thuật toán bằng sơ đồ khối là rõ ràng, trực quan giúp người đọc
dễ hình dung các bước lưu chuyển trong thuật toán. Tuy nhiên, với những bài toán lớn chứa rất
nhều bước và phức tạp thì rất khó biểu diễn bằng phương pháp này.
Ví dụ: Cho một ngã 5 như hình vẽ
9
- Phân tích thiết kế thuật toán
Giải: Chúng ta có thể mô hình hóa bài toán nói trên theo mô hình toán học đã biết đó là đồ thị
(Graph). Ðồ thị là tập hợp các điểm gọi là các đỉnh của đồ thị và một tập hợp các cạnh nối một số
các cặp đỉnh với nhau. Hai đỉnh có ít nhất một cạnh nối được gọi là hai đỉnh kề nhau. Tại ngả 5
này có 13 lối đi (AB, AC, AD, BA, BC, BD, DA, DB, DC, EA, EB, EC, ED). Ta sẽ biểu diễn mỗi lối
đi là một đỉnh của đồ thị và hai lối đi không thể cùng đi đồng thời ta nối chúng bằng một cạnh.
Tóm lại, ta có:
Ðỉnh là các tuyến đường đi cho phép.
Cạnh nối 2 đỉnh dùng để chỉ tuyến đường không thể lưu thông đồng thời.
Ta có đồ thị hình 2 như sau :
10
- Phân tích thiết kế thuật toán
Bài toán của chúng ta rõ ràng là bài toán tô màu cho đồ thị hình 2. Bài toán tô màu cho đồ thị
được phát biểu như sau: "Tô màu cho các đỉnh của đồ thị sao cho số màu được dùng là ít nhất và
2 đỉnh kề nhau (có cung nối) không được tô cùng 1 màu.
Tuy nhiên, bài toán tô màu cho đồ thị không có thuật toán tốt. Nói cách khác, thuật toán của bài
toán tô màu là : "Thử tất cả các khả năng". Thực tế cách giải này khó có thể áp dụng đưọc vì vậy
ta cần suy nghĩ cách khác để giải quyết vấn đề. Nếu bài toán nhỏ ta có thể vét cạn các khả năng
để tìm ra lời giải tối ưu.
Một cách giải quyết dùng cho bài toán chúng ta là: "Cố gắng tô màu cho đồ thị bằng ít màu
nhất" một cách nhanh chóng. Một cách giải quyết như vậy gọi là một Heuricstic. Một Heuricstic
hợp lý cho bài toán tô màu đồ thị được gọi là thuật toán Greedy.
Chọn 1 đỉnh chưa tô màu và tô màu cho nó. Với các đỉnh còn lại mà không có cạnh chung với đỉnh đang xét thì
tô các đỉnh đó cùng 1 màu với đỉnh đang xét.
Duyệt danh sách các đỉnh chưa tô màu, lấy 1 đỉnh trong số chúng và tô bằng màu mới rồi quay lại bước 1.
Ðây là thuật toán hiển nhiên và luôn đạt kết quả tốt (mặc dù có thể không là lời giải tối ưu).
Ví dụ : Xét đồ thị dưới đây và cách tô màu cho nó
Hình :Xét đồ thị và cách tô màu
Dùng Greedy: Tối ưu:
+Xanh : 1, 2 + Xanh: 1, 3, 4
+ Ðỏ : 3, 4 + Ðỏ : 2, 5
+ Tím : 5
Áp dụng thuật toán Greedy cho bài toán của đồ thị hình 2, ta được kết quả:
+ Xanh : AB, AC, AD, BA, DC, ED
+ Ðỏ : BC, BD, EA
+ Tím : DA, DB
11
- Phân tích thiết kế thuật toán
+ Vàng : EB, EC
Nhận xét:
Một đồ thị có k đỉnh mà mỗi cặp đỉnh bất kỳ đều được nối với nhau thì phải dùng k màu để tô.
Một đồ thị trong đó có k đỉnh mà mỗi cặp đỉnh bất kỳ trong k đỉnh này đều được nối với nhau thì không thể dùng
ít hơn k màu để tô cho đồ thị.
Ðồ thị hình 2 có 4 đỉnh AC, DA, EB, BD mà mỗi cặp đỉnh bất kỳ trong số chúng đều được nối với nhau. Vậy đồ
thị hình 2 không thể tô với ít hơn 4 màu. Ðiều này khẳng định lời giải trên là lời giải tối ưu.
.2. Ngôn ngữ giả và tinh chế từng bước
Một khi ta đã có mô hình thích hợp cho bài toán ta cần hình thức hóa một thuật toán trong
thuật ngữ của mô hình đó. Mở đầu ta viết những mệnh đề tổng quát rồi tinh chế dần thành những
mệnh đề cụ thể hơn và cứ tiếp tục như thế. Ðến cuối cùng ta được những chỉ thị thích hợp trong
một ngôn ngữ lập trình.
Ví dụ: Xét thuật toán Greedy áp dụng cho bài toán tô màu
Giả sử đồ thị đang xét là G. Thuật toán Greedy xác định một tập hợp NewClr các đỉnh của G
được tô cùng một màu.
Thuật toán Greedy được lập cho đến khi tất cả các đỉnh của G đều được tô màu.
Procedure Greedy (Var G : Graph ; Var NewClr : Set);
Begin
{1} NewClr : = 0 ;
{2} For mỗi đỉnh của V chưa tô màu Do
{3} If V không được nối với đỉnh nào trong NewClr Then
Begin
{4} Ðánh dấu V đã được tô màu ;
{5} Thêm V vào tập NewClr ;
End ;
End ;
Chú ý : Trong thuật toán bằng ngôn ngữ giả chúng ta đã dùng một số từ khóa của Pascal.
Graph và Set là các kiểu dữ liệu trừu tượng, chúng sẽ được xác định bằng phép định nghĩa
kiểu của Pascal.
Câu lệnh If {3} có thể được tinh chế một bước nữa như sau:
Procedure Greedy (Var G : Graph ; Var NewClr : Set);
12
- Phân tích thiết kế thuật toán
Begin
{1} NewClr : = 0 ;
{2} For mỗi đỉnh của V chưa tô màu Do
Begin
{3.1} Found : = False ;
{3.2} For mỗi đỉnh của W trong NewClr Do
{3.3} If có cạnh nối giữa V với W Then
{3.4} Found : = True ;
{3.5} If Found = False Then
Begin
{4} Ðánh dấu V đã được tô màu ;
{5} Thêm V vào tập NewClr ;
End;
End;
End ;
Ta có thể coi Graph và Set như các tập hợp. Có nhiều cách để biểu diễn 1 tập hợp trong ngôn
ngữ lập trình. Ðể đơn giản ta xem tập hợp như một danh sách (List) các số nguyên là chỉ số của
các đỉnh và kết thúc bằng 1 giá trị đặc biệt Null. Thuật toán Greedy được tinh chế 1 bước nữa
như sau:
Procedure Greedy (Var G:Graph ; Var NewClr: Set);
Var Found : Boolean ; V, W : Integer ;
Begin
NewClr : = 0 ;
V : = Ðỉnh đầu tiên trong G ;
While V Null Do
Begin
Found : = False ;
W : = Ðỉnh đầu tiên trong NewClr ;
While W Null Do
Begin
If có cạnh nối giữa V với W Then
Found : = True ;
W:=Ðỉnh kế tiếp trong NewClr ;
End;
If Found = False Then
Begin
Ðánh dấu V đã được tô màu ;
Thêm V vào tập NewClr ;
End;
13
- Phân tích thiết kế thuật toán
V : = Ðỉnh kế trong G ;
End;
End ; { Greedy}
.3. Tóm tắt ba giai đoạn để giải một bài toán
Mô hình toán học XD kiểu dữ liệu trừu Cấu trúc dữ liệu trừu
G.thuật không hình thức tượng tượng
C.trình bằng ngôn ngữ Chương trình thực thi
giả
Giai đoạn 1: Xây dựng mô hình toán thích hợp cho bài toán và tìm một thuật toán giải quyết
bài toán trên mô hình đó.
Giai đoạn 2: Thuật toán được trình bày bằng ngôn ngữ giả dựa trên các kiểu dữ liệu trừu
tượng.
Giai đoạn 3: Chọn một cách cài đặt một kiểu dữ liệu trừu tượng và thay ngôn ngữ giả bằng
các mã lệnh của một ngôn ngữ lập trình. Kết quả là ta được một chương trình hoàn chỉnh có thể
giải quyết được vấn đề đặt ra.
.4. Các kiểu dữ liệu trừu tượng (Abstract Data Type)
.4.1 Ðịnh nghĩa
Khi xây dựng thuật toán hoặc lập trình, chúng ta thường phải làm việc trên các dữ liệu và trong
mục này chúng ta xét một số khái niệm cơ bản về : các kiểu dữ liệu (Data Type), các cấu trúc dữ
liệu (Data Structure) và các kiểu dữ liệu trừu tượng (Abstract Data Type - ATD).
Trong một ngôn ngữ lập trình, kiểu dữ liệu của một biến là tập hợp các giá trị mà biến đó có
thể nhận được. Mỗi một ngôn ngữ lập trình đều có một số kiểu dữ liệu cơ sở khác nhau.
Một kiểu dữ liệu được thành lập bằng sự tập hợp các kiểu dữ liệu khác nhau gọi là kiểu dữ liệu
hợp thành hay kiểu dữ liệu có cấu trúc hay cấu trúc dữ liệu.
Một kiểu dữ liệu trừu tượng (ADT) là một mô hình toán học cùng với một tập hợp các phép
toán tác động trên mô hình đó.
Thông thường ta sẽ thiết kế thuật toán theo thuật ngữ của kiểu dữ liệu trừu tượng, nhưng để
cài đặt được thuật toán trong một ngôn ngữ lập trình, ta phải tìm cách biểu diễn kiểu dữ liệu trừu
tượng qua các kiểu dữ liệu của ngôn ngữ.
14
- Phân tích thiết kế thuật toán
.4.2 Ví dụ
Kiểu Set có thể được biểu diễn qua danh sách (List) và được quản lý bằng mảng (Array) hay
con trỏ (Pointer).
Kiểu Graph là một danh sách các số nguyên và các phép toán tác động trên nó là:
MakeNull (G): Tạo đồ thị rỗng.
W= First (G): Hàm trả về phần tử đầu danh sách của G (= Null nếu G rỗng).
W= Next (G): Hàm trả về phần tử kế tiếp trong G (= Null nếu là phần tử cuối).
Insert (V ,G): Xen phần tử V vào đồ thị G.
Ví dụ về kiểu mảng và bản ghi :
A: Array [1.. N] of Record
Field1: < Type1>;
Field2: < Type2>;
... ... ... ...
FieldN: < TypeN>;
End;
.5. Thời gian chạy của một chương trình
Trong khi giải bài toán ta có thể có một vài thuật toán, vấn đề là chọn thuật toán nào, tiêu
chuẩn như thế nào, thường có 2 yêu cầu chính:
Dễ hiểu, dễ viết chương trình.
Thuật toán dùng các tài nguyên hiệu quả như dùng ít bộ nhớ, chạy càng nhanh càng tốt,...
.5.1 Ðo thời gian chạy của một chương trình
Thời gian chạy của một chương trình phụ thuộc vào các yếu tố:
Dữ liệu đầu vào.
Tốc độ của máy được dùng.
Tính chất của trình biên dich được dùng.
Ðộ phức tạp tính toán của thuật toán.
15
- Phân tích thiết kế thuật toán
Trong thực tế thời gian chạy của một chương trình có thể xem như là một hàm của dữ liệu
vào. Cụ thể, đó là kích thước của dữ liệu vào. Vì vậy, ta gọi T(n) là thời gian chạy chương trình
với dữ liệu vào có độ dài là n.
Ðối với nhiều chương trình thì thời gian chạy chương trình còn phụ thuộc vào đặc tính của dữ
liệu vào. Nghĩa là dữ liệu vào có cùng độ dài nhưng thời gian chạy chương trình là khác nhau.
Vì vậy, ta có thể xem T(n) là thời gian chạy chương trình trong trường hợp xấu nhất trên dữ
liệu vào có độ dài là n. Hay nói cách khác T(n) là thời gian chạy chương trình với mọi dữ liệu vào
có độ dài là n.
Ðo thời gian chạy chương trình như thế nào ?
Chương trình A có thời gian chạy chương trình là T1(n)=n2.
Chương trình A có thời gian chạy chương trình là T2(n)=4*n+1
Đối với n càng lớn thì T1(n) càng lớn hơn T2(n), như vậy ta có thể xét bậc của hàm tính toán
thời gian hay còn gọi là độ phức tạp của thuật toán.
.5.2 Ðộ phức tạp của thuật toán
Cho một hàm f(n), f(n) được gọi là có bậc G(n) nếu tồn tại các hằng số C và N0 sao cho :
f(n) C * G(n) với n N0
Ví dụ : tìm bậc của hàm f(n) = (n+1)2
Ta có : f(n) có bậc G(n)=n2 vì : C = 4 và N0 = 1 để cho f(n) C * G(n) (n N0)
Giả sử T(n) là thời gian chạy chương trình, nếu T(n) có bậc là g(n) thì ta nói độ phức tạp tính
toán của thuật toán là G(n).
Ký hiệu O(G(n)) với :
O(C*f(n)) = O(f(n)) với C là hằng số. Trường hợp đặc biệt : O(C) = O(1) với C là hằng số.
.5.3 Cách tính thời gian chạy chương trình
Cách tính thời gian chạy của một chương trình bất kỳ là một vấn đề không đơn giản. Nhưng
đối với nhiều chương trình ta có thể tính thời gian chạy của nó theo 2 quy tắc sau: (áp dụng được
cho tất cả các chương trình không đệ quy).
16
- Phân tích thiết kế thuật toán
Chú ý :
Thời gian chạy của các lệnh gán Read, Write là O(1).
Thời gian chạy của một chuỗi tuần tự các lệnh được xác định theo quy tắc cộng. Như vậy thời gian này là thời
gian thi hành một lệnh nào đó lâu nhất trong chuỗi lệnh (câu lệnh đó được gọi là Câu lệnh tích cực).
Thời gian chạy của cấu trúc If là thời gian lớn nhất để thực hiện các lệnh sau Then hoặc sau Else cộng với thời
gian kiểm tra điều kiện. Thường thời gian kiểm tra điều kiện là O(1).
Thời gian thực hiện vòng lặp là tổng (trên tất cả các lần lặp) thời gian thực hiện từng vòng lặp. Nói cách khác
thời gian này được tính theo quy tắc nhân tức là tích của số lần lặp với thời gian thực hiện của thân vòng lặp.
Thời gian gọi thủ tục hay hàm là thời gian thực hiện đoạn chương trình tương ứng với hàm hay thủ tục đó.
Ví dụ 1: Câu lệnh
for i: = 1 to n do
for j: = 1 to n do
x:= x + 1;
Ví dụ 2:
Procedure BubbleSort (Var a: array [ 1 .. n ] of Integer);
Var i, j, Temp : Integer;
Begin
for i: = 1 to n do
for j: = i to n do
If a[i] > a[j] then
Begin
Temp:= a[i]; a[i]: = a[j]; (1)
a[j]:= Temp;
End;
17
- Phân tích thiết kế thuật toán
End;
Trong đó 5 dạng hàm đầu tiên gọi là hàm đa thức, còn 3 dạng hàm cuối gọi là hàm mũ. Một
thuật toán mà thời gian thực hiện có dạng là một hàm đa thức thì có thể chấp nhận được.
18
- Phân tích thiết kế thuật toán
BÀI TẬP
Bài 1 : Viết các thủ tục thực hiện các phép toán cộng và nhân 2 ma trận, rồi tính thời gian chạy của các thủ tục này.
Bài 2 : Hãy viết chương trình tính gần đúng Ġ theo công thức :
Sau đó hãy tính thời gian chạy của chương trình.
Bài 3 : Viết chương trình nhập vào một ma trận vuông cấp n. Sau đó in ra các phần tử thuộc các đường chéo song
song với đường chéo chính. Phác họa thuật toán của chương trình và tính độ phức tạp của thuật toán.
Bài 4 : Hãy tìm một thuật toán để tính Ġ sao cho độ phức tạp của thuật toán sẽ là O(n) và viết chương trình thể hiện
thuật toán đã đề ra bằng ngôn ngữ Pascal.
Bài 5 : Hãy viết chương trình đổi một số nguyên dương ở hệ thập phân (cơ số 10) sang hệ nhị phân (cơ số 2) và
đánh giá thời gian thực hiện của thuật toán.
19
- Phân tích thiết kế thuật toán
BÀI 2 : CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG
Mã bài : ITPRG3_12.2
Giới thiệu
Mỗi một thuật toán là được xây dựng trên những kiểu dữ liệu tương ứng. Những kiểu dữ liệu
này cho phép chúng ta dễ dàng cài đặt các thuật toán trong việc sử dụng những hỗ trợ sẵn có của
nó. Nhiều bài toán là không thể được giải quyết nếu không có các kiểu dữ liệu tương ứng, ví dụ :
danh sách để lưu trữ một tập các phần tử, con trỏ để tạo các danh sách động...
Trong bài này chúng ta sẽ xem xét những kiểu dữ liệu cơ bản nhất như con trỏ, danh sách,
hàng đợi... Chúng ta quan tâm ở đây những vấn đề chính như cách sử dụng, phương pháp để
khai báo và sử dụng những hàm có sẵn để dùng trên các kiểu dữ liệu này.
Mục tiêu thực hiện
Học xong bài này học viên sẽ có khả năng:
Nắm được các khái niệm cơ bản và hiểu được tầm quan trọng của việc sử dụng các cấu trúc dữ liệu trừu
tượng trong việc xây dựng thuật toán.
Cách thức khai báo và các hàm có sẵn (ví dụ trong Turbo Pascal) trên các dữ liệu này.
Áp dụng các kiểu dữ liệu này trên một số kiểu bài toán thường gặp.
2.1Khái niệm về con trỏ (Pointer)
2.1.1Ðịnh nghĩa
Con trỏ là một kiểu dữ liệu (chiếm 4 bytes trong bộ nhớ) mà các giá trị của nó là địa chỉ của
các phần tử của kiểu dữ liệu mà nó trỏ đến.
Các giá trị của biến thuộc kiểu T được phát sinh bất cứ lúc nào khi biến đó được cấp phát
bằng lệnh New.
2.1.2Khai báo
Gián tiếp :
Type Tên kiểu = ^Kiểu dữ liệu;
20
nguon tai.lieu . vn
