Dãy 0-1 là dãy vô hạn phần tử chỉ gồm các số 0 và 1 được xây dựng theo quy luật sau đây: Số đầu tiên là số 0. Nối vào dãy các số đã viết “dãy số đảo” của nó (là dãy số có cùng chiều dài với dãy đã viết, trong đó số 0 ở dãy đã viết thành số 1 ở “dãy số đảo” và số 1 ở dãy đã viết trở thành số 0 ở “dãy số đảo”). Như vậy sau mỗi lần nối, chiều dài của dãy tăng lên gấp đôi.
Dưới đây là 5 bước đầu tiên để hình thành dãy 0-1:
0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Nhiệm vụ:
Viết chương trình xác định chữ số ở vị trí thứ N của dãy 0-1
Dữ liệu: Cho trong tập tin SEQ01.inp gồm 1 dòng duy nhất chứa 1 số nguyên dương N duy nhất (N<=30000)
Kết quả: Cho trong tập tin văn bản SEQ01.out, chứa 1 số nguyên duy nhất chỉ chữ số ở vị trí thứ N của dãy 0-1
Ví dụ:
SEQ01.inp:
11
SEQ01.out:
0
Uses crt;
Trả lờiXóaVar i,n,m2:longint;
f:array[1..100000] of char;
Begin
readln(n);
f[1]:='0';
f[2]:='1';
m2:=2;
For i:=3 to n do
Begin
If f[i-m2]='0' then f[i]:='1' else f[i]:='0';
If (i mod m2=0)and(i div m2=2) then m2:=m2*2;
end;
Write(f[n]);
readln;
end.