Bài toán và thuật toán trong tin học

Thuật toán là 1 hàng hữu hạn những thao tác được sắp xếp theo một trình tự xác minh làm thế nào cho sau thời điểm thực hiện hàng thao tác ấy, tự Input của bài xích tân oán, ta cảm nhận Output đầu ra phải tra cứu.

You watching: Bài toán và thuật toán trong tin học


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

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

- Các nguyên tố của một bài toán:

+ Input: tin tức sẽ biết, ban bố chuyển vào máy tính.

+ Output: tin tức buộc phải tra cứu, biết tin lôi ra từ bỏ máy tính.

- Ví dụ: Bài toán search ước thông thường lớn số 1 của 2 số nguyên dương, lúc đó:

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

+ Output: ước thông thường lớn nhất 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à 1 trong những dãy hữu hạn những thao tác làm việc được bố trí theo 1 trình từ bỏ khẳng định sao cho sau khoản thời gian thực hiện hàng thao tác ấy, từ bỏ Input của bài xích toán thù, ta nhận ra Output đầu ra phải kiếm tìm.

b) Biểu diễn thuật toán

- Sử dụng phương pháp liệt kê: nêu ra tuần từ những thao tác bắt buộc tiến hành.

- Sử dụng sơ trang bị khối nhằm thể hiện thuật toán. 

*

c) Các đặc thù của thuật toán

- Tính dừng: thuật tân oán phải hoàn thành sau một số ít hữu hạn lần tiến hành các làm việc.

- Tính xác định: sau khoản thời gian tiến hành 1 thao tác làm việc thì hay là thuật tân oán chấm dứt hay là bao gồm đúng 1 thao tác xác minh và để được thực hiện tiếp theo.

- Tính đúng đắn: sau khi thuật toán thù xong, ta cần nhận ra Output đầu ra nên kiếm tìm.

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

lấy ví dụ 1: Kiểm tra tính nguyên ổn tố của một số ít nguyên dương

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

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

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

See more: Vua Hải Tặc Tập 895 - Vua Hải Tặc: Lễ Hội Hải Tặc

• Ý tưởng:

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

- Nếu N = 1 thì N không là số ngulặng tố.

- Nếu 1 1 của N.

+ Nếu i Xây dựng thuật toán


a) Cách liệt kê

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

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

- Bước 3: Nếu Nb) Sơ đồ vật khối

*

Lưu ý: Nếu N >= 4 với không có ước vào phạm vi từ 2 cho phần nguyên ổn căn bậc 2 của N thì N là số nguyên ổn tố.

Ví dụ 2: Sắp xếp bằng phương pháp tráo đổi

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

- Input: Dãy A gồm N số nguyên a1, a2,…, an

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

• Ý tưởng

- Với mỗi cặp số hạng đứng ngay cạnh trong dãy, nếu như số trước lớn hơn số sau ta thay đổi nơi bọn chúng cho nhau. (Các số lớn sẽ tiến hành đẩy dần dần về địa điểm xác định cuối dãy).


- Việc này tái diễn nhiều lượt, mỗi lượt tiến hành các lần so sánh cho đến Khi không tồn tại sự đổi ở đâu xẩy ra nữa.

• 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;

- Bước 2: M ← N;

- Bước 3: Nếu M M thì xoay lại bước 3;

- Bước 7: Nếu ai > ai+1 thì tráo thay đổi ai với ai+1 đến nhau;

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

b) Sơ đồ khối

*

*

ví dụ như 3: Bài toán thù tra cứu kiếm

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

- Input : Dãy A gồm N số nguyên khác biệt a1, a2,…, an với một vài ngulặng k (khóa)

ví dụ như : A tất cả các số nguim ″ 5 7 1 4 2 9 8 11 25 51″ cùng k = 2 (k = 6).

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


• Ý tưởng

Tìm kiếm tuần trường đoản cú được tiến hành một biện pháp từ nhiên: Lần lượt đi từ bỏ số hạng trước tiên, ta đối chiếu cực hiếm số hạng vẫn xét với khóa cho tới Khi chạm mặt một trong những hạng bởi khóa hoặc dãy đã làm được xét không còn nhưng không tìm thấy giá trị 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, những số hạng a1, a2,…, aN cùng quý giá khoá k;

- Cách 2: i ← 1;

- Cách 3: Nếu 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: Nếu i > N thì thông báo hàng A không tồn tại số hạng như thế nào có giá trị bằng k, rồi kết thúc;

- Cách 6: Quay lại bước 3;

b) Sơ đồ dùng khối

*

*

lấy một 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 biệt a1, a2,…, an và một số trong những nguyên k.

Ví dụ: Dãy A có các số nguyên 2 4 5 6 9 21 22 30 31 33 và k = 21 (k = 25)

- đầu ra : Vị trí i mà ai = k hoặc thông báo không tìm kiếm thấy k trong hàng. Vị trí của 2một trong những dãy là 6 (không kiếm thấy 25)


• Ý tưởng

Sử dụng tính chất hàng A sẽ sắp xếp tăng, ta kiếm tìm phương pháp thu eo hẹp nkhô nóng vùng search tìm bằng cách đối chiếu k với số hạng ở giữa phạm vi tra cứu kiếm (agiữa), khi đó chỉ xẩy ra một trong tía ngôi trường hợp:

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

- Nếu agiữa > k thì việc tìm và đào bới kiếm thu không lớn chỉ xét tự adầu (phạm vi) → agiữa - 1;

- Nếu agiữa cuối (phạm vi).

See more: Agribank Là Ngân Hàng Thương Mại Nhà Nước Hay Cổ Phần, Agribank Có Tốt Không

Quá trình trên được lặp lại cho đến Khi tra cứu thấy khóa k trên hàng A hoặc phạm vi tìm kiếm kiếm bởi trống rỗng.

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

a) Cách liệt kê

- Cách 1: Nhập N, các số hạng a1, a2,…, aN 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: Nếu agiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

- Cách 5: Nếu agiữa > k thì đặt Cuối = Giữa - 1 rồi đưa quý phái bước 7;

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

- Cách 7: Nếu Đầu > Cuối thì thông tin không kiếm thấy khóa k trên hàng, rồi kết thúc;