自由行

2006-06-08

栈改递归

Filed under: 程序员 — thomas @ 16:33
递归旧问题
这个问题,距今有3年多了。不过我自己早就忘了,以前的工程也找不到了。只好自己重新新写。本以为是个很容易的问题。实际上却花了3个多小时。
先把代码贴出来,以后腾出时间再写总结。
/*——————————————————————-
http://topic.csdn.net/t/20030118/19/1372004.html
算法问题(栈改递归其它非递归方法也可!!)
liuxk99 (极地狐) 2003-01-18 19:32:13 在 C/C++ / C语言 提问
非递归算法实现一个函数.
f = n; (m <= 1)
f = m; (n <= 1)
f = f(m – 1, n) + f(m, n – 1); (m > 1, n > 1)
——————————————————————-*/
#include “stdio.h”
#include “string.h”
#include “windows.h”
#define TRUE 1
#define FALSE 0
#define STACK_SIZE 1000
typedef struct _st{
int m;
int n;
int bLeft;
int bRight;
int fpos; // 父节点
}st;
int f(int m, int n)
{
if (m <= 1)
return n;
else if (n <= 1)
return m;
else
return f(m – 1, n) + f(m, n – 1);
}
int fs(int m, int n)
{
int res = 0;
st stk[STACK_SIZE];
int pos = 0, x, y, lspos;
memset (&stk, 0, sizeof(stk));
stk[pos].m = m;
stk[pos].n = n;
stk[pos].bLeft = FALSE;
stk[pos].bRight = FALSE;
lspos = pos;
while (1)
{
if (stk[0].bLeft && stk[0].bRight)
break;
printf((“\r\nstack :”));
for (int i = 0; i <= pos; i++)
{
printf (” (%d, %d)”, stk[i].m, stk[i].n);
}
// get stack top
x = stk[pos].m;
y = stk[pos].n;
if (x <= 1)
{
lspos = stk[pos].fpos;
res += y;
stk[lspos].bLeft = TRUE;
printf (“\r\n%02d.Pop(%d, %d)”, pos, stk[pos].m, stk[pos].n);
–pos; // pop stack
//printf((“\r\nfs(%d, %d) = %d”, x, y, res);
}
else if (y <= 1)
{
lspos = stk[pos].fpos;
res += x;
stk[lspos].bRight = TRUE;
printf (“\r\n%02d.Pop(%d, %d)”, pos, stk[pos].m, stk[pos].n);
–pos; // pop stack
}
else
{
// pop stack
if (stk[pos].bLeft && stk[pos].bRight)
{
lspos = stk[pos].fpos;
if (pos – lspos == 1) // 分支判断
stk[lspos].bLeft = TRUE;
else
stk[lspos].bRight = TRUE;
printf (“\r\n%02d.Pop(%d, %d)”, pos, stk[pos].m, stk[pos].n);
–pos;
}
else
{
lspos = pos;
// push stack
printf (“\r\n%02d.Push(%d, %d)”, pos, x – 1, y);
++pos;
stk[pos].m = x – 1;
stk[pos].n = y;
stk[pos].bLeft = FALSE;
stk[pos].bRight = FALSE;
stk[pos].fpos = lspos;
printf (“\r\n%02d.Push(%d, %d)”, pos, x, y – 1);
++pos;
stk[pos].m = x;
stk[pos].n = y – 1;
stk[pos].bLeft = FALSE;
stk[pos].bRight = FALSE;
stk[pos].fpos = lspos;
}
}
}
return res;
}
int main(int argc, char* argv[])
{
int m = 5, n = 4, res = 0;
DWORD tc1, tc2;
tc1 = GetTickCount ();
res = f(m, n);
tc2 = GetTickCount ();
printf (“%d : f(%d, %d) = %d\r\n”, tc2 – tc1, m, n, res);
tc1 = GetTickCount ();
res = fs(m, n);
tc2 = GetTickCount ();
printf (“%d : f(%d, %d) = %d\r\n”, tc2 – tc1, m, n, res);
return 0;
}

Powered by WordPress