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

I. Khái niệm bài toán:
· Trong tin học, bài toán là một việc mà ta muốn máy tính thực hiện.
· Các yếu tố xác định một bài toán:
+ Input (thông tin đưa vào máy): dữ liệu vào
+ Output (thông tin muốn lấy ra từ máy): dữ liệu ra

VD 1: Tìm UCLN của 2 số M, N.
VD 2: Tìm nghiệm của pt
ax2 + bx + c = 0 ( a ≠ 0)
VD3: Kiểm tra số nguyên dương n có phải là một số nguyên tố không?
VD 4: Xếp lạo học tập của một lớp.

II. 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 một 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 được Output cần tìm.
Ví dụ: Tìm giá trị lớn nhất của một dãy số nguyên cho trước.
· Xác định bài toán:
+ Input:
– số nguyên dương N.
– N số a1, a2, …, aN.
+ Output: giá trị Max.

· Thuật toán: (Liệt kê)
B1: Nhập N
và dãy a1, …, aN
B2: Max <== a1; i <== 2
B3: Nếu i > N thì đưa ra giá trị Max và kết thúc.
B4: Nếu ai > max
thì Max <== ai
B5: i <== i+1, quay lại B3.

Mô phỏng các bước thực hiện thuật toán trên với
N = 11 và dãy A: 5, 1, 4, 7, 6, 3, 15, 8, 4, 9, 12.


· Tính chất thuật toán:
– Tính dừng: thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.
– Tính xác định: sau khi thực hiện 1 thao tác thì hoặc là kết thúc hoặc thực hiện 1 thao tác kế tiếp.
– Tính đúng đắn: sau khi kết thúc phải nhận được Output.

III. Một số ví dụ về thuật toán.
1. Ví dụ 1: Kiểm tra tính nguyên tố của một số nguyên dương.
· Ý tưởng:
+ Nếu N=1 thì N không là số nguyên tố;
+ Nếu 1 < N < 4 thì N là số nguyên tố.
+ Nếu N ≥ 4 và không có ước số trong phạm vi từ 2 đến phần nguyên căn bậc hai của N thì N là số nguyên tố.
· Thuật toán:
a) Cách liệt kê:
B1: Nhập số ng.dương N;
B2: Nếu N = 1 thì thông báo N không nguyên tố rồi kết thúc;
B3: Nếu N< 4 thì thông báo N là nguyên tố rồi kết thúc;
B4: i <== 2 ;
B5: Nếu i> (√N) thì thông báo N là nguyên tố rồi kết thúc.
B6: Nếu N chia hết cho i thì thông báo N không nguyên tố rồi kết thúc;
B7: i <== i + 1 rồi quay lại B5


2. Ví dụ 2: Bài toán sắp xếp
Cho dãy A gồm N số nguyên a1, a2, …, aN. Cần sắp xếp các số hạng để dãy A trở thành dãy không giảm.
· Thuật toán sắp xếp bằng tráo đổi (Exchange Sort)
· Xác định bài toán:
- Input: Dãy A gồm N số nguyên a1, a2, …, an.
- Output: Dãy A được sắp xếp lại thành dãy không giảm.
· Ý tưởng: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước lớn hơn số sau thì ta đổi chỗ chúng cho nhau. Việc đó được lặp lại, cho đến khi không có sự đổi chỗ nào xảy ra nữa.
· Thuật toán:
a) Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN ;
- B2: M <== N ;
- B3: Nếu M< 2 thì đưa ra dãy A đã được sắp xếp rồi kết thúc;
- B4: M <== M–1; i <== 0;
- B5: i <== i+1;
- B6: Nếu i > M thì quay lại bước 3;
- B7: Nếu ai > ai+1 thì tráo đổi ai và ai+1 cho nhau;
- B8: Quay lại bước 5.


3. 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, a2, …, aN và một số nguyên k. Cần biết có hay không chỉ số i ( 1 ≤ i ≤ N) mà ai = k. Nếu có hãy cho biết chỉ số đó.
a) Thuật toán tìm kiếm tuần tự
(sequential search)
· Xác định bài toán
- Input: Dãy A gồm N số nguyên khác nhau a1, a2, …, 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ị bằng k.
· Ý tưởng:
- Tìm kiếm tuần tự là 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 một số 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ứ hai dãy A không có số hạng nào bằng khoá.
· Thuật toán:
* Cách liệt kê:
- B1: Nhập N, các số hạng a1, a2, …, aN và khoá k;
- B2: i <== 1;
- B3: Nếu ai = k thì thông báo chỉ số i, kết thúc;
- B4: i <== 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.


b) Thuật toán tìm kiếm nhị phân (Binary Search)
· Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, …, aN và một 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ị bằng k.