F(0) = F(F(11)) = F(F(F(22))) =
...
= F(F(F...F(F(110))...))
│ └──┬─┘
│ │ [color=blue]>100[/color]
v v
F( 100 )
└───┬──┘
│ [color=darkred]≤100[/color]
v
F(F(111))
└──┬─┘
│ [color=blue]>100[/color]
v
101
└───┬───┘
│ [color=blue]>100[/color]
v
91
...
Найти значение функции F(F(N+11)) без применения рекурсии
F={F(F(N+11)),N<=100;
N-10,N>100}
причем понятно что рекурсией это решилось за 3 минуты обмозгования
заранее спасибо
N-10,N>100}
причем понятно что рекурсией это решилось за 3 минуты обмозгования
заранее спасибо
попробуем вычислить F(0), получим такую картинку:
на каждом шаге функция представима в виде цепочки F(F(F(F(...)))) причем значение аргумента ≤100 приводит к удлинению цепочки на 1 элемент, а >100 -- к укорочению на 1.
Отсюда -- итеративная реализация:
проверил сравнивая значения итеративной и рекурсивной версии для N ∈ {0 … 200}, так что все верно
Код:
на каждом шаге функция представима в виде цепочки F(F(F(F(...)))) причем значение аргумента ≤100 приводит к удлинению цепочки на 1 элемент, а >100 -- к укорочению на 1.
Отсюда -- итеративная реализация:
Код:
depth = 1
while depth > 0:
if N > 100:
depth -= 1
N -= 10
else:
depth += 1
N += 11
return N
while depth > 0:
if N > 100:
depth -= 1
N -= 10
else:
depth += 1
N += 11
return N
проверил сравнивая значения итеративной и рекурсивной версии для N ∈ {0 … 200}, так что все верно
спасибо, неожиданно простое решение