VÍ DỤ VỀ BÀI TOÁN TRONG TIN HỌC

     

Thuật toán là một 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 tại dãy làm việc ấy, từ đầu vào của bài xích toán, ta nhận ra Output nên tìm.

Bạn đang xem: Ví dụ về bài toán trong tin học

Bạn đã xem: một vài ví dụ về thuật toán

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

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

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

+ Input: Thông tin vẫn biết, thông tin đưa vào thiết bị tính.

+ Output: Thông tin cần tìm, thông tin kéo ra từ lắp thêm tính.

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

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

+ Output: mong chung lớn nhất của A cùng B

2. Quan niệm 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 làm việc được sắp xếp theo 1 trình tự xác định sao cho sau khoản thời gian thực hiện nay dãy thao tác ấy, từ input của bài toán, ta nhận được Output cần tìm.

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

- sử dụng cách liệt kê: nêu ra tuần từ bỏ các thao tác làm việc cần tiến hành.

- thực hiện sơ thiết bị khối để biểu đạt thuật toán. 


*

c) 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ố hữu hạn lần tiến hành các thao tác.

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

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

Xem thêm: 4 Điều Cần Nhớ Trong Học Tập Tốt Ở Trường, Kỹ Năng Học Tập Hiệu Quả

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

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

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

- Input: N là một trong những nguyên dương;

• Ý tưởng:

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

- ví như N = 1 thì N ko là số nguyên tố.

- nếu 1 1 của N.

+ giả dụ i chế tạo thuật toán

a) cách liệt kê

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

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

- cách 3: trường hợp Nb) Sơ thứ khối


*

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

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

- Input: dãy A có 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 kề trong dãy, nếu số trước to hơn số sau ta đổi vị trí chúng mang lại nhau. (Các số lớn sẽ được đẩy dần dần về vị trí khẳng định cuối dãy).

- bài toá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 có sự đổi chỗ nào xảy ra nữa.

• xây đắp 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;

- cách 2: M ← N;

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

- cách 7: ví như ai > ai+1 thì tráo thay đổi ai và ai+1 mang đến nhau;

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

b) Sơ thứ khối


*

*

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

• xác minh bài toán

- input : dãy A bao gồm N số nguyên khác biệt a1, a2,…, an và một số 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ới k = 2 (k = 6).

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

• Ý tưởng

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

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

a) cách liệt kê

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

- cách 2: i ← 1;

- cách 3: trường hợp ai = k thì thông tin chỉ số i, rồi kết thúc;

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

- bước 5: ví như 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 lại bước 3;

b) Sơ thứ khối


*

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

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

- Input: dãy A là dãy tăng tất cả N số nguyên khác nhau a1, a2,…, an và một trong những nguyên k.

Xem thêm: Máy Lọc Nước Sơn Hà 10 Lõi Có Vỏ Tủ, Máy Ro Sơn Hà Smart In 3D Màu Đen 10 Lõi Lọc

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

• Ý tưởng

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

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

- trường hợp agiữa > k thì việc tìm và đào bới kiếm thu thuôn chỉ xét từ adầu (phạm vi) → agiữa - 1;

Quá trình trên được lặp lại cho đến 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) giải pháp liệt kê

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

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

- bước 3: Giữa←;

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

- cách 5: nếu như agiữa > k thì đặt Cuối = giữa - 1 rồi chuyển sang cách 7;

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

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