Câu hỏi:
Khi trình bày thuật toán ta cần trình bày rõ?
A. Mối quan hệ giữa Input và Output của bài toán đó.
B. Thuật toán để giải bài toán đó.
C. Input, Output của bài toán đó.
D. Input, Output và thuật toán để giải bài toán đó.
Đáp án đúng D.
Khi trình bày thuật toán ta cần trình bày rõ Input, Output và thuật toán để giải bài toán đó, thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 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.
Giải thích lý do chọn đáp án D:
Thuật toán là 1 dãy hữu hạn các thao tác được sắp xếp theo 1 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.
Có hai cách để biểu diễn thuật toán, đó là:
– Sử dụng cách liệt kê: nêu ra tuần tự các thao tác cần tiến hành
– Sử dụng sơ đồ khối để mô tả thuật toán.
Các tính chất của thuật toán là:
– 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.
Khi trình bày thuật toán ta cần trình bày rõ Input, Output và thuật toán để giải bài toán đó.a
Ví dụ: Sắp xếp bằng cách tráo đổi
– 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 > 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 theo 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.
