BÀI 4. BÀI TOÁN VÀ THUẬT TOÁN
1. Khái niệm bài toán
- Bài toán là một việc nào đó ta muốn máy tính thực hiện. Ví dụ: Giải phương trình bậc 2, quản lý nhân viên…
- Các bài toán được cấu tạo bởi 2 thành phần cơ bản:
- Input: các thông tin đã có.
- Output: Các thông tin cần tìm từ Output.
2. Khái niệm thuật toán
- Thuật toán để giải một bài toán là một dãy hữu hạn các thao tác được sắp xếp theo 1 trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận ra Output cần tìm.
- Ví dụ: Tìm giá trị lớn nhất của 1 dãy số nguyên.
=> Ta có 3 bước thực hiện như sau:
* Xác định BT- Input: Số nguyên dương N và dãy N số nguyên a1, a2, …, aN.
- Output: Giá trị lớn nhất Max của dãy số.
* Ý tưởng
- Khởi tạo giá trị Max = a1.
- Lần lượt với i từ 2 đến N so sánh ai với Max, nếu ai>Max thì Max= ai.
* Thuật toán:
Cách liệt kê:
- B1: Nhập N và dãy a1,...,aN;
- B2: Max \(\leftarrow\) a1, i \(\leftarrow\) 2;
- B3: nếu i>N thì đưa giá trị Max rồi kết thúc;
- B4: Nếu ai>Max thì Max \(\leftarrow\) ai;
- B5: i \(\leftarrow\) i+1 rồi quay lại bước 3;
- Thuật toán còn được diễn tả bằng sơ đồ khối.
- Quy định:
- Hình ô van: các thao tác nhập, xuất dữ liệu.
- Hình thoi: Thao tác so sánh.
- Hình chữ nhật: Các phép toán.
- Mũi tên: trình tự thực hiện các thao tác.
Ví dụ: Mô phỏng việc thực hiện thuật toán với N=8 và dãy số: 5, 1, 4, 7, 6, 3, 15, 11
Ds
|
5
|
1
|
4
|
7
|
6
|
3
|
15
|
11
|
i
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
Max
|
5
|
5
|
5
|
7
|
7
|
7
|
15
|
15
|
=> Các tính chất của thuật toán:
- Tính dừng: Thuật toán phải kết thúc sau một số hữu hạn lần thực hiện các thao tác.
- Tính xác định: Sau một số lần thực hiện thao tác, hoặc là kết thúc hoặc xác định để thực hiện bước tiếp theo.
- Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.
3. Một số ví dụ về thuật toán
Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.
- Xác định bài toán:
- Input: Số nguyên dương N.
- Output: “N là số nguyên tố” hoặc “N không là số nguyên tố”.
- Ý tưởng: Ta nhớ lại định nghĩa: Một số nguyên dương N là số nguyên tố nếu nó có đúng 2 ước số khác nhau là 1 và chính nó. Do đó ta có:
- Nếu N = 1 thì N không là nguyên tố.
- Nếu 1 < N < 4 thì N là số nguyên tố.
- Nếu N \(\ge\) 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc 2 của N thì N là số nguyên tố.
- Thuật toán:
- B1: Nhập số nguyên dương N.
- B2: Nếu N = 1 thì thông báo N không là số nguyên tố rồi kết thúc.
- B3: Nếu N < 4 thì thông báo N là số nguyên tố rồi kết thúc.
- B4: i \(\leftarrow\) 2
- B5: Nếu N>[\(\sqrt{N}\)](*) thì thông báo N là số nguyên tố rồi kết thúc.
- B6: Nếu N chia hết cho i thì thông báo N là số không nguyên tố rồi kết thúc.
- B7: i \(\leftarrow\) i + 1 rồi quay lại bước 5.
Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, a3, …,aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạng sau)
- Xác định bài toán:
- Input: Dãy A gồm N số nguyên
- Output: Dãy A được sắp xếp thành dãy không giảm.
Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
- Ý tưởng: Với 2 số liền kề, nếu số trước lớn hơn số sau ta đổi chổ cho nhau. Việc đó lặp lai, khi không còn sự đổi chổ nào nữa.
- Thuật toánCách liệt kê:
- B1: Nhập vào n và dãy số nguyên a1, . . . ,aN;
- B2: M \(\leftarrow\) N;
- B3: Nếu M<2 thì in dãy đã sắp xếp rồi kết thúc;
- B4. M \(\leftarrow\) M – 1; i \(\leftarrow\) 0;
- B5: i \(\leftarrow\) i + 1;
- B6: Nếu i > M thì quay lại bước 3;
- B7. Nếu ai > ai+1 thì tráo đổi cho nhau;
- B8: Quay lại bước 5;
Ví dụ 3: Bài toán tìm kiếm
Cho dãy A gồm N số nguyên khác nhau: a1…aN. và một số nguyên k. Cần biết có hay không chỉ số i mà ai=k. Nếu có hãy cho biết chỉ số đó.Thuật toán tìm kiếm tuần tự:
- Xác định bài toán
- Input: dãy A gồm N số nguyên khác nhau: a1…aN và số nguyên k.
- Output: chỉ số i mà ai=k hoặc thông báo không có số hạng nào của dãy A có giá trị là k.
- Thuật toán
Liệt kê:
- B1: Nhập vào N, các số hạng a1, . . . ,aN và khóa k;
- B2: i\(\leftarrow\)1;
- B3: Nếu ai=k thì thông báo chỉ số i rồi kết thúc;
- B4. i \(\leftarrow\)i+1;
- B5: Nếu i>N thì thông báo dãy A không có số hạng nào có giá trị bằng k rồi kết thúc;
- B6: Quay lại bước 3;
Dãy A có N = 7 khóa k = 10
Tìm chỉ số i để ai = k.
i
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
ai
|
7
|
12
|
4
|
6
|
11
|
10
|
8
|
Ghi chú: k = 10 → i = 6
Trong thuật toán trên, i là biến chỉ số và nhận giá trị nguyên lần lượt từ 1 đến N + 1
Biểu Tượng Cảm XúcBiểu Tượng Cảm Xúc