1. Khái niệm bài toán
- Bài toán là một
việc nào đó mà ta muốn máy tính thực hiện.
- Giải bài toán trên máy tính, cần
quan tâm đến 2 yếu tố:
+ Input: Thông tin
đưa vào máy tính
+ Output: Dữ
liệu lấy ra từ máy tính
- Ví dụ: Bài toán tìm ước chung lớn nhất của 2 số nguyên dương M và N,
khi đó:
+ Input: hai số nguyên dương M, N.
+ Output: ước chung lớn nhất của M và N
2. Khái niệm thuật toán
Thuật toán là 1 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 được Output cần tìm.
* Biểu diễn thuật toán: có hai cách
- Sử dụng cách liệt kê
- Sử dụng sơ đồ khối
Một số kí hiệu dùng trong sơ đồ khối
*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 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à thuật toán kết thúc hoặc là có đúng 1
thao tác xác định để được thực hiện 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: Tìm giá trị lớn nhất của
một dãy số nguyên
* Xác định bài toán
- 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.
* Xây
dựng thuật toán:
a. Cách 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 rồi kết thúc;
+ B4:
B4.1:
Nếu ai > Max thì Max <-- ai;
B4.2:
i <-- i+1 rồi quay lại bước 3;
b. Sơ đồ khối (SGK tin 10-trang 34)
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 (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 a1`, a2,…,aN;
-
Output: Dãy A được sắp xếp 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 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
* Xây dựng thuật toán
a)
Cách liệt kê
-
Bước 1: Nhập N, các số hạng a1,
a2,…,aN;
-
Bước 2: M ← N;
-
Bước 3: Nếu M < 2 thì đưa ra dãy A đã
được sắp xếp, rồi kết thúc;
-
Bước 4: M ← M – 1, i ← 0;
-
Bước 5: i ← i + 1;
-
Bước 6: Nếu i > M thì quay lại bước
3;
-
Bước 7: Nếu ai > a1 + 1
thì tráo đổi ai và a1 + 1 cho nhau;
-
Bước 8: Quay lại bước 5;
b)
Sơ đồ khối (SGK tin 10-trang 39)
Ví dụ 3: Bài toán tìm kiếm tuần tự
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ố
đó.
*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ự được thực hiện một
cách tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta so sánh giá trị số hạng đang
xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã được xét hết và
không có giá trị nào bằng khóa.
* Xây dựng thuật toán
a) Cách liệt kê
- Bước 1: Nhập
N, các số hạng a1, a2,…, aN và khoá k;
- Bước 2: i ←
1;
- Bước 3: Nếu
ai = k thì thông báo chỉ số i, rồi kết thúc;
- Bước 4: i
←i+1;
- Bước 5: 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;
- Bước 6: Quay
lại bước 3;
b) Sơ đồ khối (SGK tin 10-trang 41)