Bài giảng Tin học cơ sở - Chương 6: Giải thuật (Algorithms)

Nội dung text: Bài giảng Tin học cơ sở - Chương 6: Giải thuật (Algorithms)

1. 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
2. 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ã
3. 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 Vào/ra Bắt đầu Kết thúc dữ liệu Sai B A Đúng Thực hiện công việc A
4. Bắt đầu Nhập a, b r := a mod b a := b r = 0 b := r Sai Đúng Đưa ra b Kết thúc 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ã
5. 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
6. 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
7. 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
8. 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?
9. 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