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

FatKiller

Дата 5.6.2004, 18:28 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Очень нужна нерекурсивная формулировка функции.
Заранее благодарен.

cardinal

Дата 5.6.2004, 18:50 (ссылка)

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

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

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

Цитата

Следующая программа вычисляет функцию Аккермана с использованием рекурсивной функции ackr и вспомогательной функции smacc:

/* рекурсивное вычисление функции Аккермана */
# include
main () /* вызывающая */
{ int x,y,n,t; /* функция */
int ackr(int, int, int);
scanf("%d %d %d",&n,&x,&y);
t=ackr(n,x,y);
printf("%d",t);
}
int smacc( int n,int x ) /* вспомогательная */
{ switch (n) /* функция */
{ case 0: return(x+1);
case 1: return (x);
case 2: return (0);
case 3: return (1);
default: return (2);
}
}
int ackr( int n, int x, int y) /* рекурсивная */
{ int z; /* функция */
int smacc( int,int);
if(n==0 || y==0) z=smacc(n,x);
else { z=ackr(n,x,y-1); /* рекурсивные */
z=ackr(n-1,z,x); } /* вызовы ackr(...) */
return z;
}

Модифицируя функции main и ackr в соответствии с изложенным методом получим следующую программу:

/* Эквивалентная нерекурсивная программа */
/* для вычисления функции Аккермана */
#include
#include
int main()
{ typedef struct st
{ int i,j,k,z,lr;
struct st *pst;
} ST;
ST *u, *dl=NULL;
int l,x,y,n;
int smacc(int,int);
int an,ax,ay,rz,t;
scanf("%i %i %i",&n,&x,&y);
an=n;ax=x;ay=y;l=1; /* - замена вызова - */
goto ackr; /* t=ackr(n,x,y); */
l1: t=rz; /* - - - - - - - - */
printf("\n %d ",t);
goto jackr;
/* начало фрагмента заменяющего функцию ackr */
ackr:
u=( ST *) malloc( sizeof (ST) );
u->i=an;
u->j=ax;
u->k=ay;
u->lr=l;
u->pst=dl;
dl=u;
if (an==0||ay==0)
dl->z=smacc(an,ax);
else
{
an=dl->i; /* - замена вызова - */
ax=dl->j; /* */
ay=dl->k-1; /* z=ackr(n,x,y-1); */
l=2; /* */
goto ackr; /* */
l2: dl->z=rz; /* - - - - - - - - */
an=dl->i-1; /* - замена вызова - */
ax=rz; /* */
ay=dl->j; /* z=ackr(n-1,z,x); */
l=3; /* */
goto ackr; /* */
l3: dl->z=rz; /* - - - - - - - - */
}
rz=dl->z; /* - - - - - - - - */
an=dl->i; /* */
ax=dl->j; /* замена */
ay=dl->k; /* */
l=dl->lr; /* оператора */
u=dl; /* */
dl=u->pst; /* return z ; */
free(u); /* */
switch(l) /* */
{ case 1: goto l1; /* */
case 2: goto l2; /* */
case 3: goto l3; /* */
} /* - - - - - - - - */
jackr:
}
int smacc( int n,int x ) /* вспомогательная функция */
{ switch (n)
{ case 0: return(x+1);
case 1: return (x);
case 2: return (0);
case 3: return (1);
default: return (2);
}
}

http://www.opu.odessa.ua/up/c/h24.htm

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

FatKiller

Дата 5.6.2004, 21:32 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Ууууууууу ....
Блин у меня с С плоховато

А мона без кода вообще, ну "устную" формулировку?

@lex

Дата 16.6.2004, 11:21 (ссылка)

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

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 82
Регистрация: 3.2.2004
Где: Москва

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

линк посмотри...

Цитата

http://www.opu.odessa.ua/up/c/h24.htm

Akina

Дата 21.6.2004, 09:39 (ссылка)

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

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

Цитата

А мона без кода вообще, ну "устную" формулировку?

Дурацкий вопрос (милль пардон). Есть функция Аккермана. Одна-единственная, в принципе не подозревающая и существовании рекурсии. И есть программные реализации ее вычисления - вот именно они могут быть рекурсивными либо нерекурсивными.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

ТРЕТЬ

Дата 2.4.2006, 12:23 (ссылка)

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

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 8.1.2006
Где: mind's gloomy corner

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

Всё конечно здорово, но до меня лично не доходит что-то зачем там нужна 3 переменная... Вот скажем формулировка задачи, которая мне досталась

A(0,n)=n+1 (при n>= 0)
A(m,0)=A(m-1,1)(при m>0)
A(m,n)=A(m-1,A(m,n-1)) (при m,n>0)

Вот теперь пялюсь на ваше решение и не могу понять откуда берется третья переменная... Мот кто объяснит?

cardinal

Дата 2.4.2006, 13:53 (ссылка)

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

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

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

А есть такая формулировка:

Цитата

Ackermann originally considered a function A(m, n, p) of three variables...

http://en.wikipedia.org/wiki/Ackermann_function
Может поэтому, но это не так важно. Никто тебе не запрещает сделать с двумя...

--------------------

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