zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 - Tổng cục dạy nghề

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:109

Báo xấu

86
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 cung cấp cho người học những kiến thức tổng quan về phân tích thiết kế thuật toán, các kiểu dữ liệu trừu tượng và các cấu trúc dữ liệu cơ bản. Để hiểu rõ hơn, mời các bạn tham khảo chi tiết nội dung giáo trình này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình Phân tích thiết kế thuật toán (Nghề Lập trình máy tính): Phần 1 - Tổng cục dạy nghề

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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.