Cách viết thuật toán trong tin học 10

      17

Bài 4. Bài tân oán và thuật toán

1. Khái niệm bài toán

a, Khái niệm

- Bài toán là một việc như thế nào đó nhưng mà con người muốn laptop thực hiện

- Các yếu tố của một bài xích toán:

+ Input: Thông tin đã biết, đọc tin đưa vào lắp thêm tính

+ Output: Thông tin cần search, biết tin lấy ra từ thứ tính

b. Ví dụ

+ Tìm USCLN của 2 số nguyên ổn dương

+ Tìm số lớn nhất trong 3 số nguim dương a,b,c

+ Tìm nghiệm của phương trình bậc nhất: ax + b = 0 (a≠0)

+ ...

Bạn đang xem: Cách viết thuật toán trong tin học 10

2. Khái niệm thuật toán

a. Khái niệm

Thuật tân oán để giải một bài xích tân oán là:

+ Một dãy hữu hạn các thao tác làm việc (tính dừng)

+ Các thao tác được tiến hành theo một trình tự xác định (tính xác định)

+ Sau lúc thực hiện chấm dứt dãy các thao tác làm việc đó ta nhận được đầu ra của bài tân oán (tính đúng đắn)

b. Cách biểu diễn thuật toán

Có 2 phương pháp để biểu diễn thuật toán:

- Cách cần sử dụng phương pháp liệt kê: Nêu ra tuần tự các làm việc cần tiến hành

+ Ví dụ:Cho bài xích toán Tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 (a≠0)?

+ Xác định bài xích toán

Input: Các số thực a, b, c

Output: Các số thực x thỏa mãn ax2 + bx + c = 0 (a≠0)

+ Thuật toán:

Bước 1: Nhập a, b, c (a≠0)

Bước 2: Tính Δ = b2 – 4ac

Bước 3: Nếu Δ>0 thì phương trình có 2 nghiệm là

*

Bước 4: Nếu Δ = 0 thì phương trình có nghiệm kép

*

rồi kết thúc thuật toán. Nếu không chuyển quý phái bước tiếp theo

Bước 5: Kết luận phương trình vô nghiệm rồi kết thúc

- Cách sử dụng sơ đồ khối

+ Hình thoi: thể hiện thao tác so sánh;

*

+ Hình chữ nhật: thể hiện những phép tính toán;

*

+ Hình ô van: thể hiện thao tác làm việc nhập, xuất dữ liệu;

*

+ Các mũi tên: qui định trình tự thực hiện các thao tác.

*

3. Một số ví dụ về thuật toán

Bài toán thù 1: Kiểm tra tính nguyên tố

1. Xác định bài bác toán

- Input: N là một số nguim dương

- Output:

+ N là số nguyên tố hoặc

+ N không là số nguim tố

- Định nghĩa: "Một số ngulặng dương N là số nguim tố nếu nó chỉ tất cả đúng hai ước là một trong cùng N"

- Tính chất:

+ Nếu N = 1 thì N không là số nguyên tố

+ Nếu 1 1 của N

+ Nếu i

*

Hình 1. Sơ đồ khối thuật tân oán kiểm tra tính nguyên ổn tố của một số nguyên dương N​

Lưu ý:Nếu N ≥ 4 với không có ước trong phạm vi từ 2 đến phần nguim căn bậc 2 của N thì N là số nguyên tố

Bài tân oán 2: Sắp xếp bằng bí quyết tráo đổi

1. Xác định bài toán

- Input: Dãy A gồm N số ngulặng a1, a2,…,an

Ví dụ : Dãy A gồm những số nguyên: 2 4 8 7 1 5

- Output: Dãy A được sắp xếp thành dãy không giảm

Dãy A sau thời điểm sắp xếp: 1 2 4 5 7 8

2. Ý tưởng

- Với mỗi cặp số hạng đứng liền kề trong dãy, nếu số trước > số sau ta đổi chỗ chúng cho nhau.(Các số lớn sẽ được đẩy dần về vị trí xác định cuối dãy)

- Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần đối chiếu đến đến lúc không tồn tại sự đổi chỗ làm sao xảy ra nữa

3. Xây dựng thuật toán

- Bước 1. Nhập N, những số hạng a1, a2,…,an;

- Bước 2. Đầu tiên gọi M là số số hạng cần so sánh, vậy M sẽ chứa giá trị của N:

- Bước 3. Nếu số số hạng cần so sánh số phép đối chiếu M: đã trả tất M số phnghiền so sánh của lượt này. Lặp lại bước 3, bắt đầu lượt kế (với số số hạng cần so sánh mới đó là M đã giảm 1 ở bước 4);

- Bước 7. So sánh 2 phần tử ở lần thứ i là ai cùng ai+1. Nếu ai > ai+1 thì tráo đổi 2 phần tử này;

- Bước 8. Quay lại bước 5

a) Đối chiếu, sinh ra những bước liệt kê

*

b) Sơ đồ khối

*

Hình 2. Sơ đồ khối thuật toán sắp xếp bằng cách tráo đổi​

Bài toán thù 3: Tìm kiếm tuần tự

1. Xác định bài bác toán

- Input : Dãy A gồm N số ngulặng khác biệt a1, a2,…,an với một số nguim k (khóa)

Ví dụ : Dãy A gồm các số nguyên: 5 7 1 4 2 9 8 11 25 51 . Và k = 2 (k = 6)

- Output: Vị trí i nhưng mà ai = k hoặc thông tin không tìm thấy k vào dãy. Vị trí của 2 trong hàng là 5(không tìm kiếm thấy 6)

2. Ý tưởng

Tìm kiếm tuần tự được thực hiện một bí quyết tự nhiên: Lần lượt đi từ số hạng thứ nhất, ta đối chiếu giá chỉ 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 nhưng mà không tìm kiếm thấy giá trị của khóa trên hàng.

Xem thêm: 5 Cách Chế Biến Món Ăn Từ Cải Thảo Xào Ngon Miệng Dễ Làm Từ Các Đầu Bếp Tại Gia

3. 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 cùng giá chỉ trị 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 tin hàng A không có số hạng làm sao 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

*

Hình 3. Sơ đồ khối thuật tân oán search kiếm tuần tự​

Bài toán 4: Tìm kiếm nhị phân

1. Xác định bài toán

- Input: Dãy A là hàng tăng gồm N số nguyên không giống nhau a1, a2,…,an và một số nguyên ổn k.

Ví dụ: Dãy A gồm các số nguyên: 2 4 5 6 9 21 22 30 31 33. Và k = 21 (k = 25)

- Output đầu ra : Vị trí i mà lại ai = k hoặc thông báo không tìm kiếm thấy k trong dãy. Vị trí của 21 trong hàng là 6 (không tìm kiếm thấy 25)

2. Ý tưởng

- Sử dụng tính chất dãy A đã sắp xếp tăng, ta kiếm tìm giải pháp thu hẹp nhanh vùng tra cứu kiếm bằng giải pháp đối chiếu k với số hạng ở giữa phạm vi search kiếm (agiữa), Khi đó chỉ xảy ra một trong tía trường hợp:

+ Nếu agiữa= k thì tìm kiếm được chỉ số, kết thúc;

+ Nếu agiữa > k thì việc search kiếm thu hẹp chỉ xét từ ađầu (phạm vi) → agiữa - 1;

+ Nếu agiữa giữa + 1 → acuối (phạm vi).

- Quá trình bên trên được lặp lại cho đến Khi search thấy khóa k bên trên dãy A hoặc phạm vi tra cứu kiếm bằng rỗng.

3. Xây dựng thuật toán

a) Cách liệt kê

*

b) Sơ đồ khối

*

Hình 4. Sơ đồ khối thuật tân oán tra cứu kiếm tuần tự​