Lý thuyết: bài toán và thuật toán tin học lớp 10 là gì ? a tin học 10 bài 4: bài toán và thuật toán

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ự khẳng định sao cho sau khoản thời gian thực hiện dãy thao tác làm việc ấy, từ input của bài toán, ta cảm nhận Output buộc phải tìm.
Bạn đang xem: Thuật toán tin học lớp 10 là gì

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

- Bài toán là một bài toán nào đó mà con fan muốn laptop thực hiện.

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

+ Input: Thông tin đang biết, tin tức đưa vào sản phẩm công nghệ tính.

+ Output: Thông tin đề nghị tìm, thông tin mang ra từ thiết bị tính.

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

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

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

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

a) Khái niệm

Thuật 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ự khẳng định sao cho sau khoản thời gian thực hiện tại dãy làm việc ấy, từ đầu vào của bài bác toán, ta cảm nhận Output buộc phải 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 trường đoản cú các thao tác làm việc cần tiến hành.

- sử dụng sơ đồ dùng khối để mô tả thuật toán.

c) Các đặc điểm của thuật toán

- Tính dừng: thuật toán phải hoàn thành sau 1 số ít hữu hạn lần thực hiện các thao tác.

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

- Tính đúng đắn: sau khi thuật toán kết thúc, ta cần nhận được Output yêu cầu tìm.

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

Ví dụ 1: bình chọn tính yếu tắc của một số ít nguyên dương

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

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

- Output: ″N là số nguyên tố″ hoặc ″N không là số nguyên tố″.

• Ý tưởng:

- Định nghĩa: ″Một số nguyên dương N là số nguyên tố trường hợp nó chỉ có đúng nhì ước là 1 trong những và N″

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

Xem thêm: Bố cục nghị luận văn học đúng trọng tâm, cách làm nghị luận văn học đúng trọng tâm

- ví như 1 1 của N.

+ nếu như i tạo thuật toán

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

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

- cách 2: nếu như N=1 thì thông tin ″N ko là số nguyên tố″, kết thúc;

- cách 3: nếu Nb) Sơ đồ vật khối

Lưu ý: Nếu N >= 4 và không có ước vào phạm vi tự 2 mang đến 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 phương pháp tráo đổi

• xác minh bài toán

- Input: hàng A bao gồm N số nguyên a1, a2,…, an

- 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 gần cạnh trong dãy, trường hợp số trước lớn hơn số sau ta đổi khu vực chúng đến nhau. (Các số lớn sẽ tiến hành đẩy dần dần về vị trí khẳng định cuối dãy).

- vấn đề này lặp lại nhiều lượt, từng lượt thực hiện nhiều lần so sánh cho tới khi không tồn tại sự đổi nơi nào xảy ra nữa.

• thi công thuật toán

a) phương pháp liệt kê

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

- cách 2: M ← N;

- cách 3: nếu như M M thì quay lại bước 3;

- bước 7: trường hợp ai > ai+1 thì tráo thay đổi ai cùng ai+1 đến nhau;

- bước 8: xoay lại bước 5;

b) Sơ thứ khối

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

• xác minh bài toán

- input : hàng A bao gồm N số nguyên không giống nhau a1, a2,…, an và một số trong những nguyên k (khóa)

lấy một ví dụ : A gồm các 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 thấy k vào dãy. địa điểm của 2 trong hàng là 5 (không tìm kiếm thấy 6)

• Ý tưởng

Tìm tìm tuần tự được tiến hành một cách tự nhiên: lần lượt đi từ số hạng vật dụng nhất, ta đối chiếu giá trị số hạng đang xét cùng với khóa cho tới khi gặp một số hạng bởi khóa hoặc dãy đã có xét không còn mà không tìm kiếm thấy quý hiếm của khóa trên dãy.

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

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

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

- cách 2: i ← 1;

- bước 3: nếu ai = k thì thông báo chỉ số i, rồi kết thúc;

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

- bước 5: giả dụ 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ằng k, rồi kết thúc;

- bước 6: quay lại bước 3;

b) Sơ đồ vật khối

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

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

- Input: dãy A là hàng tăng bao gồm N số nguyên khác nhau a1, a2,…, an và một trong những 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 cùng k = 21 (k = 25)

- output : địa điểm i nhưng ai = k hoặc thông báo không tìm thấy k trong dãy. địa chỉ của 21 trong dãy là 6 (không search thấy 25)

• Ý tưởng

Sử dụng đặc thù dãy A đã sắp xếp tăng, ta tìm biện pháp thu nhỏ bé nhanh vùng tìm kiếm kiếm bằng phương pháp so sánh k cùng với số hạng trọng điểm phạm vi tìm kiếm kiếm (agiữa), lúc ấy chỉ xảy ra một trong ba ngôi trường hợp:

- trường hợp agiữa= k thì tìm được chỉ số, kết thúc;

- nếu agiữa > k thì việc tìm kiếm kiếm thu nhỏ bé chỉ xét từ bỏ adầu (phạm vi) → agiữa - 1;

- ví như agiữa cuối (phạm vi).

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

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

a) phương pháp liệt kê

- cách 1: Nhập N, những số hạng a1, a2,…, a
N và quý giá khoá k;

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

- bước 3: Giữa←<(Đầu+Cuối)/2>;

- bước 4: trường hợp agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

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

- cách 6: Đầu ←Giữa + 1;

- bước 7: trường hợp Đầu > Cuối thì thông báo không kiếm thấy khóa k bên trên dãy, rồi kết thúc;

Một bài bác toán có thể được màn biểu diễn bởi nhiều thuật toán, việc lựa chọn thuật toán đam mê hợp sẽ giúp cho quy trình viết chương trình đơn giản hơn và máy tính xách tay thực hiện với thời hạn nhanh hơn. Do vậy, có cha tiêu chuẩn chỉnh cơ bản lựa chọn thuật toán kia là:

- Thuật toán tất cả độ phức tạp thời gian nhỏ tuổi nhất (thực hiện lịch trình trong thời gian ngắn nhất);

- con số ô nhớ thực hiện ít nhất;

- Viết chương trình đến thuật toán dễ dàng hiểu, dễ dàng và đơn giản nhất.

timluanvan.com