рекурсия, еще одна Опции

[lopata]

Не только слово XTREE , все слова с нечетным количеством букв подходят для "ёлочной" рекурсии. Все буквы слова расположены в форме ёлки.

Для слова XTREE получается след. ёлка :


Представьте себе, что вы уполномоченный по безопасности пожарной службы. Сколько возможных путей пожара до верхушки, если одна буква на самом нижнем уровне зажигается через одну свечку и огонь может распростроняться тольк вверх и вправо-вверх (в левой половине дерева) и соответсвенно влево-вверх (в правой половине дерева).

Ответьте на вопрос рекурсивным математическим определением функции XFire и реализуйте в паскале.

Помогите, пожалуйста, разобраться. Не понимаю вообще как решать задачу.
В какую сторону идти?

Сообщение отредактировано: lopata - 4.01.2010 18:04

[andriano]

Для начала почитать что-нибудь про рекурсию.
Этого достаточно.

[lopata]

Для начала я почитала. И тем не менне непонятно... Я понимаю, что это моя проблема в непонимании. Но прошу помочь как-нибудь..

[andriano]

И чего ты хочешь?
Чтобы тебе пересказали то же самое, но своими словами?

[lopata]

Я не знаю. Просто объяснить как рекурсия работает на этом примере.

[volvo]

Просто объяснить как рекурсия работает на этом примере.

Почему именно на этом? Тебе уже объясняли, как работает рекурсия, неоднкратно. Ты говоришь, что читала, но не поняла. Какой смысл здесь "растекаться мыслью по древу" (С)? Если ты не поняла там - какой шанс у тебя понять здесь?

Ты разберись, как вообще работает рекурсия (на чем-то самом простом), а потом будешь пытаться применить ее в своей задаче.

[lopata]

Что такое рекурсия теоретически я понимаю. Понимаю как работают примеры вычесления факториала, послед. Финабоччи и возведения в степень. Дальше дело не идет(

[andriano]

Что такое рекурсия теоретически я понимаю. Понимаю как работают примеры вычесления факториала, послед. Финабоччи и возведения в степень. Дальше дело не идет(

Расскажи.
Отсюда и "начнем плясать".

[lopata]

по идее Wegs(Wort) := Wegs(wort)-3+Wegs(wort-2)
Wegs(3) = 3

*Wegs- кол-во путей
*Wort - кол-во букв

Сообщение отредактировано: lopata - 6.01.2010 1:22

[TarasBer]

Непонятно.
Wegs(Wort) := Wegs(Wort)-3+Wegs(Wort-2) - это не рекурсивное математическое определение, так как справа тоже стоит Wers(Wort), который мы и пытаемся определить.

[lopata]

тогда я совсем не поняла(
Wegs := Wegs(Wort)-3+Wegs(Wort-2)

[andriano]

Хорошо, что значит?
i := i+1;

[lopata]

значение увеличивается на единицу...

[andriano]

Вот то же самое происходит и с функцией: она вызывает сама себя с ДРУГИМ(!) значением параметра и из полученных чисел формирует собственное возвращаемое значение.
Т.е. справа - результат вызова других экземпляров функции, а слева - значение, которое она вернет наружу.

Кстати, обрати внимание, если при рекурсивном вызове значение параметра не изменяется, то рекурсия не когда не может закончиться. Т.е. ВСЕГДА нужно проверять, чтобы
1. Передаваемое п рекурсии значение не совпадало с входным
2. Существовало корректное условие завершения рекурсии.

Сообщение отредактировано: andriano - 6.01.2010 1:52

[lopata]

Вроде.
Путь(n) = Путь(n-2) + 2 в /
например Путь(5)= Путь(3)+ 2 в степени 2..
степень увеличивается на 1..

или вот еще один бред:
Путь(7)= Путь(5) +(Путь(5) -Путь(3))*2

Сообщение отредактировано: lopata - 6.01.2010 2:28

[TarasBer]

Уже ближе к истине, но всё равно - как в итоге выглядит общая формула
f(n) = ?

[lopata]

судя по тому, что было выше, то: *ну да
f (n):= f(n-2)+ (f(n-4)-f(n-2))*2

больше пока идей нету..

Сообщение отредактировано: lopata - 6.01.2010 3:51

[TarasBer]

Что здесь такое f-2? Перечитай хотя бы то, что написала.

[lopata]

я имела в виду:
f (n):= f(n-2)+ (f(n-2)-f(n-4))*2
но оно все равно неверно

[volvo]

Давай пойдем другим путем, ты перестанешь гадать, и начнешь рассуждать, договорились? Начнем с самого простого варианта твоего "дерева": допустим, что оно выглядит так:

  1  
2 3 4

(разные значения узлов - просто чтоб проще ориентироваться). Представила себе это? Допустим (я говорю, допустим, пока), тебе уже известно, сколько путей пожара есть от вершины "2", от вершины "3" и от вершины "4".

А теперь добавляем еще один уровень, внизу:

    1    
  2 3 4  
5 6 7 8 9

Как теперь, зная, сколько путей есть из "2" и из "3", найти, сколько путей есть из "5" или из "6"?