рекурсия Опции

[lopata]

Количество свечей, которые можно поставить(повесить) на Рождественскую елку зависит от высоты(h) елки.
Изучите следующие примеры освещения свечами:


1 рис. h = 1. Candles = 1;
2 рис. h = 2. Candles = 4;
3 рис. h = 3. Candles = 13;
a)Укажите(дайте) рекурсивное определение и рекурсивный алгоритм для Candles(h).
b) Реализуйте итеративный ввод с действием для Candles(h).

Честно говоря, вообще не понимаю как это делать..
Объясните, пожалуйта, если кто понял, что нужно вообще делать в этом задании.
Не понимаю как это можно делать с помощью рекурсии..да и вообще не понимаю как это делать.

[volvo]

Подозрительно похоже на Салфетку Серпинского. Посмотри в FAQ-е, klem4 по-моему, показывал, как такое делается...

[lopata]

Спасибо, volvo. Просто не было понятно , что это вообще.
Попробую разобраться.

[lopata]

Как выяснилось (хотя возможно и неверно), что количество
Candles =(3 в степени (h-1)) + (3 в степени (h-2))

Вроде сходится..
а как применить на практике не знаю
саму рекурсию не особо понимаю.
Не мог бы кто-нибудь объяснить как это можно сделать.

[lopata]

всё...терь я совсем запуталась.

[Tony]

Ну если я правильно понимаю поставленную задачу, то при h = 4 ответ будет 40, и при этом соотношени Candles(h) = 3^(h-1) + 3^(h-2) неверно...

Но тогда верно другое соотношение, а именно : Candles(h) = 3 * Candles(h - 1) + 1; Candles(1) = 1.

Программно это реализуется так :

Код

function Candles(h:longint):longint;
begin
  if h = 1 then Candles := 1 else Candles := 3 * Candles(h - 1) + 1;
end;

При этом функция Candles вызывает сама себя до тех пор, пока h не станет равным 1. После этого рекурсия как бы возвращается назад, используя полученные значения... Вообще конечно это сложно объяснить .

[volvo]

Как выяснилось (хотя возможно и неверно), что количество
Candles =(3 в степени (h-1)) + (3 в степени (h-2))

Вроде сходится..

Не сходится, потому что неверно. Верная формула: Candles(h) = (3^h - 1) / 2

[lopata]

Спасибо,Tony . Но я все равно не могу понять как работают эти рекурсии.

Добавлено через 2 мин.
volvo , а как ты откопал эту формулу?.

[volvo]

а как ты откопал эту формулу?

А чего ее откапывать? Я ее и не закапывал вообще-то. У меня память хорошая, если честно, я просто помню много разных формул...

[andriano]

а как ты откопал эту формулу?.

Вообще-то формулы не откапываются, а выводятся.

[lopata]

а как ты откопал эту формулу?.

Вообще-то формулы не откапываются, а выводятся.

я это и имела в виду.

[lopata]

Спасибо . Теперь, кажется, начинаю понимать как работают рекурсии.
Вот такая вот функция получилась с итерацией:

FUNCTION CandlesIter (h : Integer):integer;
VAR i, c : integer;
    temp :integer;
BEGIN
temp:=0;
        FOR i:= 1 TO h DO
                 temp:= 3*temp+1;
                 CandlesIter:=temp;
END;

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

[Lapp]

Спасибо . Теперь, кажется, начинаю понимать как работают рекурсии.
Вот такая вот функция получилась с итерацией:

FUNCTION CandlesIter (h : Integer):integer;
VAR i, c : integer;
    temp :integer;
BEGIN
temp:=0;
        FOR i:= 1 TO h DO
            BEGIN
                 temp:= 3*temp+1;
                 CandlesIter:=temp;
            end;
end;

А где тут рекурсия?

[lopata]

Как видишь, тут рекурсии нет.
Я говорю о той функции, которую написал Tony.