Lập trình Scratch tìm dãy con tăng dài nhất

Like Tweet Pin it Share Share Email

Bài toán tìm dãy con tăng dài nhất là một bài toán cơ bản trong lập trình, bài này cũng nằm trong giáo trình bồi dưỡng HSG pascal của mình. Hôm nay mình sẽ chuyển sang code bằng Scratch để bạn nào đang luyện thi Scratch có thể tham khảo cho vui.

Ý tưởng tìm dãy con tăng dài nhất

Tìm tất cả các dãy con tăng và chọn ra dãy dài nhất:

Mình lấy ví dụ ta có dãy số sau:  [2; 7] ; [5 ; 6; 8 ; 11 ; 12] ; [8] ; [7 ; 24] ; [6]

–  Dùng 1 biến lưu vị trí đầu tiên của các dãy con tăng – Biến “Lưu”

– 1 biến đếm số phần tử của các dãy tăng – Biến “Đếm”

– 1 biến lưu độ dài dãy tăng lớn nhất – Biến “Max”

– 1 biến để đánh dấu vị trí đầu tiên của dãy dài nhất khi được chọn (biết vị trí đầu tiên và số phần tử sẽ biết được dãy từ đâu tới đâu) – Biến “Lưu”

Lập trình tìm dãy con tăng dài nhất trong Scratch

Chúng ta bắt đầu thực hiện nào

Bước 1: Đánh dấu vị trí đầu tiên và số phần tử của dãy con tăng dài nhất

Đoạn chương trình trên hơi phức tạp nôm na là như sau.

Nó sẽ đi tìm từ đầu dãy con tăng đầu tiên sau đó lưu lại vị trí đầu tiên của dãy vào biến “Lưu” và lưu số phần tử của dãy vào biến “Max”. Tiếp theo đi tìm dãy con tăng tiếp theo và lại “Đếm” xem dãy đó có bao nhiêu phần tử, nếu số phần tử đếm được mà lớn hơn “Max” thì có nghĩa là dãy trước đó không phải là dãy dài nhất, lúc này tạm thời dãy này mới là dãy dài nhất. Lưu lại vị trí đầu tiên và số phần tử của dãy này. Cứ như vậy kiểm tra cho tới hết thì thôi.

Bước 2: Xuất kết quả ra biến ‘Kết quả”

Ta đưa dữ liệu dãy con tăng dài nhất ra một biến mình đặt tên là “kết quả” để tiện cho chú mèo nói kết quả ra màn hình như sau:

ở đây mỗi phần tử mình viết cách nhau một khoảng trắng cho đơn giản. Còn nếu bạn muốn dùng dấu “;” để ngăn cách thì sửa code lại phức tạp hơn 1 chút kẻo xuất thừa một dấu ở đầu xâu.

Bước 3: Hoàn thiện và xem kết quả

Và bây giờ hãy gọi hai thủ tục trên và cho mèo nói ra kết quả thôi

Bạn hãy bấm lá cờ và ta có kết quả như sau:

Mình để hiển thị mảng nhập vào để các biện tiện theo dõi. Trong chương trình này mình import dữ liệu cho mảng từ một file .txt đã nhập sẵn dữ liệu.

Có thể bạn quan tâm: Cách vẽ đường tròn nội tiếp, ngoại tam giác đều trong Scratch cho học sinh tiểu học
Chúc các bạn thực hiện thành công và đừng quên comment chia sẻ nếu có thắc mắc, cũng như có ý tưởng hay hơn.

Comments (0)

Trả lời

Your email address will not be published. Required fields are marked *