Re: general algorithm + ackermann question

If I interpret your (somewhat mangled ;-) terminology correctly, what
the assignment is asking you to do for a "dynamic solution" is fill in
a 2d table indexed on m and n and sized according to the "topmost"
values of m and n in the recursion. Fill in m=0,1,2 and n=0, which is
easy. Then do the rest of the table in an order such that you only
look at entries already filled in. After you have worked that out,
you'll see that you only need to keep a couple of rows of the table
around because the recursion never looks back by more than one row.
Other economies are likely to exist. I'll let you work them out.

Yeah, I guess I did get a big "mangled". Sorry about that...made
since at the time. Hey, I'm trying though and I was up front about
this being homework and never asked for a solution...just direction.
I appreciate everyone's help.

Anyway, within the same assignment, I had to do a dynamic Fibonacci
function. I wrote a correct Fibonacci function, but it wasn't really
dynamic. So I got myself into trouble in by using it as an example of
how to do the dynamic Ackermann.

I'm sure there are better ways to do this, but I came up with this:

long[,] dynAckTable = new long[4, 14000];
long dynAck(long m, long n)
{
if (dynAckTable[m, n] > 0)
{
return dynAckTable[m, n];
}
else
{
if (m == 0)
{
dynAckTable[m, n] = n + 1;
}
else if (n == 0)
{
dynAckTable[m, n] = dynAck(m - 1, 1);
}
else
{
dynAckTable[m, n] = dynAck(m - 1, dynAck(m, n -
1));
}

return dynAckTable[m, n];
}


}

It works, but so far not past A(3,10) . There was mention of just
having to keep a couple of rows of the table at a time. It seems as
if that would solve my problem of going past A(3,10).

Thanks again,

Jason
.

Relevant Pages

  • Re: print 1 to n without any conditional statement, loop or jump.
    ... If he wants you to use recursion, he should have given you that hint ... that this thing is between two friends, ... programmer(rather student) of C. ... Its not my assignment nor homework. ...
    (comp.lang.c)
  • Re: Recursion Usage and Concepts - Newbie Question
    ... I'm struggling with an assignment that involves using a 'quicksort' ... use of recursion is a requirement of this assignment. ... question my pursuit of using static methods. ... Another paradigm that uses recursion is Dynamic Programming. ...
    (comp.lang.java.programmer)
  • Re: Program shuts down computer
    ... > I'm working on an assignment to develop a sort algorithm. ... > recursion can cause strange problems, but I don't think that's what's ...
    (comp.programming)
  • Program shuts down computer
    ... I'm working on an assignment to develop a sort algorithm. ... recursion can cause strange problems, but I don't think that's what's ... Jeez -- if I could only figure out how to do this on purpose I'd have a real ...
    (comp.programming)
  • Recursion Usage and Concepts - Newbie Question
    ... I'm struggling with an assignment that involves using a 'quicksort' ... use of recursion is a requirement of this assignment. ... few examples of other ppl's recursive Java routines, ... question my pursuit of using static methods. ...
    (comp.lang.java.programmer)