Giáo trình Tin học cơ sở - Chương 6: Giải thuật (Algorithms)

Chương 6: Giải thuật (Algorithms) I-Phương pháp giải quyết vấn đề bằng máy tính Bài toán => Giải thuật => Chương trình => Ngôn ngữ máy => Máy thực hiện Chương 6: Giải thuật (Algorithms) I-Phương pháp giải quyết vấn đề bằng máy tính Bài toán => Giải thuật => Chương trình => Ngôn ngữ máy => Máy thực hiện II-Khái niệm về giải thuật 1. Khái niệm 2. Các tính chất của giải thuật Chương 6: Giải thuật (Algorithms) II-Khái niệm về giải thuật 1. Khái niệm 2. Các tính chất của giải thuật - Tính thực hiện được: - Tính kết thúc: - Tính kết quả: - Tính hiệu quả: - Tính duy nhất: - Tính tổng quát: - Tính hình thức: Chương 6: Giải thuật (Algorithms) III-Các cách diễn đạt giải thuật 1. Liệt kê các bước bằng lời 2. Lưu đồ giải thuật 3. Giả mã Chương 6: Giải thuật (Algorithms) III-Các cách diễn đạt giải thuật 1. Liệt kê các bước bằng lời Ví dụ: Giải thuật tìm USCLN(a,b) B1: Nhập vào hai số nguyên a, b B2: Đem a chia nguyên cho b, lấy phần dư để trong r. B3: Nếu r = 0 thì chuyển sang B4. Nếu r ¹ 0 thì a lấy giá trị của b, b lấy giá trị của r và quay lại B2. B4: Đưa ra USCLN là b B5: Kết thúc Chương 6: Giải thuật (Algorithms) III-Các cách diễn đạt giải thuật 2. Lưu đồ giải thuật Bắt đầu Kết thúc Vào/ra dữ liệu A Thực hiện công việc A B Đúng Sai Bắt đầu Kết thúc Nhập a, b r := a mod b r = 0 Đưa ra b Đúng Sai a := b b := r Chương 6: Giải thuật (Algorithms) III-Các cách diễn đạt giải thuật 3. Dùng giả mã Chương 6: Giải thuật (Algorithms) III-Các cách diễn đạt giải thuật 3. Dùng giả mã • Vào: a, b • Ra: USCLN(a,b) 1) Read(a,b); 2) r := a mod b; 3) While r ¹ 0 do begin a := b; b := r; r:=a mod b; end; 4) Write(b); 5) Kết thúc Chương 6: Giải thuật (Algorithms) IV-Một số giải thuật cơ bản 1. Hoán đổi nội dung 2 ô nhớ (đổi chỗ) Ví dụ: Hoán đổi nội dung 2 ô nhớ a và b 1) tg := a; 2) a : = b; 3) b := tg; Sau này, viết gọn là DoiCho(a,b) hoặc a :=: b hoặc a « b Chương 6: Giải thuật (Algorithms) IV-Một số giải thuật cơ bản 2. Tìm giá trị lớn nhất/nhỏ nhất trong 1 dãy số Ví dụ: Cho dãy số a1, a2,, an. Tìm giá trị lớn nhất Chương 6: Giải thuật (Algorithms) 1) read(n); 2) read(a[1], a[2],, a[n]); 3) max:=a[1]; 4) For i:=2 to n do If a[i] > max then max:=a[i]; 5) write(max); 6) Kết thúc Chương 6: Giải thuật (Algorithms) IV-Một số giải thuật cơ bản 3. Sắp xếp dãy số tăng/giảm dần Ví dụ: Cho dãy số a1, a2,, an. Sắp xếp dãy số tăng dần từ trái qua phải. Chương 6: Giải thuật (Algorithms) Giải thuật 1: 1) Read(n); 2) Read(a[1], a[2],, a[n]); 3) For i:=1 to n-1 do For j:=i+1 to n do If a[j] < a[i] then a[i] « a[j] 4) Write(a[1], a[2],, a[n]); 5) Kết thúc Chương 6: Giải thuật (Algorithms) Giải thuật 2: 1) Read(n); 2) Read(a[1], a[2],, a[n]); 3) For i:=1 to n-1 do begin +) k:=i; +) For j:=i+1 to n do If a[j] < a[k] then k:=j; + If k ¹ i then a[i] « a[k]; end; 4) Write(a[1], a[2],, a[n]); 5) Kết thúc Chương 6: Giải thuật (Algorithms) IV-Một số giải thuật cơ bản 4. Tìm giá trị x trong dãy số Ví dụ: Cho dãy số a1, a2,, an. Tìm xem có phần tử nào bằng x không? Chương 6: Giải thuật (Algorithms) 1) Read(n); 2) Read(a[1], a[2],, a[n]); 3) Read(x); 4) Co:=FALSE; {Ban dau la khong co} 5) For i:=1 to n do If a[i] = x Then begin Co:=TRUE; break; end; 6) If Co = TRUE Then write(‘Co phan tu bang x’) Else write(‘Khong co phan tu bang x’); 7) Kết thúc