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 đó 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 a₁,a₂,…,a_N.

- Output: Giá trị lớn nhất Max của dãy số.

 * Ý tưởng

+ Khởi tạo giá trị Max= a₁.

+ Lần lượt với i từ 2 đến N so sánh a_i với Max, nếu a_i>Max thì Max= a_i.

 * Xây dựng thuật toán:

a. Cách liệt kê:

+ B1: Nhập N và dãy a₁,...,a_N;

+ B2: Max <-- a₁, i <-- 2;

+ B3: Nếu i>N thì đưa ra giá trị Max rồi kết thúc;

+ B4:

                             B4.1: Nếu a_i > Max thì Max <-- a_i;

                             B4.2: i <-- i+1 rồi quay lại bước 3;

b. Sơ đồ khối (SGK tin 10-trang 34)

Ví dụ 2: Bài toán sắp xếp bằng tráo đổi

Cho dãy A gồm N số nguyên a₁, a₂,…,a_N. 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 a_1`, a₂,…,a_N;

- 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 a₁, a₂,…,a_N;

- 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 a_i > a_{1 + 1} thì tráo đổi a_i và a_{1 + 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 a₁, a₂,…, a_N và một số nguyên k. Cần biết có hay không chỉ số i (1 ≤ i ≤ N) mà a_i = 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 a₁, a₂, …, a_N và số nguyên k;

- Output: Chỉ số i mà a_i = 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 a₁, a₂,…, a_N và khoá k;

- Bước 2: i ← 1;

- Bước 3: Nếu a_i = 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)