Bài giảng Tin học đại cương (Phần 2): Chương 2 - TS. Nguyễn Kim Hiếu

Bài giảng "Tin học đại cương (Phần 2) - Chương 2: Thuật toán" cung cấp cho người học các kiến thức: Định nghĩa thuật toán, biểu diễn thuật toán, một số thuật toán thông dụng, thuật toán đệ quy, thuật giải heuristic. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học đại cương (Phần 2): Chương 2 - TS. Nguyễn Kim HiếuNội dung chương nàyIT1110 Tin học đại cươngPhần II Giải quyết bài toánChương 2 Thuật toán2.1. Định nghĩa thuật toán2.2. Biểu diễn thuật toán2.3. Một số thuật toán thông dụng2.4. Thuật toán đệ quy2.5. Thuật giải heuristic212.1. Định nghĩa thuật toánVí dụ 1: Thuật toán tìm phần tử lớn nhấtcủa một dãy hữu hạn các số nguyênLà một khái niệm cơ sở của toán học và tinhọc.Bao gồm một dãy hữu hạn các lệnh/chỉ thịrõ ràng và có thể thi hành được để hướngdẫn thực hiện một hành động nhằm đạtđược mục tiêu đề ra.Thuật toán là sự thể hiện của một phươngpháp để giải quyết một vấn đề.Các bước:31. Đặt giá trị lớn nhất tạm thời là số nguyên đầu tiên.2. So sánh số nguyên kế tiếp trong dãy với giá trị lớnnhất tạm thời, nếu số nguyên này lớn hơn giá trị lớnnhất tạm thời thì đặt giá trị lớn nhất tạm thời bằng sốnguyên này.3. Lặp lại bước 2 nếu còn số nguyên trong dãy chưađược xét.4. Dừng nếu không còn số nguyên nào trong dãy chưađược xét. Giá trị lớn nhất tạm thời lúc này chính là giátrị lớn nhất trong dãy số.4Các đặc trưng của thuật toánVí dụ 2: Thuật toán giải phương trình bậchai: ax2 + bx + c = 0 (a0)1. Nhập 3 hệ số a, b, c2. Tính giá trị Δ = b2 - 4*a*c3. Xét dấu Δ. Nếu Δ>0 thì thực hiện các thao tácsau đây:3.1. Tính các nghiệm theo các công thức:x1 = (-b-sqrt(Δ))/(2*a)x2 = (-b+sqrt(Δ))/(2*a)3.2. Xuất kết quả: phương trình có hai nghiệm x 1 và x2.4. Nếu Δ là 0 thì xuất kết quả: phương trình cónghiệm kép là -b/(2*a)5. Nếu Δ 0 thenx1  (-b-sqrt(Δ))/(2*a)x2  (-b+sqrt(Δ))/(2*a)Xuất: x1 và x2, Dừngelse if delta = 0 then x12  -b/(2*a), Xuất: nghiệm kép x12else Xuất: phương trình vô nghiệmend ifThuật toánThuật toánnguyênThuật toándãyThuật toánThuật toánkiểm tra số nguyên tốtìm USCLN, BSCNN của 2 sốtìm phần tử lớn nhất trong mộtsắp xếptìm kiếm13142.4. Thuật toán đệ quyTìm phần tử lớn nhất trong một dãy hữu hạn sốNhập: dãy số a[1], a[2], a[3],… a[n] Xuất: max là giá trị lớn nhất trong dãy số đã cho Thuật toán:max  a[1]for i = 2 to n doif max < a[i] thenmax  a[i]end ifend forXuất: max là giá trị lớn nhất trong dãy sốCó một số trường hợp, cách giải có thể vi phạm cáctính chất của thuật toán nhưng lại khá đơn giản vàđược chấp nhận.Bài toán có thể được phân tích và đưa tới việc giảimột bài toán cùng loại nhưng cấp độ thấp hơn.Ví dụ:Định nghĩa giai thừaĐịnh nghĩa dãy số Fibonacci: 1, 1, 2, 3, 5, 8, 13,...150! = 1n! = n*(n-1)! với n>0f1 = 1,f2 = 1,fn = fn-1 + fn-216Thuật toán đệ quy (2)Thuật toán đệ quy (3)Thuật toán đệ quy tính giai thừa của 1 số tựnhiên:Input: số tự nhiên nOutput: F(n) bằng n!Thuật giải:1. F  12. if n>0 then F  F(n-1)*n3. Output FThuật toán đệ quy tính số hạng thứ n củadãy số Fibonacci:Input: số tự nhiên nOutput: F(n) bằng số hạng thứ n của dãyThuật giải:1. if n=1 or n=2 then F  12. if n>2 then F  F(n-1)+F(n-2)3. Output F1718Thuật toán đệ quy (4)Bài tậpĐặc điểm của thuật toán đệ quy:Có 1 trường hợp cơ sở/trường hợp dừngCó phần đệ quy bên trong thuật toán (nó gọiđến chính nó)Có sự biến đổi tiến tới trường hợp cơ sở.19Viết thuật toán tìm USCLN của hai số tựnhiênViết thuật toán tìm BSCNN của hai số tựnhiênViết thuật toán tìm phần tử lớn nhất trongmột dãy số hữu hạnViết thuật toán sắp xếpViết thuật toán tìm kiếm20