Задание В18

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

Функция F вычисляется следующей программой, написанной на языке Pascal

Function F(X: string): string;

var

     L: integer;

     T: string;

begin

     L:=length(X);

     if L>1 then

     begin

          T:=copy(X,2,L-1);

          case X[1] of

               '0': F:=T;

               '1': F:=F(T)+'0'+F(T)

          else F:=F(X)

          end;

     end;

     else F:=F(X);

end;

Строка X, для которой F(X)=10X, равна ___.

Решение.

Для нормального выхода из рекурсии необходимо, чтобы исходная строка состояла только из символов '0' или '1', количество символов больше одного.

Пусть X=0Y, тогда F(0Y)=Y. По условию задачи необходимо найти такое X, чтобы F(X)=10X, то есть F(0Y)=100Y, Y=100Y. Очевидно, что такой строки не существует.

Пусть X=1Y, тогда F(1Y)=F(Y)+’0’+F(Y). Таким образом, для вычисления функции F(1Y) необходимо вычислить F(Y).

Пусть Y=0Z, тогда F(0Z)=Z, следовательно, F(1Y)=Z0Z. Итак, если X=10Z, то F(X)=Z0Z. Найти такое X, чтобы F(X)=10X означает подобрать такую строку Z, чтобы Z0Z=1010Z. Очевидно, что это справедливо для Z=101. Тогда исходная строка X=10101.

Ответ: X=10101.