Студентам
Преподавателям
Оценка качества образования
Образовательные интернет-ресурсы ТГТУ
Организациям-партнерам
|
Раздел "Информатика, вычислительная техника, автоматизация" C
2.4.
,
, , ,
.
()
.
int a()
{.....a().....}
,
. ,
, .
:
a(){.....b().....}
b(){.....c().....}
c(){.....a().....} .
a,b,c , ,
.
. 1,2,3.
1 n ,
(..31).
, 1
3 2 .
,
. , n
2^n-1.
1 2 3
| | |
+ +---+ | |
| +-+---+-+ | |
n +-+-------+-+ | |
| +-+-----------+-+ | |
+ ==+---------------+===========-===============-=========
.31. .
,
, - i
j, ( i -> j).
, n i
j, w . n-1
i w j,
i j , , n-1 w
j, i. , n
n-1 .
: T(n,i,j,w) = T(n-1,i,w,j), T(1,i,j,w),
T(n-1,w,j,i).
i n-1 w n-1 j
+ | -------->-+|+--------->+ |
n-1| | I ||| | |
+ / \ / \ / \
+-/-----\-+ / \ +-/-----\-+
==+----|----+===/=========\====+----|----+======
+-------------->-------------+
.32. .
, n
, n.
tn(n,i,j,w),
, n i j
w {i,j,w} = {1,3,2}.
/* */
#include
main() /* */
{ void tn(int, int, int, int); /* */
int n;
scanf(" %d",&n);
tn(n,1,2,3);
}
void tn(int n, int i, int j, int w) /* */
{ if (n>1) /* */
{ tn (n-1,i,w,j);
tn (1,i,j,w);
tn (n-1,w,j,i);
}
else printf(" \n %d -> %d",i,j);
return ;
}
tn m=3
.33. tn n, i, j,
w . tn
, n, i, j, w,
, n, i, j, w ,
.
+-------+
|3,1,2,3|
+---+---+
+---------------|--------------+
+---+---+ +---+---+ +---+---+
|2,1,2,3| |1,1,3,2| |2,2,3,1|
+---+---+ +-------+ +---+---+
+---------|---------+ 1->3 +---------|---------+
+---+---+ +---+---+ +---+---+ +---+---+ +---+---+ +---+---+
|1,1,3,2| |1,1,2,3| |1,3,2,1| |1,2,1,3| |1,2,3,1| |1,1,3,2|
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+
1->3 1->2 3->2 2->1 2->3 1->3
.33. tn.
,
.
, :
main() /* */
{ ... f() ...}
f() /* */
{ ... f() ...}
main f.
f , ..
f.
f 1,2,...,s,
V1,V2,...,Vt main f k f.
:
- AR1,AR2,...,ARs,
f (
1,2,...,s);
- rz f (
f);
- ,
f, lr int, ,
pst ,
;
- dl ;
- u ;
- k L1,...,Lk ;
- jf,
f;
- l int
.
f,
:
1. f main;
2. main AR1,AR2,...,ARs,RZ,
ST dl u:
typedef struct st { P1;P2;...;Ps;V1;V2;...;Vt;
int lr; struct st *pst } ST;
ST *dl=NULL, *u;
3. f .
:
) f;
)
:
goto jf;
f: a=malloc(sizeof(ST));
a->P1=AR1; a->P2=AR2; ... ;a->Ps=ARs;
a->lr=l; a->pst=dl; dl=a;
) f JF,
, ;
) return(y) f
:
RZ=y; l=dl->lr;
a=dl; dl=a->pst; free(a);
switch(l)
{ case 1: goto L1;
case 2: goto L2;
...
case k: goto Lk;
}
4. i- f ( ,
f) V=f(A1,A2,...,As) :
AR1=A1; AR2=A2; ... ; ARs=As; l=i; goto f;
Li: V=RZ;
l=i l=1 f, l=2
..
switch goto
Li; ( Li L1 , Li L2
..)
5. f
main.
, :
+ X+1, N=0
| X, N=1, Y=0,
| 0, N=2, Y=0,
A(N,X,Y)= | 1, N=3, Y=0,
| 2, N=>4, Y=0,
+ A(N-1,A(N,X,Y-1),X), N#0, Y#0;
N,X,Y - .
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);
}
}
|
|
|