Thuật toán ngày xuân

Ngày xuân kể về Thuật toán

Nguyễn Xuân Huy

Năm Quý Mùi xin giới thiệu với các bạn một vài thuật toán nhẹ nhàng nhưng có phần bổ

ích dùng trong vài phút vui Xuân. Hầu hết các thuật toán trong bài đều do các bạn học

sinh đề xuất.

Mừng Xuân Quý Mùi Bạn Xuân muốn làm một nền thiếp chúc Tết Quý Mùi gồm 2n

dòng

văn bản mỗi dòng có đúng n ký tự Q và M sao cho hai dòng kề nhau khác nhau tại đúng

một vị trí, dòng đầu tiên và dòng cuối cùng cũng khác nhau tại đúng một vị trí. Thí dụ, với

n=3 thì nền tấm thiếp của bạn đó sẽ như sau:

QQQ

QQM

QMM

QMQ

MMQ

MMM

MQM

MQQ

Cho trước chiều dài n trong khoảng 1.. 20. Hãy tạo một nền thiếp theo yêu cầu của bạn

Xuân. Kết quả ghi trong tệp văn bản QUYMUI.OUT.

Bài giải

Với n=1 ta có 2 dòng

Q

M

Giả sử ta đã thu được các dòng cho trường hợp n-1. Để thu được kết quả cho n ta thực hiện

2 bước sau đây:

Bước 1: Thêm Q vào các dòng của thiếp n-1

Bước 2: Lật các dòng của thiếp n-1 và thêm M vào mỗi dòng đó.

Thí dụ, với n=2 ta đã có 4 dòng

QQ

QM

MM

MQ

Để tính n=3 ta có

Bước 1:

QQQ

QQM

QMM

QMQ

Bước 2:

MMQ