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

[lopata]

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


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


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

[volvo]

из "7" тоже столько сколько и из "5".

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

из "6" будет столько путей сколько из "3" +1 ;

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

Возражения?

[lopata]

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

[lopata]

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

[andriano]

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

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

[volvo]

поэтому просто подогнала формулу..

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

[lopata]

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

[TarasBer]

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

[volvo]

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

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

[lopata]

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

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

[volvo]

Тебе уже неоднократно говорили, что надо ставить граничные условия. Если б ты написала, что
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]

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

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

?

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

[TarasBer]

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

Ну и хорошо.

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

[lopata]

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

[TarasBer]

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

[lopata]

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

[lopata]

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

[lopata]

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