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 EndFibonacci NumbersA simple example of program designPurpose of this presentation•The 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 program•The example we use is writing a program to compute and display a Fibonacci sequenceFibonacci sequences•A Fibonacci sequence is an infinite list of integers•The first two numbers are given–Usually (but not necessarily) these are 1 and 1•Each 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 sequence•We 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 step•We 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 names–If we use a loop, we must reuse namesPreparing for another step•This computation gave us our third number: int next = first + second;System.out.print(next + " ");•The sequence so far is: first second next–To get another number, we need second + next–Variable first is no longer useful for anything–Let’s move values around so that first + second does the job we needPreparing to make many steps•We 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 stop•Suppose we stop when we get to a number that’s 1000 or bigger•So 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?One other minor detail•We have been printing the numbers all on one line•We’ll get to 1000 quickly enough, so we won’t have a terribly long line•For 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 bug•The 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 yet–next 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) { // oops--a bug next = first + second; System.out.print(next + " "); first = second; second = next;}System.out.println( );Finishing up•We have the commands we need, but we do not have a complete application•We need to put the commands into a method•We need to put the method into a class•The 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
View Full Document