Условие:
Последовательность из латинских букв строится следующим образом. Вначале она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (a, b, c, ...). Ниже приведены первые шаги построения последовательности:
Вначале. Пустая последовательность.
Шаг 1. a.
Шаг 2. baa.
Шаг 3. cbaabaa
Шаг 4. dcbaabaacbaabaa.
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
Требуется написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага.
Сокращенное условие:
Из латинских букв некоторым (см.подробное условие) образом строится последовательность. Требуется написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага.
Технические условия:
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число N (1<=N<226).
Формат выходных данных:
В выходном файла OUTPUT.TXT записывается символ, стоящий в позиции N получившейся последовательности.
Примеры входных и выходных файлов:
Input.txt
4
Output.txt
w
Решение:
---------- cut ----------
Задачу надо решать методом возврата. Этот метод использовался в задаче "Последовательность". Надеюсь, что все будет понятно после прочтения программы.
---------- cut ----------
var
k : integer;
n, p : longint;
inp, out : text;
begin
assign(inp,'input.txt'); reset(inp);
assign(out,'output.txt'); rewrite(out);
readln(inp,n);
p:=2; for k:=2 to 25 do p:=p*2;
k:=0;
while n>1 do
begin
k:=k+1;
if n>p then n:=n-p else n:=n-1;
p:=p div 2
end;
writeln(out,chr(ord('z')-k));
close(out)
end. |
