Tin Học 10 Bài 4: Bài Toán Và Thuật Toán

     

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

- bài toán là 1 việc nào kia ta muốn máy tính xách tay thực hiện. Ví dụ: Giải phương trìnhbậc 2, quản lý nhân viên…

- các bài toán được cấu trúc bởi 2 nguyên tố cơ bản:

Input: các thông tin sẽ có. Output: những thông tin bắt buộc tìm từ Output.

2. Quan niệm thuật toán

- Thuật toán để giải một bài toán là một trong dãy hữu hạn các làm việc được bố trí theo 1 trình tự xác minh sao cho sau khoản thời gian thực hiện dãy thao tác ấy, từ đầu vào của bài xích toán, ta nhận ra Output yêu cầu tìm.

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

=> Ta bao gồm 3 bước tiến hành như sau:

*Xác định BT

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

Bạn đang xem: Tin học 10 bài 4: bài toán và thuật toán

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

*Ý tưởng

- Khởi chế tạo giá trị Max = a1.

- lần lượt vớii tự 2 mang đến Nso sánh aivới Max, nếu như ai>Max thì Max= ai.

*Thuật toán:

Cách liệt kê:

B1: Nhập N với dãy a1,...,aN;B2: Max(leftarrow)a1, i(leftarrow)2;B3: nếu i>N thì đưa 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ở về bước 3;

Cách lập sơ thiết bị khối:

- Thuật toán còn được diễn đạt bằng sơ vật dụng khối.

Xem thêm: Tâm Đường Tròn Ngoại Tiếp Tứ Giác, Please Wait

- Quy định:

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

*

Ví dụ: Mô bỏng 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 kết thúc sau một số trong những hữu hạn lần thực hiện các thao tác. Tính xác định: Sau một vài lần thực hiện thao tác, hoặc là chấm dứt hoặc xác định để thực hiện bước tiếp theo. Tính đúng đắn: Sau lúc thuật toán kết thúc, ta đề nghị nhận được Output nên tìm.

3. Một vài ví dụ về thuật toán

Ví dụ 1: đánh giá tính nhân tố của một vài nguyên dương.

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

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

- Ý tưởng: Ta ghi nhớ lại định nghĩa: một số nguyên dương N là số nguyên tố trường hợp nó có đúng 2 cầu số khác biệt là 1 và thiết yếu nó. Vì thế ta có:

Nếu N = 1 thì N ko là nguyên tố. Trường hợp 1 nếu như N (ge) 4 và không tồn tại ước số vào phạm vi tự 2 cho 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: giả dụ N = 1 thì thông báo N ko là số yếu tắc rồi kết thúc. B3: trường hợp N B4: i (leftarrow) 2B5: nếu như N><(sqrtN)>(*) thì thông tin N là số nguyên tố rồi kết thúc. B6: nếu N chia hết choi thì thông báo 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: việc sắp xếp

Cho hàng A tất cả N số nguyên a1, a2, a3, …,aN. Nên sắp xếp những số hạng để hàng A phát triển thành 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 minh bài toán:

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

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

- Ý tưởng: cùng với 2 số tức tốc kề, nếu số trước lớn hơn số sau ta thay đổi chổ mang đến nhau. Câu hỏi đó lặp lai, khi không còn sự thay đổi chổ làm sao nữa.

- Thuật toán

Cách liệt kê:

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

*

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

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

Thuật toán kiếm tìm kiếm tuần tự:

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

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

Xem thêm: 40 Món Quà Sinh Nhật Bất Ngờ, Tặng Quà Sinh Nhật Cho Vợ Yêu Ý Nghĩa Và Lãng Mạn

- Ý tưởng: thứu tự từ số hạng sản phẩm công nghệ nhất, ta đối chiếu giá trị số hạng đang xét với khoá cho đến khi hoặc chạm chán một số hạng bởi khoá hoặc dãy đã làm được xét không còn và không có giá trị nào bằng khoá. Trong trường hợp thứ 2 dãy A không tồn tại số hạng nào bởi khoá...

- Thuật toán

Liệt kê:

B1: Nhập vào N, các số hạng a1, . . . ,aNvà khóa k;B2: i(leftarrow)1;B3: giả dụ ai=k thì thông báo chỉ số i rồi kết thúc;B4. I(leftarrow)i+1;B5: nếu như i>N thì thông tin dãy A không tồn tại số hạng nào có mức giá trị bởi k rồi kết thúc;B6: quay lại bước 3;

*

Dãy A gồm N = 7 khóa k = 10

Tìm chỉ số i để 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à vươn lên là chỉ số cùng nhận quý giá nguyên lần lượt từ 1 đến N + 1