Thuật toán là 1 trong những dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác minh sao cho sau khi thực hiện nay dãy thao tác ấy, từ input đầu vào của bài xích toán, ta cảm nhận Output bắt buộc tìm.

Bạn đang xem: Bài tập thuật toán tin học 10

Bạn đã xem: những dạng thuật toán tin học tập lớp 10

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

- Bài toán là một câu hỏi nào đó mà con người muốn máy vi tính thực hiện.

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

+ Input: Thông tin đã biết, thông tin đưa vào đồ vật tính.

+ Output: Thông tin đề xuất tìm, thông tin mang ra từ đồ vật tính.

- Ví dụ: việc tìm cầu chung lớn nhất của 2 số nguyên dương, lúc đó:

+ Input: hai số nguyên dương A, B.

+ Output: ước chung lớn số 1 của A cùng B

2. Có mang thuật toán

a) Khái niệm

Thuật toán là một dãy hữu hạn các thao tác được thu xếp theo 1 trình tự xác định sao cho sau khi thực hiện nay dãy làm việc ấy, từ đầu vào của bài toán, ta nhận thấy Output yêu cầu tìm.

b) trình diễn thuật toán

- thực hiện cách liệt kê: nêu ra tuần tự các thao tác làm việc cần tiến hành.

- thực hiện sơ vật dụng khối để biểu lộ thuật toán. 


*

c) 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 tiến hành các thao tác.

- Tính xác định: sau thời điểm thực hiện tại 1 thao tác làm việc thì hay là thuật toán xong xuôi hoặc là gồm đúng 1 thao tác xác định để được triển khai tiếp theo.

- Tính đúng đắn: sau khi thuật toán kết thúc, ta phải nhận được Output đề nghị tìm.

3. Một trong những ví dụ về thuật toán

Ví dụ 1: khám nghiệm tính yếu tắc của 1 số ít nguyên dương

• Xác định bài toán

- Input: N là một số nguyên dương;

• Ý tưởng:

- Định nghĩa: ″Một số nguyên dương N là số nguyên tố nếu như nó chỉ có đúng hai ước là một trong những và N″

- giả dụ N = 1 thì N ko là số nguyên tố.

- trường hợp 1 1 của N.

+ trường hợp i chế tạo thuật toán

a) bí quyết liệt kê

- bước 1: Nhập số nguyên dương N;

- cách 2: giả dụ N=1 thì thông báo ″N ko là số nguyên tố″, kết thúc;

- cách 3: giả dụ Nb) Sơ trang bị khối


*

Lưu ý: Nếu N >= 4 và không có ước trong phạm vi trường đoản cú 2 mang lại phần nguyên căn bậc 2 của N thì N là số nguyên tố.

Ví dụ 2: Sắp xếp bằng cách tráo đổi

• xác minh bài toán

- Input: dãy A gồm N số nguyên a1, a2,…, an

- Output: hàng A được sắp xếp thành hàng không giảm.

• Ý tưởng

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

- việc này lặp lại nhiều lượt, từng lượt triển khai nhiều lần so sánh cho đến khi không có sự đổi chỗ nào xảy ra nữa.

• sản xuất thuật toán

a) giải pháp liệt kê

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

- cách 2: M ← N;

- bước 3: giả dụ M M thì tảo lại bước 3;

- cách 7: nếu ai > ai+1 thì tráo thay đổi ai cùng ai+1 đến nhau;

- bước 8: tảo lại bước 5;

b) Sơ trang bị khối


*

*

Ví dụ 3: Bài toán tra cứu kiếm

• khẳng định bài toán

- đầu vào : hàng A tất cả N số nguyên khác biệt a1, a2,…, an và một vài nguyên k (khóa)

ví dụ như : A gồm những số nguyên ″ 5 7 1 4 2 9 8 11 25 51″ và k = 2 (k = 6).

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

• Ý tưởng

Tìm kiếm tuần trường đoản cú được tiến hành một giải pháp tự nhiên: thứu tự đi từ số hạng sản phẩm công nghệ nhất, ta so sánh giá trị số hạng sẽ xét với khóa cho đến khi gặp một số hạng bằng khóa hoặc dãy đã làm được xét hết mà không tìm thấy giá trị của khóa bên trên dãy.

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

a) giải pháp liệt kê

- bước 1: Nhập N, những số hạng a1, a2,…, aN và giá trị khoá k;

- cách 2: i ← 1;

- bước 3: ví như ai = k thì thông tin chỉ số i, rồi kết thúc;

- cách 4: i ←i+1;

- cách 5: nếu i > N thì thông báo dãy A không tồn tại số hạng nào có giá trị bởi k, rồi kết thúc;

- bước 6: quay trở về bước 3;

b) Sơ thiết bị khối


*

Ví dụ 4: Tìm kiếm nhị phân

• Xác định bài toán

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

Ví dụ: hàng A gồm các số nguyên 2 4 5 6 9 21 22 30 31 33 với k = 21 (k = 25)

- output đầu ra : địa chỉ i mà ai = k hoặc thông báo không kiếm thấy k vào dãy. địa điểm của 21 trong dãy là 6 (không tra cứu thấy 25)

• Ý tưởng

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

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

- giả dụ agiữa > k thì việc đào bới tìm kiếm kiếm thu bé nhỏ chỉ xét từ adầu (phạm vi) → agiữa - 1;

- nếu agiữa cuối (phạm vi).

Xem thêm: Pst Là Gì ? Ý Nghĩa Của Từ Pst Pst Time Là Gì

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

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

a) bí quyết liệt kê

- bước 1: Nhập N, những số hạng a1, a2,…, aN và quý hiếm khoá k;

- cách 2: Đầu ←1; Cuối ←N;

- cách 3: Giữa←;

- bước 4: giả dụ agiữa = k thì thông tin chỉ số Giữa, rồi kết thúc;

- bước 5: ví như agiữa > k thì để Cuối = giữa - 1 rồi đưa sang cách 7;

- bước 6: Đầu ←Giữa + 1;

- cách 7: giả dụ Đầu > Cuối thì thông báo không tìm kiếm thấy khóa k trên dãy, rồi kết thúc;