Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > функция Аккермана

Автор: FatKiller 5.6.2004, 18:28

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

Автор: cardinal 5.6.2004, 18:50

Цитата

Следующая программа вычисляет функцию Аккермана с использованием рекурсивной функции 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

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

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

Автор: @lex 16.6.2004, 11:21

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

Цитата

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

Автор: Akina 21.6.2004, 09:39

Цитата

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

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

Автор: ТРЕТЬ 2.4.2006, 12:23

Всё конечно здорово, но до меня лично не доходит что-то зачем там нужна 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

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

Цитата

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

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