Câu hỏi: “…(1) là một dãy hữu hạn các …(2) được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy các thao tác ấy, từ …(3) của bài toán, ta nhận được …(4) cần tìm”. Các cụm từ còn thiếu lần lượt là?

A. Input – Output – Thuật toán – Thao tác

B. Thuật toán – Thao tác – Input – Output

C. Thuật toán – Thao tác – Output – Input

D. Thao tác – Thuật toán– Input – Output

Trả lời:

Đáp án đúng: C. Thuật toán – Thao tác – Output – Input

*Giải thích:

– Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho khi thực hiện dãy các thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

Hãy để Top tài liệu cung cấp thêm cho các bạn kiến thức về thuật toán để hiểu rõ hơn về câu hỏi trên nhé.

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

– Trong phạm vi Tin học, bài toán là việc nào đó ỉmuon máy tính thực hiện. Nhận xét: Ta không nên hiểu máy móc bài toán dưới dạng toán học, mà ta quan niệm bài toán ở đây là cung cấp cho máy thông tin đầu vào (Input) và yêu cầu thông tin đầu ra (Output).

*Ví dụ

+ Tìm USCLN của 2 số nguyên dương

+ Tìm số lớn nhất trong 3 số nguyên dương a,b,c

+ Tìm nghiệm của phương trình bậc nhất: ax + b = 0 (a≠0)

+ …

1 là một dãy hữu hạn các 2 được sắp xếp theo một trình tự xác định sao cho khi thực hiện

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

– Thuật toán là một dãy hữu hạn các thao tác được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác ấy, từ Input của bài toán, ta nhận được Output cần tìm.

– Nhận xét: Để đơn giản, ta hiểu thuật toán là các bước tìm Output dựa vào Input với sự thực hiện của máy tính điện tử.

Các tính chất 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 thao tác.

– Tính xác định: Sau khi thực hiện một thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng một thao tác xác định để được thực hiện tiếp theo.

– Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

Ví dụ: Cho bài toán Tìm nghiệm của phương trình bậc 2: ax2 + bx + c = 0 (a≠0)?

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

+ Input: Các số thực a, b, c

+ Output: Các số thực x thỏa mãn ax2 + bx + c = 0 (a≠0)

– Thuật toán

1 là một dãy hữu hạn các 2 được sắp xếp theo một trình tự xác định sao cho khi thực hiện (ảnh 2)

3. Các cách mô tả thuật toán

– Mô tả thuật toán theo tuần tự: liệt kê lần lượt từng bước tìm Output.

– Mô tả thuật toán theo sơ đồ khối: Dùng các kí hiệu để biểu diễn các thao tác:

1 là một dãy hữu hạn các 2 được sắp xếp theo một trình tự xác định sao cho khi thực hiện (ảnh 3)

Yêu cầu: Mô tả các thuật toán tìm giá trị lớn nhất của các dãy số, sắp xếp dãy sô, tìm kiếm một giá trị cho trước trong một dãy số.

* Các tính chất của thuật toán

– Tính dừng: Thuật toán phải kết thúc sau 1 số hữu hạn lần thực hiện các thao tác.

– Tính xác định: Sau khi thực hiện 1 thao tác thì hoặc là thuật toán kết thúc hoặc là có đúng 1 thao tác xác định để được thực hiện tiếp theo.

– Tính đúng đắn: Sau khi thuật toán kết thúc, ta phải nhận được Output cần tìm.

4. Ví dụ minh họa

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

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

– Việc này lặp lại nhiều lượt, mỗi lượt tiến hành nhiều lần so sánh cho đến khi không có sự đổi chỗ nào 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 < 2 thì đưa ra dãy A đã được sắp xếp, rồi kết thúc;

– Bước 4: M ← M – 1, i ← 0;

– Bước 5: i ← i + 1;

– Bước 6: Nếu i > M thì quay lại bước 3;

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

– Bước 8: Quay lại bước 5;

Mô phỏng ví dụ:

1 là một dãy hữu hạn các 2 được sắp xếp theo một trình tự xác định sao cho khi thực hiện (ảnh 4)

b) Sơ đồ khối

1 là một dãy hữu hạn các 2 được sắp xếp theo một trình tự xác định sao cho khi thực hiện (ảnh 5)

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *