Bài 4: Bài toán và thuật toán

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;

Cách lập sơ đồ khối:

– Thuật toán còn được miêu 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 triển khai 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án
Cá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à 1 số ít 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.

– Ý tưởng : lần lượt từ số hạng thứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp 1 số ít hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá. Trong trường hợp thứ 2 dãy A không có số hạng nào bằng khoá …
– 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

Source: https://final-blade.com
Category : Kiến thức Internet