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

- bài toán là 1 trong việc nào đó ta muốn laptop thực hiện. Ví dụ: Giải phương trìnhbậc 2, thống trị nhân viên…

- những bài toán được kết cấu bởi 2 nhân tố cơ bản:

Input: các thông tin đang có. Output: những thông tin phải tìm từ bỏ Output.

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

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

- Ví dụ: Tìm giá bán trị lớn số 1 của 1 hàng số nguyên.

=> Ta có 3 bước thực hiện như sau:

*Xác định BT

- Input: Số nguyên dương N cùng dãy N số nguyên a1, a2, …, aN.

Bạn đang xem: Một số bài tập về thuật toán lớp 10

Bạn đang xem: một vài bài tập về thuật toán lớp 10

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

*Ý tưởng

- Khởi sản xuất giá trị Max = a1.

- theo thứ tự vớii trường đoản cú 2 mang đến Nso sánh aivới Max, giả dụ ai>Max thì Max= ai.

*Thuật toán:

Cách liệt kê:

B1: Nhập N và dãy a1,...,aN;B2: Max(leftarrow)a1, i(leftarrow)2;B3: ví như i>N thì gửi giá trị Max rồi kết thúc;B4: trường hợp ai>Max thì Max (leftarrow)ai;B5: i (leftarrow)i+1 rồi trở lại bước 3;

Cách lập sơ thứ khối:

- Quy định:

Hình ô van: các làm việc nhập, xuất dữ liệu.Hình thoi: thao tác so sánh.Hình chữ nhật: các phép toán.Mũi tên: trình tự triển khai các thao tác.


*

Ví dụ: Mô rộp việc tiến hành thuật toán với N=8 cùng dãy số: 5, 1, 4, 7, 6, 3, 15, 11

Ds

5

1

4

7

6

3

15

11

i

2

3

4

5

6

7

8

9

Max

5

5

5

7

7

7

15

15

=> Các đặc thù của thuật toán:

Tính dừng: Thuật toán phải hoàn thành sau một số trong những hữu hạn lần tiến hành các thao tác. Tính xác định: Sau một số lần triển khai thao tác, hoặc là chấm dứt hoặc xác minh để triển khai bước tiếp theo. Tính đúng đắn: Sau khi thuật toán kết thúc, ta đề xuất nhận được Output nên tìm.

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

Ví dụ 1: kiểm tra tính nhân tố của một số trong những nguyên dương.

- xác minh bài toán:

Input: Số nguyên dương N.Output: “N là số nguyên tố” hoặc “N ko là số nguyên tố”.

- Ý tưởng: Ta lưu giữ lại định nghĩa: một số trong những nguyên dương N là số nguyên tố nếu như nó tất cả đúng 2 ước số khác nhau là 1 và thiết yếu nó. Cho nên ta có:

Nếu N = 1 thì N ko là nguyên tố. Ví như 1 trường hợp N (ge) 4 và không có ước số vào 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ố.

- Thuật toán:

B1: Nhập số nguyên dương N. B2: ví như N = 1 thì thông báo N ko là số thành phần rồi kết thúc. B3: nếu N B4: i (leftarrow) 2B5: giả dụ N>(*) thì thông tin N là số yếu tố rồi kết thúc. B6: ví như N chia hết choi thì thông tin N là số ko nguyên tố rồi kết thúc. B7: i (leftarrow) i + 1 rồi trở lại bước 5.

Ví dụ 2: vấn đề sắp xếp

Cho dãy A có N số nguyên a1, a2, a3, …,aN. Nên sắp xếp những số hạng để dãy A trở nên dãy không bớt (tức là số hạng trước không to hơn số hạng sau)

- xác định bài toán:

Input: dãy A bao gồm N số nguyênOutput: dãy A được sắp xếp thành dãy không giảm.

Thuật toán sắp xếp bằng tráo đổi(Exchange Sort)

- Ý tưởng: với 2 số ngay lập tức kề, giả dụ số trước to hơn số sau ta đổi chổ mang lại nhau. Câu hỏi đó lặp lai, khi không hề sự đổi chổ như thế nào nữa.

- Thuật toán

Cách liệt kê:

B1: Nhập vào n cùng dãy số nguyên a1, . . . ,aN;B2: M (leftarrow)N;B3: giả dụ MB4. M(leftarrow)M – 1; i(leftarrow)0;B5: i (leftarrow)i + 1;B6: nếu i > M thì quay trở về bước 3;B7. Nếu như ai> ai+1thì tráo đổi cho nhau;B8: trở lại bước 5;


*

Ví dụ 3: Bài toán tìm kiếm kiếm

Cho dãy A gồm N số nguyên khác nhau: a1…aN.và một vài nguyên k. Cần biết có hay không chỉ số i nhưng mà ai=k. Nếu tất cả hãy cho biết thêm chỉ số đó.

Thuật toán tra cứu kiếm tuần tự:

- xác định bài toán

Input: hàng A có N số nguyên không giống nhau: a1…aNvà số nguyên k.Output: chỉ số i nhưng mà ai=k hoặc thông báo không tồn tại số hạng như thế nào của hàng A có giá trị là k.

Xem thêm: Tìm Hiểu Về Clustered Index Là Gì ? Sự Khác Biệt Giữa Cluster Và Non Cluster Index

- Ý tưởng: theo lần lượt từ số hạng vật dụng nhất, ta đối chiếu giá trị số hạng đang xét với khoá cho tới khi hoặc gặp một số hạng bởi khoá hoặc dãy đã được xét không còn và không tồn tại giá trị nào bởi khoá. Trong trường hợp thứ hai dãy A không có số hạng nào bởi khoá...

- Thuật toán

Liệt kê:

B1: Nhập vào N, những số hạng a1, . . . ,aNvà khóa k;B2: i(leftarrow)1;B3: nếu ai=k thì thông báo chỉ số i rồi kết thúc;B4. I(leftarrow)i+1;B5: trường hợp 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;B6: quay lại bước 3;


*

Dãy A tất cả N = 7 khóa k = 10

Tìm chỉ số i nhằm ai = k.

i

1

2

3

4

5

6

7

ai

7

12

4

6

11

10

8

Ghi chú: k = 10 → i = 6

Trong thuật toán trên, i là biến hóa chỉ số cùng nhận quý giá nguyên lần lượt từ là một đến N + 1