Đề thì OLP sinh viên chuyên 2004 ĐHHH

[real_time]

Bài 2: Dãy nhị phân

Cho tập S tất cả các dãy nhị phân độ dài N. Trong đó mỗi dãy ko có hai bit một nào kề nhau. Các dãy này được xếp theo chiều tăng dần của số nguyên tương ứng mà dãy biểu diễn. theo thứ tự đó, mỗi dãy có một số hiệu bắt đầu từ 1.
Ví dụ với N=5 ta có
Số hiệu Dãy
1 00000
2 00001
3 00010
4 00100
5 00101
... ...
Yêu cầu Tìm dãy nhị phân có số hiệu M trong Tập S
Dữ liệu vào từ File văn bản có tên là BinSeq.Inp gồm hai số N và M mỗi số cách nhau một dấu cách, trong đó N là độ dài của dãy, M là số hiệu của dãy nhị phân cần tìm(2<=N<=200)
Kết quả aghi ra File BINSEQ.OUT dãy nhị phân độ dài N có số hiệu M.
Ví dụ
BINSEQ.INP
5 5
BINSEQ.OUT
00101

[Junior IT]

Xét 2 loại dãy
- Dãy bắt đầu bằng số 0
- Dãy bắt đầu bằng số 1
Dùng công thức Quy hoạch động :
f[0][N] = số dãy độ dài N có số bắt đầu là 0
f[1][N] = số dãy độ dài N có số bắt đầu là 1
=> f[0][N] = f[1][N - 1] + f[0][N - 1]
f[1][N] = f[0][N - 1]
Rồi theo bảng QHĐ đó truy ngược ra dãy kết quả

[real_time]

Tui sợ cách này chậm. yêu cầu test lớn nhất là 200 chữ số cơ mà.
Mỗi test chỉ 1 giây thôi

[quoc_vu]

cách giải rất đơn giản gọi f(i) là số dãy có được khi chữ số 1 đứng ở vị trí thứ i
f(1)=1
f(2)=1
f(3)=f(2)+f(1)
f(i)=f(i-1)+f(i-2) dãy Fibonacy
cấu trúc dữ liệu : vì n<=200 nên phải dùng chuỗi để lưu mảng f
rồi từ từ lần ra dãy cần tìm

[tranlethu]

he he cac bac biet the na`o la` day fibo nhi phan chua
000001->0
000010->1
000100->2
000101->2
001000->3
001001->3
001010->3
010000->5
010001->5
010010->5
010100->5
010101->5
Cu theo nhu vay la ta tinh ra duoc so can tim theo Da Fibo test chua den 1s