Subject: RE: [xsl] Fibonacci & XSL From: "Jason Macki" <jmacki@xxxxxxx> Date: Tue, 17 Dec 2002 10:11:41 -0600 |
To solve this problem in linear time, do it from the bottom up, not from the top down. For example, if you wanted to calculate f(6) dynamically, start with 0 and work up to 6 using the results of the previous two calculations. F(0) = 1 F(1) = 1 F(2) = f(1) + f(0) = 2 F(3) = f(2) + f(1) = 3 F(4) = f(3) + f(2) = 5 F(5) = f(4) + f(3) = 8 F(6) = f(5) + f(4) = 11 -----Original Message----- From: Kasper Nielsen [mailto:news@xxxxxx] Sent: Tuesday, December 17, 2002 5:19 AM To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx Subject: [xsl] Fibonacci & XSL This is actually more a question of dynamic programming in XSL. If you can't remember the function it is: F0 = 0 F1 = 1 f(n)=f(n-1)+f(n-2) for n>=2 is it possible to make a template that calculates this in linear time (I know it can be done in O(lg n) but linear is enogh) in xsl? The straightforward recursive method for calculating f(n) is clearly exponential in n. If it is possible I would prefer an example using memoization because I need it to a similar problem I have. regards Kasper XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
RE: [xsl] Fibonacci & XSL, Yates, Danny (ANTS) | Thread | RE: [xsl] Fibonacci & XSL, Yates, Danny (ANTS) |
RE: [xsl] Fibonacci & XSL, Yates, Danny (ANTS) | Date | [xsl] output method html doesnt wor, Andrew Welch |
Month |