Народ.. Допоможіть.. Як знайти "глибину рекурсії"? Мається на увазі, яка найменша кількість разів ми виконували "рекурсію", приблизно для такої проги(як її переробити???)
program Project2;
{$APPTYPE CONSOLE}
var
n,t:integer;
function r(a:integer):integer;
begin
if a=n then r:=0
else
begin
r(a+2);
r(a+3);
end;
end;
begin
readln(n);
t:=r(0);
writeln(t);
end.
Тобто, питання таке:
прога повинна виводити мінімальну кількість доданків(2 або 3), щоб отримати N.
Приклад:
IN 6
Out 2
От постійно думаю над тим, міняти свій девіз на "рекурсія - зло", чи хай залишається, як є?.. Взагалі, найпростіший спосіб оцінити глибину рекурсії - це "рекурснутись", тобто спробувати виконати те, що повинна виконати рекурсія, і подивитись, що з того вийде. А далі математично оцінити глибину тієї.. е... прірви... в яку затягне дана рекурсія. Конкретно в цьому випадку порадив би написати прямий розв'язок за сталий час, тобто алгоритмічно щось таке:
if (a==1){return -1;} else {return (a-1)/3+1;}
ідея та сама, що була на минулому матчі на ТопКодері (дів2-250, словом, "яйця".
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
var v : longint;
function r(a:integer):integer;
begin
inc(v);
if a=n then r:=0
else
begin
r(a+2);
r(a+3);
end;
end;
Тоді (якщо ви перед викликом функції обнулили v) в змінній v буде міститися к-ть викликів r. А далі математично оцінити глибину тієї.. е... прірви... в яку затягне дана рекурсія. (c)
P.S.
ідея та сама, що була на минулому матчі на ТопКодері (дів2-250, словом, "яйця".
А про яйця я щось пригадую, але крім простого перебору я нічого тоді не придумав
Змінив(ла) Witaliy, 18-11-2009 17:36
Witaliy написав:
Простіше просто трішки змінити функцію:
...
Тоді (якщо ви перед викликом функції обнулили v) в змінній v буде міститися к-ть викликів r. А далі математично оцінити глибину тієї.. е... прірви... в яку затягне дана рекурсія. (c)
Ну так. Заставити комп рекурснутись часто простіше, ніж зробити це самому. Добре, якщо є доступ до залізяк під струмом, які можуть рахувати Гірше, коли під рукою книжка з кодом, а комп десь далеко.
Witaliy написав:
А про яйця я щось пригадую, але крім простого перебору я нічого тоді не придумав
Я вже тобі розписував в асьці. Якщо яєць менше шести, або десять, або непарне число - неможливо розкласти, інакше - потрібно число кошиків, рівне "яйця поділити на 8 і округлити вверх".
P.S. Коли вже тестувалка підніметься після епідемії, в мене вже 3 задачі в планах
Одінь окуляри з фіолетовим шклом - так легше стіну пробивати чолом.
Змінив(ла) LeBron, 18-11-2009 20:55
Повідомлень: 167 Звідки: ЛНУ ім. Івана Франка Зареєстрований: 21.10.06
Опубліковано 19-11-2009 00:24
Witaliy написав:
Простіше просто трішки змінити функцію:
var v : longint;
function r(a:integer):integer;
begin
inc(v);
if a=n then r:=0
else
begin
r(a+2);
r(a+3);
end;
end;
Маленька поправочка - це буде не глибина рекурсії, а кількість усіх викликів функції. Правда я не знаю, чи це власне не те, що хотів автор цієї теми.
Якщо він хотів оцінити складність його алгоритму (точніше кількість операції на макс. тесті) - то такий спосіб якраз підходить. Якщо в нього ж були проблеми з переповненням стеку викликів, то йому власне якраз глибину треба.
Тобто щось на зразок такого:
var d : longint;
function r(a:integer; i:integer):integer;
begin
if a=n then
begin
r:=0
d = max(d,i);
end
else
begin
r(a+2, i + 1);
r(a+3, i + 1);
end;
end;
Birthday(s):
![mylyanyk.ivan [Lviv_NU]](../themes/Brasil-Fusion/forum/yahoo.gif)
.
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
