手工带入数据具体体会过程，易于理解并选择栈来处理递归问题
2. m = 3, n = 4时候 如果栈大小只为100的时候，是不够用的
（这个开始发现不了 是后面突然想到的，复杂度的问题）

01 typedef int Type;

02 #include

03 #include

04 #include

05 #define ERROR 0

06 #define OK 1

07 www.2cto.com

08 int Akm_Recur(int m, int n)//对于递归来说 本身就是一个压栈的过程，直接易懂

09 {

10 if (m == 0)

11 return n + 1;

12 else if (n == 0)

13 Akm_Recur(m - 1, 1);

14 else

15 Akm_Recur(m - 1, Akm_Recur(m, n - 1));

16 }

17

18 int Akm(int m, int n)//建立空栈 数据入栈用于保存 先入后出符合条件

19 {

20 int result = 0;

21 int len = 0;

22 Stack S;

23

24 Creat(&S);

25

26 do

27 {

28 while (m)

29 {

30 while (n)

31 {

32 Push(&S, m - 1);

33 len ++;

34 n -= 1;

35 }

36 n = 1;

37 m -= 1;

38 }

39

40 if (!Isempty(S))

41 {

42 Pop(&S, &m);

43 n += 1;

44 }

45 }while((m != 0) || (Isempty(S) != OK));

46

47 return n + 1;

48 }

49

50 int main()

51 {

52 int m, n;

53 int result;

54

55 while (1)

56 {

57

58 title: test Akm(3_27)

59 scanf("%d%d", &m, &n);

60 result = Akm_Recur(m, n);

61 printf("%d ", result);

62 result = Akm(m, n);

63 printf("%d\n", result);

64

65 }

66 return 0;

67 }

view sourceprint 001 #include

002 #include

003 #include

004 #define MAX 10000

005 #define IN 10

006 #define ERROR 0

007 #define OK 1

008

009 typedef struct stack

010 {

011 Type *base;

012 Type *top;

013 int size;

014 }Stack, *LinkStack;

015

016

017 void Creat(LinkStack S)

018 {

019 S->base = (Type *)malloc(sizeof(Stack) * MAX);

020 if (!S->base)

021 exit(0);

022 S->top = S->base;

023 S->size = MAX;

024 }

025

026 int Push(LinkStack S, Type c)

027 {

028 if (S->top - S->base >= S->size)

029 {

030 S->base = (Type *)malloc(sizeof(Stack) * (S->size + IN));

031 if (!S->base)

032 return ERROR;

033 S->top = S->base + S->size;

034 S->size += IN;

035 }

036 *(S->top++) = c;

037 return OK;

038 }

039

040 int Pop(LinkStack S, Type *c)

041 {

042 if (S->top == S->base)

043 return ERROR;

044 *c = *(--S->top);

045 return OK;

046 }

047

048 int Gettop(Stack S, Type *c)

049 {

050 if (S.top == S.base)

051 return ERROR;

052 *c = *(S.top - 1);

053 return OK;

054 }

055

056 int Isempty(Stack S)

057 {

058 if (S.top == S.base)

059 return OK;

060 return ERROR;

061 }

062

063

064 void Clear(LinkStack S)

065 {

066 S->top = S->base;

067 }

068

069 void Destroy(LinkStack S)

070 {

071 free(S->base);

072 }

073

074 int PrintT(Stack S)//栈顶输出

075 {

076 Type e;

077 if (Isempty(S))

078 return ERROR;

079 while (S.top != S.base)

080 {

081 if (Pop(&S, &e))

082 printf("%c ", e);

083 }

084 putchar('\n');

085 return OK;

086 }

087

088 int PrintB(Stack S)//从栈底输出

089 {

090 Type e;

091 Stack SD;

092

093

094 if (Isempty(S))

095 return ERROR;

096

097 Creat(&SD);

098 while (S.top != S.base)

099 {

100 if (Pop(&S, &e))

101 Push(&SD, e);