00001 #include "MusimatTutorial.h" 00002 MusimatTutorialSection(B0126) { 00003 Print("*** B.1.26 Fibonacci Numbers ***"); 00004 /***************************************************************************** 00005 00006 B.1.26 Fibonacci Numbers 00007 00008 In the sequence 00009 00010 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 377, 610, 987, 1597, 2584, . . . 00011 00012 each subsequent term is the sum of its two immediately preceding values. For example, 8 = 5 + 3. 00013 This series, invented by Leonardo Pisano Fibonacci (1170-1250), is the solution to a problem he 00014 posed in his book "Liber Abaci": "A certain man put a pair of rabbits in a place surrounded on 00015 all sides by a wall. How many pairs of rabbits can be produced from that pair in a year if it is 00016 supposed that every month each pair begets a new pair which from the second month on becomes 00017 productive?" 00018 00019 An iterative method of computing the Fibonacci sequence is shown below 00020 in function iterFib(). 00021 *****************************************************************************/ 00022 00023 para1(); // Step into this function to continue the tutorial 00024 para2(); // Step into this function to continue the tutorial 00025 } 00026 00027 Integer iterFib(Integer n) { 00028 Integer fn1 = 1; 00029 Integer fn2 = 1; 00030 Integer result = 1; 00031 00032 For (Integer i = 2; i < n; i = i + 1) { 00033 result = fn1 + fn2; 00034 fn2 = fn1; 00035 fn1 = result; 00036 } 00037 Return (result); 00038 } 00039 00040 Static Void para1() { 00041 00042 /***************************************************************************** 00043 Executing the following For loop, 00044 *****************************************************************************/ 00045 00046 For ( Integer i = 1; i < 10; i = i + 1 ) 00047 Print(iterFib(i)); 00048 } 00049 00050 /***************************************************************************** 00051 prints the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34. 00052 Below is a method that accomplishes the same calculation using recursion: 00053 *****************************************************************************/ 00054 00055 Integer recurFib(Integer n) { 00056 If (n == 1 Or n == 2) 00057 Return(1); 00058 Else 00059 Return (recurFib(n - 1) + recurFib( n - 2)); 00060 } 00061 00062 Static Void para2() { 00063 00064 /***************************************************************************** 00065 The recursive technique has crisper expressive power than the iterative approach because we see 00066 the inner structure of the sequence directly in the method of its construction. However, it is com- 00067 putationally much more expensive, especially for large n, because we must call the recurFib() 00068 method twice at each step, whereas iterFib() performs only one addition and minor data 00069 shuffling at each step. Here is an example where Knuth's "goodness" criterion depends upon con- 00070 text. If efficiency is paramount, the iterative approach is preferred; recursion is preferable if 00071 expressive crispness is most important. 00072 00073 The Fibonacci sequence becomes relevant musically when we examine the ratios of subsequent 00074 terms: 00075 00076 1 2 3 5 8 13 00077 -,-,-,-,-,--, ... 00078 1 1 2 3 5 8 00079 00080 The corresponding sequence of quotients is 00081 00082 1, 200, 1.500, 1.670, 1.600, 1.625, 1.619, 1.617, 1.618, . . . 00083 00084 Thus we see that the ratio of adjacent Fibonacci numbers converges rapidly to the value of the 00085 golden mean, phi. The Greek letter phi is commonly used to stand for the golden 00086 mean. This number appears in a wide range of natural designs, including the arrangements of petals 00087 in flowers, seed clusters, and pine cones. Studied at least since Euclid wrote his Elements, the 00088 golden mean has appeared consciously and unconsciously as a central design element in countless 00089 musical works (see section 9.16.1). 00090 *****************************************************************************/ 00091 00092 For (Integer i = 1; i < 10; i++) 00093 Print(recurFib(i)); 00094 00095 /***************************************************************************** 00096 prints the same sequence. It is useful to watch recurFib() compute using 00097 a debugger because you can see how it recursively enters itself with 00098 ever-changing values. 00099 00100 *****************************************************************************/ 00101 } 00102 00104 /* $Revision: 1.3 $ $Date: 2006/09/05 08:03:08 $ $Author: dgl $ $Name: $ $Id: B0126.cpp,v 1.3 2006/09/05 08:03:08 dgl Exp $ */ 00105 // The Musimat Tutorial © 2006 Gareth Loy 00106 // Derived from Chapter 9 and Appendix B of "Musimathics Vol. 1" © 2006 Gareth Loy 00107 // and published exclusively by The MIT Press. 00108 // This program is released WITHOUT ANY WARRANTY; without even the implied 00109 // warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00110 // For information on usage and redistribution, and for a DISCLAIMER OF ALL 00111 // WARRANTIES, see the file, "LICENSE.txt," in this distribution. 00112 // "Musimathics" is available here: http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=10916 00113 // Gareth Loy's Musimathics website: http://www.musimathics.com/ 00114 // The Musimat website: http://www.musimat.com/ 00115 // This program is released under the terms of the GNU General Public License 00116 // available here: http://www.gnu.org/licenses/gpl.txt 00117 00118
1.7.2