rekursia, разобраться с задачкой Опции

[Jenkins]

рекурсия

ф-я f вычисляется:

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)

Найти строку Х, для которой f(x)=020X

Нужно само решение - подробное и понятное
(ответ 100201)

[Jenkins]

НУ ТОГДА ХОТЯ БЫ ПОНЯТНОЕ...

[Lapp]

Jenkins, а ты можешь объяснить, почему задача находится в разделе Теоретические Вопросы, если тебе, как ты пишешь, "нужно само решение"? При чем тут теория Паскаля?

М

Тема переносится в раздел Задачи

Решение можно получить перебором, но нужно сделать пару оговорок.

1. По внимательном рассмотрении видно, что f(x) не будет содержать никаких символов, кроме тех, которые содержались в x - ну и, может быть, нуля. С другой стороны, никакие символы, кроме 0 и 1, не могут исчезнуть. Значит, исходная строка должна быть составлена из 0, 1 и 2. Эти три цифры используются в троичной системе счисления - следовательно, нужно перебирать троичные представления чисел. Строго говоря, нужно рассмотреть все последовательности с предшествующими нулями.

2. Если в функции происходит переход на оператор f:=f(x), то рекурсия зацикливается. Это в частности означает, что х, который привел к такой ситуации - не есть решение. Но встреча такого значения х в переборе вызовет ошибку в программе. Следовательно, такие х надо просто отбросить. Как? Ну, например, так: вместо f:=f(x) написать f:='-'. Ясно, что при таком значении функции условие задачи не выполнится, так что эти х не просочатся в решение.

Значит, так.. Организовываешь цикл с перебором всех троичных записей чисел, начиная с 0 и с учетом разного количества предшествующих нулей. Последнее можно осуществить, например, если при проверке каждого х проверять еще и последовательность цифр, получающуюся заменой первой единицы на ноль. Модифицируешь функцию, как описано в п.2 и смотришь условие f(x)='020'+x . Когда оно выполнится - печатаешь х. Если нужно найти только одно решение - выходишь, если много - продолжаешь поиск..
Вроде, все.

Возможно, есть "аналитическое решение", то есть "силой мозгов" . Надо подумать..