Matlab Tutorials | Examples
Practice 6:
Loops: Fibonacci Greatest Common Divisors
The Fibonacci numbers are Nature’s numbering system. Given the first two Fibonacci numbers, f0=0 and f1=1, all remaining Fibonacci numbers can be derived iteratively by making use of the following formula:
f(n)= f(n-1) + f(n-2) The first few terms of the series goes as follows:
|
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
fn |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
34 |
55 |
89 |
144 |
233 |
377 |
As the series goes to infinity, the ratio between adjacent terms converges to roughly 0.618034, an irrational number called the “golden ratio” or the “divine proportion.”
The Fibonacci sequence and the Golden Ratio appear in many systems around us, from the geometry of the DNA molecule (and the human body), to the physiology of plants and animals, even to the collective behaviour patterns of investors on financial markets. See http://www.world-mysteries.com/sci_17.htm for more information.
An interesting observation is that the greatest common divisor (GCD) of any two Fibonacci numbers appears to be another Fibonacci number. Look at the following examples:
gcd(f6, f9) = gcd(8, 34) = 2= f3 gcd(f6, f12) = gcd(8, 144) = 8= f6 gcd(f7, f14) = gcd(13, 377) = 13 = f7 gcd(f10, f7) = gcd(55, 13) = 1= f1
Write a MATLAB program that does the following:
- Gets two positive integer numbers, m and n from the user. If either number is not a positive integer, asks for that number again, until a proper value is given.
- Using loop constructs finds the mth and nth Fibonacci numbers fm and fn (do NOT use built-in MATLAB functions; do NOT utilize arrays).
- Finds the greatest common divisor of fm and fn, by making use of loop constructs (do NOT use built-in functions for finding the GCD or factoring the numbers; do not utilize arrays; use of basic functions such as MOD(), REM(), FLOOR(), etc. are permitted).
- Determines whether the GCD value is another Fibonacci number fk. If so, prints the k value on the screen, if not, displays “GCD property of Fibonacci numbers refuted!” (do NOT use built-in MATLAB functions; do NOT utilize arrays).
- Asks the user if s/he wants to try another pair. If yes, does the same operation again from step 1, otherwise quits the program.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
clc clear all again = true; %%Condition of the outer while loop which making decision work again code while(again) value = 1; %%Initilization of the output m = input('Enter first positive integer: '); %% Inputs for first number while(m<=0) || (m~=ceil(m)) %% Checking the positive integer disp('This is not a positive integer!') m = input('Enter first positive integer: '); end %%%----------Calculating First Fibonnaci Numbers----------%%% f3 = 0; if m==1 f3 = 1; end f1 = 0; f2 = 1; for i = 1:m-1 f3 = f1 + f2; f1 = f2; f2 = f3; end %%%----------END----------%%% n = input('Enter second positive integer: '); while(n<=0) || (n~=ceil(n)) disp('This is not a positive integer!') n = input('Enter second positive integer: '); end %%%----------Calculating Second Fibonnaci Numbers----------%%% f3a = 0; if n==1 f3a = 1; end f1 = 0; f2 = 1; for i = 1:n-1 f3a = f1 + f2; f1 = f2; f2 = f3a; end %%%----------END----------%%% %%%----------Checking which fibonnaci output is smaller----------%%% if(m>n) divider = f3a; %%Make them divider temp=n; else divider = f3; temp=m; end %%%----------END----------%%% %%%----------Decreasing the divider for the GCD----------%%% while(mod(f3,divider)~=0) || (mod(f3a,divider)~=0) divider = divider -1; end if(divider == 1) value = 2 ; else %%%----------END----------%%% %%%----------Calculating New Fibonnaci Number----------%%% f1 = 0; f2 = 1; f3b = 0; counter = 0; while(f3b ~= divider) f3b = f1 + f2; f1 = f2; f2 = f3b; value = value +1; end end %%%----------END----------%%% %%%----------Printing output and asking try another or not----------%%% fprintf('The GCD of Fibonacci numbers f(%g) and f(%g) is f(%g).\n',m,n,value); choose = input('Do you want to try another pair (y/n)? ','s'); switch choose(1) % switch expression case {'Y','y'} %Case expressions two type again = true; case {'N','n'} again = false; disp('Goodbye !'); otherwise disp ('Invalid selection. It must be one of (Y,y / N,n)'); disp('Goodbye !'); again = false; end %%%----------END----------%%% end |