C++ Loops Lesson 11 - Fibonacci Sequence (2023)

Introduction

Content

Program here is going to involve the creation of a very famous mathematical sequence of numbers called the Fibonacci sequence.

The Fibonacci sequence is commonly used in explaining the rates of growth.

It shows up a bunch of nature.

This is quite famous so here's how it works.

The Fibonacci sequence starts with these two values, 0 and 1.

These are the first two numbers of the sequence then the rule for each each number that follows that second number, which is 1 is each number is the sum of the previous two.

So in this example, when the sequence would start with 0 and 1, and then the number that would follow, it would be 0 plus 1, which would be 1.

The number that follows that 1 is 1 plus 1, which is 2 the number which follows this is 1 plus 2, which is 3.

The number that follows is 2, plus 3, which is 5.

The number that follows is 3 plus 5, which is 8 and then 13 and then 21 and then 34 and then so on and so on.

And so on.

Yeah, the numbers do get quite large very quickly.

So what we want to do is we want to create a program that will display these numbers because imagine that you were doing a real life example.

And then for some reason you needed to access the 100th number of the Fibonacci sequence.

So you can't use a formula to figure out what it is.

This is just a perfect example of a looot loop.

So you're, not gonna you know, take your calculator out and start adding numbers together 100 times until you get it.

You would write a quick computer program, which is much faster than adding a numbers together, a hundred times and then it's going to look something like this.

So what we're going to do is we're going to start with two numbers, n1 and n2.

These are going to be 0 and 1 initially and then we're going to generate a third number.

So the third number is going to be n3 and then we'll carry on from here.

So let's set our initial value.

So n1 is going to be 0, and then m2 is going to be 1, and then we'll start our sequence from here.

So that in order to display the full thing, we need to display these two values here.

So let's see out and one with followed by a space I'm going to display them all on one line.

Instead of vertically, it'll, just look a little cleaner, see out and two we'll put a space here as well.

And then we'll start our loop.

We've displayed the numbers 0 and 1 I can run it just to show you what we've got so far I've got 0 and 1.

And then all of the numbers are going to be arranged on this one line.

So what I want to do is I want to get the first 10 numbers.

So what I want to do is I want to write an appropriate for loop for this move this up so it's easier for you to see.

But what I want to do is I want to think of the logic of what I'm doing as I'm considering the way that I write this for loop.

So the the one change that I want to consider is now I want the first 10 numbers I've already displayed the first two numbers.

So I could have this go from 1 to 8 because I know that I will have 8 more numbers to display.

However, the logic that I want to do is the next number that I will be displaying is the third number so I'm going to start my counter at three instead of one because I know that the next thing that the loop is doing is going to be kind of like the third step of the process so I'm going to honor that by putting three and I'll show you the reason why I do that is imagine that I for this program, we're going to display the first ten, however, if I needed to change the program and display the first 15 or so I would put that value here.

So I'm gonna put while I is less than or equal to ten.

So if I reduced it by two and left this at eight and went from one to eight, then any new value that I would want to put in I would have to remember, oh, yeah, reduce to reduce by two because I've already displayed to the values.

So I'm gonna go from three to ten, you go I, plus plus I'm, ready to go.

Okay.

So the new number, the new number in three is going to be equal to the sum of the previous two.

So the previous two number in this example, are n 2 and N 1 I, don't space, those out so I've got n 2.

And n 1 are going to form the results for n 3 and then I want to display and three I'm gonna do it in the same fashion as the earlier.

Two I, just realized I put in 2 here, let's put n 3 there, instead so we're going to then display n 3.

Now what I have to do is I have to prepare all of the values.

So that I can get the following number in the sequence.

So what I have to do is I essentially have to shuffle all of the numbers down.

So if we look at the example at the top, imagine that I just got the number 5 by adding together, three and two.

But now when I'm getting eight I need to essentially discard the two I, don't care about anymore, and then I'm going to be looking at the three and the five instead so here's how this is going to work the first thing that we need to do is and one is going to get the value of n2.

So we're gonna pull it down one level and then we're going to have n2 is going to get the value of and three.

And then our program is ready to go.

So every time you go through the loop, it's going to shuffle these down.

Now, if you don't understand what the loop is doing, please, pause, the video and trace the variables through the loop, anytime you encounter a loop that you don't understand, you should be tracing the variables so do a little walkthrough of the loop.

And that is the only way to familiarize yourself with what the loop is doing.

If you can't immediately, see what the loop is doing so let's, take a look at what happens when we run this.

So we're gonna get the first ten values.

And there we go.

We go all the way up to 34 now again.

This is why I did this I didn't? Go one to eight I, went three to ten because I have ten values here.

And if I wanted to take a look at value, 15 all the way up to 15 I can run that again, and then I get all the way up to value 15.

Now what would happen in the alternate scenario where instead of taking a look at the first 15 numbers? What we wanted to do was we wanted to go until we get a particular number reached.

So imagine I wanted to go to the number one and that's what we're going to write next.

So we're gonna redo this loop on the next line.

So we're gonna do an end L here.

You know, what let's put two of them just.

So we get a little bit of spacing between this we're going to reinitialize.

Our n1 is going to be 0, and then n2 is going to be 1.

So we're gonna reinitialize those two values and 3.

We don't really care about because we're going to be recalculating it.

The first time we go through the loop.

Now, I want to go to the number 1000, which I feel like I could estimate by looking at this sequence, roughly how many more times it would take to get to a thousand, but computers are terrible with estimating values by looking at a set.

We we'd have to put a bunch of extra programming, and that would get it to do that.

So in this scenario, we do not know how many times how many numbers from the sequence.

It will take to get to the number 1000 so we're going to find out so here's, how it's gonna work let's do a while loop and we're gonna keep going while n3 is less than or equal to a thousand.

So we're gonna go up to that value.

And then the content of the loop is the same.

So if you want to save yourself some time, you can copy and paste that down there.

And then here we've got another loop that goes up to the value, 1000.

So let's run the program, and then we're gonna see both scenarios there we go.

So what I did was I wanted it to go all the way up something that would be at least a thousand and then stuff.

Now, if we take a look at this, oh my gosh, I, didn't display items, 1, & 2.

So we should put in these two lines.

I will add that to my sequence there we go so I'll run that again.

So we've got 1 2, 3, 4 5, 6, 7, 8, 9 10, 11, 12, 13, 14, 15, 16, 17, 18.

We've got 18 values here.

Now it would have been really difficult to figure that out.

And imagine we were looking for say, a number that was a million, you know, keep going until you get a number that's over a million how many numbers would we need.

We have no idea.

So this is why it's a really good idea to have a while loop for this kind of scenario.