VPF::Функция Аккермана - Форум программистов

ISMD

Дата 16.4.2006, 00:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 16.4.2006

Репутация: нет
Всего: нет

Нужны два варианта решения: рекурсивный и итерационный.

1. Рекусия уже написана но очень быстро переполняется стек. Подкиньте идею оптимизации.

2. Нужно решение итерационное с помощью имитации стека массивом записей. smile

Код



function Acc(n,m : word): word;
begin
if (n=0) then Acc:=m+1 else
    begin
    if (n<>0)and(m=0) then Acc:=Acc(n-1,1);
    if (n<>0)and(m<>0) then Acc:=Acc(n-1,Acc(n,m-1));
end;

volvo877

Дата 16.4.2006, 13:36 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2073
Регистрация: 15.11.2004

Репутация: 2
Всего: 116

Цитата(ISMD @ 15.4.2006, 23:51

)

Рекусия уже написана но очень быстро переполняется стек

На то она и функция Аккермана smile

Кстати, у тебя лишние проверки производятся. Можно от них избавиться:

Код


Function Acc(N, M: LongInt): LongInt;
begin
  If N = 0 then Acc := M + 1
  Else
    If M = 0 then Acc := Acc(N - 1, 1)
    Else Acc := Acc(N - 1, Acc(N, M - 1))
end;

Кстати, вот второй способ рекурсивной реализации (здесь стек будет переполняться не так быстро):

Код


Function FAcc(n, m: LongInt): Longint;
begin
  While n <> 0 Do Begin
    Dec(n);
    If m = 0 Then m := 1 Else m := FAcc(n + 1, m - 1);
  End;
  FAcc := m + 1;
end;

ISMD

Дата 16.4.2006, 16:48 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 3
Регистрация: 16.4.2006

Репутация: нет
Всего: нет

Volvo877, спасибо за идейку smile

.

Интересно, что насчёт записей, статическая память по идее будет переполняться лишь немного медленнее, т. к. все переменные остаются, а исключается только адрес возврата. Но ещё саму структуру надо разработать smile

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Object Pascal: кроссплатформенные технологии \| Следующая тема »