Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần
Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần, hãy mô tả chi tiết các bước:
Sách bài tập Tin học 11 Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần - Kết nối tri thức
Câu 27.55 trang 80 SBT Tin học 11: Thiết kế thuật toán và chương trình cho bài toán sau bằng phương pháp làm mịn dần, hãy mô tả chi tiết các bước:
Cho trước hai xâu kí tự s1 và s2. Tìm xâu s dài nhất sao cho xâu s đồng thời là phần đầu (prefix) của cả hai xâu s1 và s2.
Lời giải:
Có thể thiết kế bài toán trên theo phương pháp làm mịn dần theo các bước như sau:
1) Thiết lập xâu rỗng s.
2) Duyệt đồng thời theo các kí tự của s1 và s2 từ trái sang phải, cho đến khi kết thúc một trong 2 xâu s1, s2 và dừng khi gặp vị trí khác nhau giữa hai xâu. Trong quá trình duyệt, duyệt tới đâu thì nối với s tới đó.
3) Khi kết thúc duyệt thì dừng chương trình, trả về xâu s.
Kết quả việc chi tiết hoá các công việc trên có thể như chương trình sau:
Lời giải sách bài tập Tin học 11 Bài 27: Thực hành thiết kế chương trình theo phương pháp làm mịn dần hay khác: