Fibonacci NumbersPurpose of this presentationFibonacci sequencesStarting the Fibonacci sequenceTaking the next stepPreparing for another stepPreparing to make many stepsThe program so farDeciding when to stopOne other minor detailSlide 11Fixing the bugThe (fixed) program so farFinishing upThe “box” our program goes inThe complete final programThe EndJan 14, 2019Fibonacci NumbersA simple example of program designPurpose of this presentationThe whole point of this presentation is to give you some idea of how to put together the components we have so far (declarations, assignments, if and while statements) into a working programThe example we use is writing a program to compute and display a Fibonacci sequenceFibonacci sequencesA Fibonacci sequence is an infinite list of integersThe first two numbers are givenUsually (but not necessarily) these are 1 and 1Each subsequent number is the sum of the two preceding numbers: 1 1 2 3 5 8 13 21 34 55 89 144 ...Let’s write a program to compute theseStarting the Fibonacci sequenceWe need to supply the first two integers int first = 1;int second = 1;We need to print these out: System.out.print(first + " ");System.out.print(second + " ");We need to compute and print the next number: int next = first + second;System.out.print(next + " ");Taking the next stepWe need to compute and print the next number: int next = first + second;System.out.print(next + " ");Now what?We don't want to make up a lot more namesIf we use a loop, we must reuse namesPreparing for another stepThis computation gave us our third number: int next = first + second;System.out.print(next + " ");The sequence so far is: first second nextTo get another number, we need second + nextVariable first is no longer useful for anythingLet’s move values around so that first + second does the job we needPreparing to make many stepsWe need to make these moves:We can do it like this: first = second;second = next;We can put these statements in a loop and do them as many times as we pleasefirst second nextfirst second nextfirst second next 1 1 2 1 2 3 2 3 5 3 5 8The program so farint first = 1;int second = 1;System.out.print(first + " ");System.out.print(second + " ");while ( ? ? ? ) { // when do we stop? int next = first + second; System.out.print(next + " "); first = second; second = next;}Deciding when to stopSuppose we stop when we get to a number that’s 1000 or biggerSo we continue as long as the number is less than 1000: while (next < 1000) { ... }Question: is the final number printed greater than 1000 or less than 1000?while (next < 1000) { int next = first + second; System.out.print(next + " "); first = second; second = next;}One other minor detailWe have been printing the numbers all on one lineWe’ll get to 1000 quickly enough, so we won’t have a terribly long lineFor neatness’ sake, we really ought to end the line (rather than hoping Java does it for us): System.out.println( );The program so farint first = 1;int second = 1;System.out.print(first + " ");System.out.print(second + " ");while (next < 1000) { int next = first + second; System.out.print(next + " "); first = second; second = next;}System.out.println( );// oops--a bugFixing the bugThe first time we see the variable next, it’s in the test of the while loop: while (next < 1000) {next hasn’t been given a value yetnext hasn’t even been declared!Solution: declare next up with the other variables, and give it some reasonable initial valueThe (fixed) program so farint first = 1;int second = 1;int next = 2;System.out.print(first + " ");System.out.print(second + " ");while (next < 1000) { next = first + second; // "int" was removed System.out.print(next + " "); first = second; second = next;}System.out.println( );Finishing upWe have the commands we need, but we do not have a complete applicationWe need to put the commands into a methodWe need to put the method into a classThe next slide shows the extra stuff we need, but doesn’t explain itThe “box” our program goes inpublic class Fibonacci { public static void main(String args[ ]) { (code goes here) }}The complete final programpublic class Fibonacci { public static void main(String args[ ]) { int first = 1; int second = 1; int next = 2; System.out.print(first + " "); System.out.print(second + " "); while (next < 1000) { next = first + second; System.out.print(next + " "); first = second; second = next; } System.out.println( ); }}Our codeThe
View Full Document