Thực hiện thiết kế thuật toán và chương trình bằng phương pháp làm mịn dần theo các bài toán sau. Trao đổi, thảo luận với bạn bè để thiết lập được lời giải tốt hơn.
Thực hiện các bước thiết kế giải bài toán trên theo phương pháp làm mịn dần, trao đổi và thảo luận để biết được cách thiết kế chương trình theo mô đun.
Phương pháp thiết kế chương trình theo mô đun sẽ tách bài toán lớn thành các bài toán nhỏ hơn, hay thành các mô đun, tương đối độc lập với nhau, sau đó tiến hành thiết kế thuật toán và chương trình cho từng mô đun con. Mỗi mô đun có thể là một số hàm hoặc thủ tục độc lập. Chương trình chính là một bản ghép nối các hàm và thủ tục con.
Cùng trao đổi, thảo luận các bước thiết kế chương trình theo thuật toán sắp xếp chèn, từ đó đưa ra phương pháp chính khi thiết kế chương trình. Sau mỗi bước thiết kế cần trao đổi và trả lời các câu hỏi sau:
1. Bước này đã thực hiện được công việc gì?
2. Kết quả vừa thực hiện với kết quả của bước trước đó khác nhau như thế nào?
Tham khảo:
Xác định cách thức sắp xếp chèn: Sắp xếp chèn là một thuật toán đơn giản, trong đó từng phần tử của dãy đang xét được chèn vào vị trí đúng của dãy con đã được sắp xếp trước đó. Bước này định nghĩa cách thức sắp xếp chèn, bao gồm quá trình so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng.
1. Bước này đã định nghĩa cách thức sắp xếp chèn, bao gồm cách thức so sánh và di chuyển các phần tử để đưa phần tử mới vào vị trí đúng của dãy con đã được sắp xếp trước đó.
2. Kết quả của bước này khác với kết quả của bước trước đó về cách thức sắp xếp chèn được định nghĩa và thực hiện. Bước này tập trung vào việc định nghĩa và triển khai thuật toán sắp xếp chèn cụ thể, trong khi bước trước đó có thể là các bước chuẩn bị dữ liệu, định nghĩa bài toán, hoặc thiết kế các thuật toán phụ trợ khác.
Trong các bài trước em đã học cách thiết kế thuật toán cho một số bài toán như bài toán tìm kiếm, bài toán sắp xếp và thiết lập chương trình thực hiện thuật toán đó. Một bài toán có nhiều thuật toán khác nhau và do đó có thể có nhiều chương trình khác nhau cùng giải quyết một bài toán. Hãy thảo luận và trả lời các câu hỏi sau:
Làm thế nào để biết trong các thuật toán giải cùng một bài toán thì thuật toán nào là tốt nhất?
Có những tiêu chí nào để đánh giá tính “tối ưu” của một thuật toán?
THAM KHẢO!
Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.
Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, giải bài toán trên máy tính thường được tiến hành qua 5 bước xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh và viết tài liệu.
Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thuật toán) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu.
Thuật toán tối ưu là sử dụng ít thời gian, ít bộ nhớ, ít phép toán, giải bài toán trên máy tính thường được tiến hành qua 5 bước xác định bài toán, lựa chọn hoặc thiết kế thuật toán, viết chương trình, hiệu chỉnh và viết tài liệu.
Để giải bài toán trên máy tính, người ta thực hiện thực hiện các công việc sau
a). Lựa chọn hoặc thiết kế thuật toán
b) Xác định bài toán c) Viết tài liệu
d) Viết chương trình e) Hiệu chỉnh
Hy chọn cách sắp xếp đúng nhất về thứ tự thực hiện các công việc nêu trên
A. b →a →d →c →e
B. b →a →d →e →c
C. a →b →d →e
D. d →a →b →e →c
Em đã biết thiết kế một số thuật toán và chương trình: tìm kiếm tuần tự, tìm kiếm nhị phân, sắp xếp chèn, sắp xếp chọn, sắp xếp nổi bọt. Tất cả các thiết kế chương trình đó có điểm nào chung?
Theo em, để thiết kế một thuật toán đúng giải một bái toàn cho trước cần trải qua các bước như thế nào? Nêu quan điểm của riêng em và trao đổi với các bạn.
- Các thuật toán và chương trình mà em đã biết đều là các thuật toán cơ bản trong lập trình và giải quyết các vấn đề thông thường. Các điểm chung của chúng bao gồm: Tính đơn giản, độ phức tạp thấp.
- Theo em, để thiết kế một thuật toán đúng giải một bái toàn cho trước cần trải qua các bước:
1. Xác định bài toán
2. Tìm cấu trúc dữ liệu biểu diễn thuật toán.
3. Tìm Thuật Toán.
4. Lập Trình (Programming)
5. Kiểm thử chương trình (Testing program)
6. Tối ưu chương trình (optimization program)
Cho dãy số A = A[0], A[1]. .... A[n — 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phân tử nào trùng nhau hay không. Cần đưa ra câu trả lời là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.
Bước 1: Xác định đầu vào và đầu ra của chương trình.
Đầu vào: Dãy số A gồm n phần tử (A[0], A[1], ..., A[n-1]).
Đầu ra: Một câu trả lời là "có" nếu trong dãy A có hai phần tử trùng nhau, hoặc "không" nếu không có.
Bước 2: Xác định giải thuật kiểm tra trùng nhau.
Giải thuật đơn giản nhất là duyệt qua từng phần tử của dãy A, so sánh nó với các phần tử trước đó trong dãy để tìm kiếm phần tử trùng nhau.
Bước 3: Thiết kế mã nguồn chương trình.
Sử dụng một vòng lặp for để duyệt qua từng phần tử của dãy A từ đầu đến cuối.
Trong mỗi lần lặp, so sánh phần tử hiện tại (A[i]) với các phần tử trước đó (A[0], A[1], ..., A[i-1]) để kiểm tra xem có phần tử trùng nhau hay không.
Nếu tìm thấy phần tử trùng nhau, đưa ra kết quả là "có" và kết thúc chương trình.
Nếu không tìm thấy phần tử trùng nhau sau khi đã duyệt qua toàn bộ dãy A, đưa ra kết quả là "không".
def check_duplicate(A):
for i in range(len(A)):
for j in range(i + 1, len(A)):
if A[i] == A[j]:
return "có"
return "không"
# Đầu vào: Dãy số A
A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Gọi hàm để kiểm tra
result = check_duplicate(A)
# Đầu ra: Kết quả kiểm tra
print(result)
Quá trình giải bài toán trên máy tính gồm các bước nào? *
Xác định bài toán, xây dựng thuật toán, viết chương trình.
Xác định giả thiết kết luận của bài toán, tìm lời giải.
Tìm hiểu bài toán, xây dựng thuật toán, viết chương trình.
Xây dựng thuật toán, xác định bài toán, viết chương trình.
tìm hiểu bài,xây dựng thuật toán,viết chương chình
Quan sát cách thực hiện thuật toán tìm kiếm tuần tự trên ví dụ cụ thể sau. Hãy trao đổi thảo luận để hiểu và mô tả được thuật toán trong trường hợp tổng quát.
Thuật toán tìm kiếm tuần tự: Duyệt lần lượt các phần tử của dãy để tìm phần tử có giá trị bằng K. Nếu tìm thấy, trả về chỉ số của phản tử bằng K; Ngược lại, thông báo không tìm thây và trả về giá trị -1. Thuật toán có thê duyệt từ đâu dãy hoặc từ cuối dãy.
Phát biểu nào sau đây là sai?
A.Với mọi bài toán ta có thể viết được ngay chương trình mà không nhất thiết phải thực hiện theo ba bước: Xác định thuật toán; Mô tả thuật toán; Viết chương trình.
B.Trong tin học ta có thể hiểu bài toán là một công việc hay một nhiệm vụ nào đó mà ta muốn máy tính thực hiện.
C.Xác định bài toán là chỉ rõ các điều kiện cho trước và kết quả cần thu được.
D.Một dãy hữu hạn các thao tác nếu thực hiện rất nhiều lần nhưng không thu được kết quả cần thiết từ những điều kiện cho trước thì không được xem là một thuật toán.
Dựa vào dãy số gồm n số em hãy chỉ ra KẾT QUẢ CẦN ĐẠT ĐƯỢC của bài toán : Tính tổng của các phần tử lớn hơn 0 trong dãy n số cho trước
A.Số thứ tự của các số trong dãy gồm n số
B.Vị trí của số thứ n
C.Dãy gồm n số
D.Tổng các phần tử lớn hơn 0