IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> избавиться от рекурсии, переписать функцию
сообщение
Сообщение #1


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Добрый день!
Есть следующие функция:
function f_a(const n : integer): longint;
begin
if n <= 1 then f_a:=1 else
f_a:=n - f_a(f_a(n-1));
end; { f_a }

Необходимо переписать функцию, избавившись от рекурсии.

Для n>=0 получаем:
Код
  1   1   2   3   3   4   4   5   6   6   7   8   8   9   9  10  11  11  12  12  13  14  14  15  16  16  17  17  18  19  19  20  21  21  22  22  23  24  24  25...
То есть мы имеем цифры идущие парами, но через 3 или 5 хода встречается "цифра-одиночка".

Что с этим делать - не знаю. Буду рад помощи.

Сообщение отредактировано: compiler -


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Последовательность Хольфштадтера? smile.gif

function myFa(n: integer): longint;
function sigma: real;
begin
sigma := (sqrt(5)-1) / 2;
end;
begin
myFa := trunc(sigma*(n + 1));
end;

, если не ошибаюсь...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(volvo @ 15.05.2008 15:49) *
Последовательность Хольфштадтера? smile.gif
И откуда ты это знаешь?smile.gif
Цитата
в теле функции заводи массив значений (можно выделять динамически), и последовательно заполняй его циклом for слева направо.
То есть, вместо рекурсивного вызова функции мы получаем рекурсивное обращение к элементам массива.. Где-то я такое уже видел, да подзабыл уже...

Спасибо!


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата
получаем рекурсивное обращение к элементам массива


да, вроде того smile.gif

есть еще рекурсия с запоминанием промежуточных результатов.

это когда к итерации не переходишь (не заменяешь рекурсию циклом), но заводишь внешний массив, и в рекурсивной процедуре всегда сохраняешь полученный результат в этот внешний массив.

а в самом начале процедуры смотришь, не вызывалась ли она раньше с такими же параметрами (и если да - не считаешь ничего, а возвращаешь полученный ранее ответ).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(Michael_Rybak @ 15.05.2008 17:27) *
есть еще рекурсия с запоминанием промежуточных результатов. ...
интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


code warrior
****

Группа: Пользователи
Сообщений: 484
Пол: Мужской
Реальное имя: Славен

Репутация: -  8  +


Цитата(compiler @ 15.05.2008 18:59) *
интересно, интересно... надо будет попробовать написать так несколько функций..
ещё раз спасибо.
Это еще называется динамическим программированием.


--------------------
ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Человек
*****

Группа: Пользователи
Сообщений: 1 050
Пол: Мужской
Реальное имя: Станислав

Репутация: -  3  +


Цитата(hardcase @ 16.05.2008 17:01) *
Это еще называется динамическим программированием.
буду знать, спасибо..


--------------------
Спасибо!
Удачи!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 22.10.2021 9:51
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name