[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] RE: Fibonacci & XSL
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: 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
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|