HAI CÁCH ĐỂ MÔ TẢ THUẬT TOÁN LÀ

     

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

Bạn đang xem: Hai cách để mô tả thuật toán là


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

- Bài toán là một việc nào đó mà con tín đồ muốn máy tính thực hiện.

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

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

+ Output: Thông tin cần tìm, thông tin lấy ra từ thứ tính.

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

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

+ Output: ước chung lớn nhất của A với 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ự xác định sao cho sau khi thực hiện nay dãy thao tác ấy, từ input của bài toán, ta cảm nhận Output bắt buộc tìm.

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

- áp dụng cách liệt kê: nêu ra tuần trường đoản cú các thao tác cần tiến hành.

- sử dụng sơ vật khối để biểu hiện 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 xong 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 khoản thời gian thực hiện nay 1 thao tác làm việc thì hay là thuật toán hoàn thành hoặc là tất cả đúng 1 thao tác xác minh để được tiến hành tiếp theo.

- Tính đúng đắn: sau thời điểm thuật toán kết thúc, ta đề xuất nhận được Output nên tìm.

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

Ví dụ 1: soát sổ tính nhân tố của 1 số ít nguyên dương

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

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

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

Xem thêm: What Are Your Plans For The Future, Professionally And Personally? ?

• Ý tưởng:

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

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

- nếu như 1 1 của N.

+ nếu như i xuất bản thuật toán


a) cách liệt kê

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

- bước 2: trường hợp N=1 thì thông tin ″N không là số nguyên tố″, kết thúc;

- cách 3: nếu như Nb) Sơ vật dụng khối

*

Lưu ý: Nếu N >= 4 và không tồn tại ướ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 gồm N số nguyên a1, a2,…, an

- Output: dãy A được bố trí thành dãy không giảm.

• Ý tưởng

- Với từng cặp số hạng đứng liền kề trong dãy, nếu như số trước to hơn số sau ta đổi nơi chúng mang lại nhau. (Các số lớn sẽ tiến hành đẩy dần dần về vị trí xác minh cuối dãy).


- vấn đề này tái diễn nhiều lượt, từng lượt tiến hành nhiều lần so sánh cho đến khi không tồn tại sự đổi nơi nào xảy ra nữa.

• kiến tạo thuật toán

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

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

- bước 2: M ← N;

- cách 3: trường hợp M M thì tảo lại bước 3;

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

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

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

*

*

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

• xác minh bài toán

- input : dãy A gồm N số nguyên khác biệt a1, a2,…, an và một số trong những nguyên k (khóa)

ví dụ như : 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 chỉ i mà lại ai = k hoặc thông báo không tìm kiếm thấy k vào dãy. địa chỉ 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 trường đoản cú được thực hiện một cách tự nhiên: theo lần lượt đi trường đoản cú số hạng đồ vật nhất, ta so sánh giá trị số hạng sẽ xét cùng với khóa cho đến khi gặp mặt một số hạng bởi khóa hoặc dãy đã làm được xét không còn mà không tìm kiếm thấy cực hiếm của khóa 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, các số hạng a1, a2,…, aN và quý giá khoá k;

- bước 2: i ← 1;

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

- bước 4: i ←i+1;

- cách 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ở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 xích toán

- Input: hàng A là dãy 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 đầu ra : địa điểm i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 (không tìm kiếm thấy 25)


• Ý tưởng

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

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

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

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

Xem thêm: Lý Thuyết Điện Trường Đều Là Điện Trường Có, Điện Trường Đều Là Gì

Quá trình bên 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 kiếm tìm kiếm bằng rỗng.

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

a) cách liệt kê

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

- bước 2: Đầu ←1; Cuối ←N;

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

- cách 4: ví như agiữa = k thì thông tin chỉ số Giữa, rồi kết thúc;

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

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

- cách 7: nếu như Đầ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;