Версия для печати темы

Автор: lopata 4.01.2010 18:03

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

Для слова XTREE получается след. ёлка :
http://keep4u.ru/full/d7bf8668f942fe599d4b4b3b7251fa97.html

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

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

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

Автор: andriano 4.01.2010 18:13

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

Автор: lopata 4.01.2010 19:29

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

Автор: andriano 4.01.2010 20:07

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

Автор: lopata 4.01.2010 20:15

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

Автор: volvo 4.01.2010 20:46

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

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

Автор: lopata 5.01.2010 22:38

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

Автор: andriano 5.01.2010 23:55

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

Автор: lopata 6.01.2010 1:11

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

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

Автор: TarasBer 6.01.2010 1:32

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

Автор: lopata 6.01.2010 1:36

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

Автор: andriano 6.01.2010 1:38

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

Автор: lopata 6.01.2010 1:41

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

Автор: andriano 6.01.2010 1:51

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

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

Автор: lopata 6.01.2010 2:08

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

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

Автор: TarasBer 6.01.2010 2:33

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

Автор: lopata 6.01.2010 3:36

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

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

Автор: TarasBer 6.01.2010 3:48

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

Автор: lopata 6.01.2010 5:38

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

Автор: volvo 6.01.2010 5:55

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

  1  
2 3 4

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

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

    1    
  2 3 4  
5 6 7 8 9

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

Автор: lopata 6.01.2010 6:23

Договорились.
Насколько мой воспаленный мозг соображает:
То есть из "5" будет столько же путей сколько и из "2" , ;
из "6" будет столько путей сколько из "3" +из "2"


Добавлено через 9 мин.
из середины и из вершин только один путь.

Автор: volvo 6.01.2010 6:34

А я не говорил ,что тебе известно число путей из "5", заметь... Кроме того, вершины "5" и "7" никак не связаны между собой, поэтому и при вычислении f("7") - обозначим это так - ты не должна рассматривать f("5"). Семерка связана ТОЛЬКО с "3", поэтому придется тебе выражать количество путей из "7" через количество путей из "3"...

Неправда... Из "6" ты можешь пойти либо через "2" (тогда число путей будет равно тому, что нам известно для "2"), либо через "3" (тогда число путей совпадет с их числом для "3"). А всего их будет f("6") = f("2") + f("3")

Возражения?

Автор: lopata 6.01.2010 6:37

Да, это я поняла.

Автор: lopata 6.01.2010 8:28

если честно, не смогла применить эту логику...
поэтому просто подогнала формулу..

Автор: andriano 6.01.2010 17:01

В данном случае мне кажется более продуктивным №обратить" задачу. Т.е. двигаться по дереву не от основания к вершине (в направлении распространения пламени), а от вершины к основанию (т.е. в обратном направлении).
Очевидно, в каждой вершине образуются два новых пути кроме центрального ствола, где их три.

Автор: volvo 6.01.2010 18:18

Ну, и что у тебя получилось? Какова окончательная "подогнанная" формула?

Автор: lopata 6.01.2010 22:18

f(n)=f(n-1)*2+1

Автор: TarasBer 6.01.2010 22:42

И как же тогда будет выглядеть код функции на паскале?

Автор: volvo 6.01.2010 22:55

Это неправильная формула. По крайней мере ты не вычислишь по ней ничего. Чему, скажем, равно F(1)?

Автор: lopata 6.01.2010 22:56

тогда я вообще не понимаю/

Автор: volvo 6.01.2010 23:02

Тебе уже неоднократно говорили, что надо ставить граничные условия. Если б ты написала, что
f(n) = f(n-1) * 2 + 1; f(0) = 0 - это уже можно было бы запрограммировать. А так у тебя нет ни малейшего шанса дождаться вычисления по приведенной тобой формуле: программа все время будет искать предыдущее значение. До бесконечности. Практически же все окончится гораздо раньше: как только переполнится стек - программа вылетит с ошибкой.

Вот, например, формула, которая выдаст правильный ответ (если правильно запрограммировать функцию, и правильно ее вызвать):
f(0) = 0; f(1) = 1; f(n) = f(n - 1) + 2(f(n - 2) + 1)

Автор: lopata 6.01.2010 23:19

а если я сделаю так:

FUNCTION f(n : longint) : Longint;
BEGIN
IF n = 1 THEN f := 1
   ELSE f := f(n-2)*2+1
END;

?

Добавлено через 3 мин.
вычисляет верно..

Автор: TarasBer 6.01.2010 23:57

> вычисляет верно..

Ну и хорошо.

Добавлено через 2 мин.
От себя добавлю: я даже не буду придираться к *2 вместо shl 1, всё равно пытаться оптимизировать вычисление степени двойки через рекурсию бесполезно, а если уж оптимизировать, то ответ писать в виде f := 1 shl (n shr 1 + 1) - 1, но он, увы не соответствую требованию задания непременно воткнуть рекурсию.

Автор: lopata 7.01.2010 0:21

но все равно ведь формула должна быть другая..

Автор: TarasBer 7.01.2010 0:32

Формула правильная, в чём проблема?

Автор: lopata 7.01.2010 0:36

не знаю. просто я очень долго мучалась. пыталась найти какие-то решения. а тут раз и ..

Автор: lopata 7.01.2010 2:58

всем большое спаcибо.

Автор: lopata 12.01.2010 15:30

Volvo,спасибо) оказывается эта логика очень даже пригодилась.
нужно было сделать функцию с 2 параметрами: номер уровня и номер буквы по счету.