Lecture Notes on Iteration Using For-Statement in C++

[Music] what we wish to discuss as I mentioned is a new control statement in C++ called the false statement to implement iteration by Counting last thing we had hinted at that we will then use this false statement to solve two interesting problems one is to estimate the value of logarithm of a given value given number to the BC how many of you have heard of Riemann integral some people many okay five so we'll be we'll be using the Riemann integral submission to calculate that value how many of you heard of him general numbers none so that's a rather interesting problem they are the two problem that we wish to dismiss so first of all finding the sum of N numbers value of n is given as input now this is different from our real artificial end conditions which we used to put you remember when we wanted to sum some given numbers or we wanted to find out the maximum of given numbers we would artificially treat some specific number as end of input such as 0 so we said that we will run an iterative loop till the input value rate is 0 somebody had observed that suppose 0 itself is the value what do we do we said we can define a range of values and give an input which is outside that ray suppose we have to work with all possible values that can come in then we didn't know how to handle it in variable E in most counting problems you may have a bearing on how many terms you want to add of a sequence or how many values you want to add or how many values you want to handle then such is the case you will know that number in advance suppose that number is n and could be 5 thousand 1 million 200 whatever but once you have the n you know exactly how long the iteration has to wrap it has to run once twice thrice for etcetera and end times once you're finished in time you are done now if you look at the while control structure the while control structure says that as long as a given condition is true the iteration will continue now you have to recast this condition mechanism in the context of some counting that you will have to do for n times doing that iteration only there only in human life how do we do counting you take a child you say you have to do this five times so every time the child does it once we will say one and he said - and you say three four five done so basically the child is setting up a counting mechanism every time he does something he increases the count by one then two then three then four we need such a mechanic and what is the child's way of saying whether he has to continue or not he will look at the current count so it is four it says less than five I have to country in exactly the same fashion we need to execute a block of statements n times then we need a counting mechanism where we say we said some count equal to one arbitrary vision then we execute that iteration block increase count by one and repeat the block again execute that block increase count by one and repeat it obviously have to keep repeating the block till the current value of count is less than or equal to n when we finished it in its time then we will get out of the iteration how do we set this up using a while statement so I have shown here some statements like back bro notice that earlier we did not have anything called n now we will have n I have put it in blue but not see in greater greater it why because n need not always be obtained as input I could also assign a value it is equal to 53 so I want to do something 53 times I can even compute the value of n from some other expression which based on some previous computations in the program say that I know how to do these iteration so many times so there are multiple ways of obtaining L but having opt I now have the counting mechanism statements so one additional statement which is ultra visual completely there is nothing to do with our program is inserted they're called count equal to up next it says while count less than equal to n do the following so there is a block of statements which are to be repeated and after executing that block I want to say count is equal to count plus 1 now when I come out at the end of that block very obviously I will go back that's the nature of I and when I go back while we check the condition again but this time count will have become 2 I reiterate that again again count will increase I will go back out will become 3 then it will become 4 sometimes it will be equal to n but still a less iteration I have to continue so I will complete it count will be added by 1 and it will be greater than n then I go back this time the darvon will say sorry count is not less than equal to n get out and I will get up so it is a very simple mechanism please note I require certain artificial statements to implement iteration control by counting the first artificial statement is assignment to n the second ultra visual statement is actually the condition check the condition has nothing to do with what you are computing it has to do with counting so he is count less than equal to L then carry on otherwise get up and finally after the iteration block the last additional ultra visual instruction is incrementing the count so I increment the count by 1 there are radiations possible for example suppose I want to execute this iteration n times I start with count equal to 1 but I say whether higher count is less than equal to 2 star M some arbitrary I still want to execute the iteration n times what will I have to do well if I say count is equal to count plus 2 count will increase by 2 1 3 5 7 there could however be a problem depending upon whether n is all or even you can just cross-check that but there are variations possible we use this now to find some of n numbers so this is the program so it is starting with definition of integer a sum is equal to zero it is initialized n is defined and additionally I am defining int count notice that the first statement says gives number of values to be added by input n I said count equal to 1 while count is less than equal to n what do I have to do read a number and I need to sum so that is what saying into the next number inputted sum is equal to sum plus a that strictly is the iterative block that I have but additionally I say count is equal to count plus 1 so you agree that this program will do the needful it will add n given numbers this trick can be used to solve any problem so these are lists of problems adding a fixed number of terms of a sequence calculating average marks for a given number of students calculating factorial L this factorial L is an interesting problem you all know the definition of factorial n right I agree is the definition of factorial n the way we calculate it iteratively is very similar in principle to the way we accumulate some observe that in the previous example we had a very lower object called sum and we were adding values to it so every iteration some was changing okay by the way that is the reason why it is called iteration and not repetition the repetition is you merely repeat the same action again and again eater Asian is there every repetition causes something to change that is what is iteration and that is why the word iteration now here what should change so what we can do is we can have a location which will calculate let us say we call it fact and we will have another location which will have each of these terms one by one and I will keep multiplying that with fact instead of adding it to fact then I will get the cumulative product so I need to find a product actor now just as we start some equal to zero we should start some factor equal to one let us see if we're to find out factorial for what will happen here I have to now multiply this one successively by two three and four where will I get these numbers well it so happens that my counting mechanism is actually generating these numbers for count is initially 1 then 2 then 3 then 4 then 5 and so on so if I put count let's say this is my count initially this is 1 in the first iteration I multiply 1 by 1 is the artificial this thing nothing will happen this one will be replaced by 1 actually next I will increment count by 1 to 2 and in that iteration block if I multiply 2 with fact to get a new value of fat I will get 2 here next iteration the count becomes 3 I will get multiplied 3 with fact and replace the value of fat so effectively my statement is going to be fact is equal to fact star town I read that is though just as some is equal to some plus a value fact is equal to fact star count and the count is internally generated I do not have to depend on it so next time these three will become fourth I will multiply this 4 sorry first 3 and 2 is multiplied so this will have become 6 now count becomes 4 4 gets multiplied by 6 it becomes 24 and suppose I was to calculate for this 4 will now become 5 and next time when I come back for iteration it is a sorry 5 is greater than 4 get out so that is how I can simply calculate factorial here is a program which does that so you can see given number whose factor is needed I input M now I set up my counting mechanism count is equal to 1 while count is less than equal to n fact M is equal to fact n star count I have chosen to use the name fact M to represent factorial of some value and I add 1 to the count you all agree that this iteration will correctly calculate factorial L so it's very simple except that I need these artificial statements for setting up counting mechanism in exactly the similar way if I want to keep on doing some counting till L I look for some simpler mechanism unlike those abbreviations that I discussed where I advise please don't use them here is an abbreviation which is actually quite useful and very extensively used in C++ program this mechanism is called the false statement this false statement is a very spacious statement what that does is it permits you to define three things in one place in your program after all in counting mechanism what do we need we need an initial value we need a condition for continuation and we need an increment if we can prescribe all these three things typically at the beginning of the block and keep in mind the logic that while these three things are specified the first thing is that before you do anything in this block that is initialization of the cup the next thing you do the checking of the condition every time you come to the iteration and the last thing that specified which is the increment you do only when you completed one it so this is what it says the instruction permits us to define these three things and these actions are defined at the beginning of the iterative block so this is the nature of the false statement for in bracket this is important to note you write three things separated by semicolons the first thing is count equal to one typical specification for initial action the next thing is the condition for continuation of the top so that is count less than equal to n iteration will continue as long as this condition is valid and the last specification is count plus plus which is count equal to count plus one remember I said that stand alone such post pre increments can be used whether you say minus minus a plus plus count or plus plus it means the same thing here say stand alone and it is indeed used in this sense in almost all false statements that you see in professional problem is a simpler thing but do you see now although I am writing all the three things in one statement at the beginning of my creative block those actions do not take place at that point the actions take place exactly as depicted by the earlier do-while implement so that is why the explanation is written it initializes the count before beginning the first iteration at the beginning of each subsequent iteration to check that condition and permit continue execution of the iteration only if that condition is satisfied and at the end of every iteration it will increment the count immediately after the iteration and go back so that is the simplest implementation of it by counting here is a program written to add n numbers using for state notice the program is very similar to what we had seen earlier which were implemented using do-while but we had artificial constraints on what number to be input so that zero can be taken as it then today earlier we saw how by counting we could include implement this algorithm using high state this is an implementation using form so you will notice that after reading the number of numbers to be read here and I am actually setting up F for iteration so for count equal to one count less than equal to n count plus plus can you tell me what this will do now in the translated algorithm it will set up count equal to one just outside this iteration board that statement will be executed next the condition will be J is count less than equal to n of course one may be less than equal to n because n would be five ten five thousand whatever and if so the iteration will be executed what does the iteration say enter the next number and it is added to some observe that what we were earlier doing artificially by writing count equal to count plus 1 in our dowhile implementation need not be written because that is part of the specification of the false statement the third part here this count equal to count plus plus will actually be executed at this point in the algorithm after completing it so we yeah how many numbers do you wish to add inside that until next number to be added yes because pre increment or post increment does not make any difference it is going to be a standalone operation no not after all that after a particular expression is evaluated the expression is that itself so the moment that is evaluated the value changes after post and pre does not apply to block of statements post entry applies to the evaluation within an expression when the only thing in the expression is that the value will change whether it is pre or post yes I will see that later but the point is what we are stressing at this juncture is a simple counting mechanism I start with 1 I want to count 1 2 3 4 5 6 n this is the mechanism integer agreed so let us keep that in mind everybody understands now how to set up an iteration an important point here was the algorithm was wrong because there is no C out number which is not required because when you type it you see it yourself you are going to type it okay the the point is we are discussing counting mechanism and unfortunately we concentrated on n number of other errors which are there in the program but it just shows that you are understood how counting works and I take it for granted by look at this program this finds maximum of n given numbers again it is very similar to finding out some except that we are not adding anything to sum but we start with the max number notice that we have n numbers given in this so I take the first number outside the iteration to set up the right value of Max and notice that there is no artificial condition here which says that find out maximum of given n positive integers or something the number that comes in could be any number and therefore I cannot make any assumption on max so I read the first number assign it to max now I have only n minus 1 numbers left to read and that is why the iteration specifies for I count equal to 1 count less than equal to n minus 1 count plus sum of n natural numbers in exactly the same way that we calculated factorial n I do not need any input so I simply set up an iteration for I equal to 1 I less than equal to n I is equal to I plus 1 sum is equal to sum plus I so instead of count I am using an object I whose value is changing because of the false statement and I am adding in every iteration that value of I to count so count we'll start with some we'll start with zero then one will be added two will be added free will be added up to N and when n iterations are over the control will come out printing this up okay in exactly the same way the factorial can be found notice that in the previous example of the file iteration when we implemented factorial L we actually started with fact equal to 1 but we multiplied that 1 by 1 again which was not necessary since I presume that n is larger than 2 because you won't use a computer to find factorial 2 hopefully so it will be a number larger than 2 3 4 so I start with fact equal to n factorial equal to 1 this time I am using the name n n factorial and I start the iteration count from I equal to 2 to n now what will happen is n factorial will get multiplied by the current value of I which is 2 at the beginning then 3 then 4 then 5 I will complete up to n so this is yeah it will not have any impact how many times I have said that whether you write plus plus ion I plus plus as long as it is a standalone statement it is not part of any other expression there is no difference in the implementation plus plus I is same as I plus 1 I is equal to I plus 1 I plus plus is also same as I is equal to I plus 1 there is no difference between these two when it is a standalone statement it has an impact only if it is part of a larger expression 3x square plus plus plus I minus something something then only it has a different meaning so this is a state-level statement here although it is part of the false specification please remember 4 gives 3 specifications the initialization part the condition part and the increment part and these 3 are independent specifications they have nothing to do with each other so it is not considered part of a larger expression and therefore there is no conclude this question is important because you will find in many books programs which will use the counting mechanism as minus minus IR plus plus I and I use as AI plus and therefore some confusion could be possible but it should be avoided this is no confuse both will implement a increment by one is that is that okay no right now we come to the general format and semantics of the false statement but actually what you have these three parts of the specification has not necessarily three simple statements like count equal to 1 or count plus plus the initial part can be a series of specification called init group that condition however is only one that is the continuation can be give me complex candy and the last part is called increment group in that increment group several statements separated by comma can also be used in the initialization group several statements in they separated by comma can be used a comma is a separation operator in C++ and it effectively works as equivalent of semicolon it finishes one statement and starts the next day please note that in the increment group if you have prescribed two three four five actions separated by comma one of those actions could still be plus plus J or J plus plus and that will still be a standalone instruction so that it will not have any impact on the camping you can read these variations at home and figure out what they do particularly see the last one fall in bracket semicolon semicolon bracket closed what am I saying initial condition none condition to be checked for continuation none increment now nothing this is actually in finite row this is equivalent of saying while one carry on doing so this is equivalent of a in finite row that is the C++ interpretation there are other multiple options shown for example if increment conditional increment statement is not written at all nothing is incremented okay so obviously you have to do something has to change the condition otherwise you will never get out of it anyway since most of you know Riemann integral I think we can both to this particular problem very quickly we observe that the computer cannot do integral calculus it can only do computation of value and therefore if I have to evaluate an integral I go back to the basic definition of integral integral of a function is actually the area under the curve between the two limits where I want to integer now area can be approximated so I will have a large area for example this is my function calculate the area under the curve y equal to 1 by X we understand what is significance of y equal to 1 by X the area under this curve between 1 and ay is actually the natural logarithm of a so log of a to the base e is nothing but the area under this curve and I had to calculate this area now I cannot do the measurement and the curve and so on so forth in terms of computer calculations I will have to calculate this area by approximating it I assume that there is a series of rectangles that I have and I keep adding the area of each rectangle say if I have 20 30 50 100 rectangles then the sum of all the areas of those red eléctrica tangles will be an approximation of this area people used to do these things manually and it was impossible to calculate say sum of thousand rectangle areas like this but machine can be used to do that so this is what I wish to do these are the rectangles whose areas I want to calculate now you can see that if this is my rectangle then this has some height and some wealth if all the tangles are same then I know what is the width suppose there were 100 rectangles I decide to use between 1 and a what will be the width of each individual rectangle a minus 1 by 100 a minus 1 by hauser whatever that is the way that is fixed the height of any rectangle suppose I measure the height at this point now if I know this which is X corner then I know 1 upon X is this point I can do that for every such point so I can get the height and therefore I can get the weight thing too height which is the area so this is what is shown here if there are n rectangles width of each rectangle is a minus 1 by N and to find out the height first I find out the x-coordinate of Erik time now here the x-coordinate of first rectangle is 1 because this is the this is the x-coordinate of positive x coordinate of second rectangle is 1 plus w third rectangle 1 plus 2 w in general for is rectangle the x-coordinate will be 1 plus I minus 1 into W agree very simple derivation and if this is the value of the x-coordinate what is the height here is 1 upon this so that is what we have done height H of is rectangle which is equal to 1 by X which is 1 upon that entire expression so this is simple derivation no problem now I know the height I know the will of is rectangle I have such a lyric tenders can you not see that I can set up a four iteration in every iteration I take one rectangle where I is 1 2 3 4 5 N and keep on adding to some it is like summing n values except that values are not being input but values have been calculated area of is rectangle is explicitly counted as W into H which is W into 1 by X which is W into 1 upon 1 plus I minus 1 into W this is the simple derivation and my program therefore automatically writes itself first I have to decide how many how many rectangles we say thousand if it is thousand width of rectangles taken together there is a minus 1 there for width of each one is a minus 1 by thousand x coordinate is this height is this an area of the rectangle is this this is just a consolidation of whatever we have discussed so far nothing new in this law it is useful however to write such things before you start writing your program so you know exactly what you want and now we write this program so look at this problem observe that I am now generalizing the program to say I had thousand rectangles like this so what am i doing area is zero I define W I calculate W as a minus 1 upon thousand I of course input the value of a then I set up the four iteration what does that fall say for I is equal to one semicolon I less than equal to thousand semicolon I is equal to I plus 1 so that means please do the following block of statements one thousand times starting with the value of I equal to one then I equal to 2 I equal to 3 etcetera it is important what value I takes because we are using I explicitly never computation what is the computation area is equal to area plus W star 1 upon 1 plus I minus 1 style of exactly the same formula that will work now nothing else is to be written you can wonder later on whether you will get the correct calculation because there are a lot of 1 upon this and so on and if an integer division occurs somewhere your son you will notice however when you examine this that no such problem will happen because W is defined as float and therefore while I minus 1 will be integer when it is multiplied by W it becomes float when that is added to 1 that becomes float and when one is divided by that whole quantity that 1 will become 1 point 8 however those of you who wish to be more meticulous might write everyone has one point 0 just to be on the safer self there is no harm in doing but notice that my entire program although I am adding areas of thousand rectangles does not have the housing statement and if I won't take the machine to add 1 million rectangles my program will remain the same what will change the thousand would it not make sense then to further generalize this program and say that instead of thousand I will input some end from the user say how many how many rectangles we want to add tell me in fact maybe interesting I will display the results on Moodle by the of this program where I execute it for one hundred thousand and ten thousand and he can compare what is the value of actual log with with the values that you get there is a further interesting what should I say modification possible because when you add a rectangle area observe that a portion of the area above the curve also gets added now you can take the height of that rectangle not to be the starting point but the end point but then you will lose so instead of taking this height which causes this much portion to be extra you can take this I but that will cause reduction in that so one suggestion is you calculate the area of the rectangle taking the first height into account calculate the area of the rectangle taking the second height into account and take the average because that will give you half of the a perfect angle portion which is likely to be closer to the truth will it make a difference not if you are a thousand ten thousand rectangle you note that when you have all rectangles it is not that you are adding some meaningful portion of that curve at a later stage but you are actually making the width of every rectangle smaller and therefore the approximation will be more accurate will comment more on this but we understand how easy it is you can solve the problem of any integration between limits using this approach that's why it is the Riemann integral is important because it can be used in multiple places we will quickly look at this interesting problem the another problem called him general numbers the I am introducing this problem is not the original him general small the problem is suppose I have to build a wall of four feet long and in that wall I have to lay bricks but I have bricks of two kites one is one one foot brick and the other is to feed break so short break in a long break the question that is being posed is in how many different ways can I lay the bricks to make four feet length so here I have written the possibilities I can choose all four bricks of one foot long so I have one one valve man I can choose the first brick to be two feet long and the other ones sharp I can choose one two one I can choose one one two or I can choose two bricks which are two feet long agreed so these are the various possibilities how many possibilities do we notice here 1 2 3 4 5 actually an exercise in combinatory but suppose I ask this question in how many ways this can be done if the length is 3 feet or if the length is 5 feet I have written down here the combinations if I have a 3 feet length wall then any line of bricks will have either 1 1 1 or will have 2 1 or will have went to there is no other possibility for four feet wall we have already listed and for five feet wall I will have more combination these are exhaustive combination they have been written however in a spatial fashion so that you can identify some relationship between the previous possibilities for 3 feet tall at a 4 feet wall in the five feet wall one of those possibilities observe this in a 3 feet wall and a 4 feet wall I have all combinations of 3 feet wall with 1 one foot brick added to it that makes it four feet book I have originally some combinations I'm selling the possibilities are the five feet wall I have all the possibilities of the four feet wall and I did one foot break there so that all of them becomes the possibilities for five feet wall what are the additional possibilities in the five feet wall 1 1 1 2 2 1 2 1 2 2 notice that these three possibilities have a larger brick at the end but all the three possibilities if you remove that to algebraic come from the possibilities of 3 feet or 3 feet tall had one one one two one one two if I add 2 to it I get all the possibilities of 5 feet one so I noticed that possibilities for five feet wall is actually equal to the total number of posse it is 4/4 we'd wall by adding one foot break plus the total number of possibilities for three feet wall by adding it to fit me simple this is actually called a recurrence relation the original problem of the hem Chandra was a musical problem him general lived in 11th century in India and he said Voytek meter which is made of short syllables and long syllables so long syllable is two beats and short syllable is one here is an example of poetic meter somebody some of you might know this poem Yahoo an endo to Shara and Avila say char will be credited so these are the beats that you see that what him gender opposed the problem was if I am designing a poetic meter with eight beats how many ways are there to fill up these eight bits that was his mathematical problem and then he gave a solution in 1100 something he gave a solution he says by the method of ping girl it is enough to observe that the last beat is long or short Bingle had written this mathematical sutra he lived 200 before Christ 200 years before Christ came to the Rose 1100 years ad so this is an important point which preserve Rama day made his lecture three years ago and I make it every time copy if necessary and if permitted but give credit the very fundamental actual of professional life that is why you will find that when you write research papers and you quote whether somebody else has done something you always quote you cite that reference saying this I read it in this book or this place so that is I am NOT taking the credit somebody assisting is to be given liquid mingle I did by the way a whole lot of things and several of his sutra have subsequently been incorporated the point of the hymn Chandler solution now is that if by method of Pingala if I observe what is the last bit is longer short I can get the classification and eight bit pattern can be made of taken me seven bit pattern and add a short bit or take any six bit pattern and I'll a long wait just like the brick problem and this gives us a recurrence relation number of 8-bit patterns equal to the number of 7bit patters plus number of six bit patterns but I cannot solve this problem then I must no wonder the number of seven bit patterns of lol number of six meter number of seven bit patterns Intel is defined by number of 68 patterns and number of five bit so if I start backward I say H n which is the total number of patterns within bits H 8 will be H 7 plus h 6 in general HN is equal to HN minus 1 plus HN minus 2 this is called a recurrence relation and we need to know its seven and a six for which we need to know H five for which we need to know H four etcetera so you start always from the first thing H 1 number of patterns with one big only one say short bit H 2 number of patterns with two bits there are exactly two patterns possible s s and L nothing else is possible now you know H 1 and H 2 Bristow H 3 is equal to H 2 plus H 1 which is 2 plus 1 H 4 is equal to H 3 plus h 2 h 5 is equal to h 4 etcetera h n will be equal to now I have three values one value is the current H n which I want to compute one value is a previous value and one value is the mixed value which I want to compute so I have next current and previous suppose I set up an iteration in which I have these three locations current previous and next I initialize some value to current some value to previous which is H 1 and H 2 I can now calculate next which will be H 3 and if I now set up an iteration but before every iteration I keep shifting the well I will take the current value and put it in previous next value put it in current and go to the next iteration and if I keep on doing this I can generate in numbers in in this M generosity so this is the program the integer definition is used to define H 3 and H and there is a variable called H next I hope you understand the significance of these three names H brave is a previous value H current is the current value and H next is what I have to calculate these three locations initially contain one two and unknown one and two represent H 1 and H 2 respective ok now I set up an iteration for I equal to 3 I less than equal to n I plus plus I already taken in as input suppose M is 10 then the iteration will begin with I equal to 3 what will it do it will calculate H next is equal to H pre plus h correct these are three locations by the way they have nothing to do with that whatever with the value of I there will be only 3 location what will be the value of H makes that this time H next will be equal to first iteration the first iteration what will be the value H breve is 1 h current is 2 so 2 plus 1 3 its next will have a value 3 now for preparation of the next iteration I do not have to do anything about counting that is being done but I need to shift these values so that next time as 4 is calculated next time H 5 is calculated and all these calculations happen in a location called H next is that is this here so that's it these numbers generate mathematics from poetry and represent a extremely interesting model you might have heard of golden ratio successive terms the ratio of successive terms tends to that limit these are commonly known as Fibonacci numbers how many of you have heard of Fibonacci numbers all of you none of you knew about himself it is not uncommon to forget your own heritage when you start believe believing that anything great can only be done by friends and not by us you never look for old mathematical exploitation how many of you have tried to read yes real about whatever happened in this country whatever happened in the entire Middle East Fibonacci has admitted that he learned these things from an Arabian scholar in North Africa to whom he had gone to learn the Hindu numerals and such things the entire algebra for example was developed by Arabic scholars all of that is now treated as Western knowledge nothing wrong in it a whole lot of knowledge has been added by these scholars all across the world including Western scholars so the idea is not to belittle any effort but when your own heritage is so strong so did not interest you to know what is that and you don't have to read big history books just go to Wikipedia just us Indian mathematics just for your own interest I would suggest you read it I will close this thank you very much [Music]

[Music] what we wish to discuss as I mentioned is a new control statement in C++ called the false statement to implement iteration by Counting last thing we had hinted at that we will then use this false statement to solve two interesting problems one is to estimate the value of logarithm of a given value given number to the BC how many of you have heard of Riemann integral some people many okay five so we&#39;ll be we&#39;ll be using the Riemann integral submission to calculate that value how many of you heard of him general numbers none so that&#39;s a rather interesting problem they are the two problem that we wish to dismiss so first of all finding the sum of N numbers value of n is given as input now this is different from our real artificial end conditions which we used to put you remember when we wanted to sum some given numbers or we wanted to find out the maximum of given numbers we would artificially treat some specific number as end of input such as 0 so we said that we will run an iterative loop till the input value rate is 0 somebody had observed that suppose 0 itself is the value what do we do we said we can define a range of values and give an input which is outside that ray suppose we have to work with all possible values that can come in then we didn&#39;t know how to handle it in variable E in most counting problems you may have a bearing on how many terms you want to add of a sequence or how many values you want to add or how many values you want to handle then such is the case you will know that number in advance suppose that number is n and could be 5 thousand 1 million 200 whatever but once you have the n you know exactly how long the iteration has to wrap it has to run once twice thrice for etcetera and end times once you&#39;re finished in time you are done now if you look at the while control structure the while control structure says that as long as a given condition is true the iteration will continue now you have to recast this condition mechanism in the context of some counting that you will have to do for n times doing that iteration only there only in human life how do we do counting you take a child you say you have to do this five times so every time the child does it once we will say one and he said - and you say three four five done so basically the child is setting up a counting mechanism every time he does something he increases the count by one then two then three then four we need such a mechanic and what is the child&#39;s way of saying whether he has to continue or not he will look at the current count so it is four it says less than five I have to country in exactly the same fashion we need to execute a block of statements n times then we need a counting mechanism where we say we said some count equal to one arbitrary vision then we execute that iteration block increase count by one and repeat the block again execute that block increase count by one and repeat it obviously have to keep repeating the block till the current value of count is less than or equal to n when we finished it in its time then we will get out of the iteration how do we set this up using a while statement so I have shown here some statements like back bro notice that earlier we did not have anything called n now we will have n I have put it in blue but not see in greater greater it why because n need not always be obtained as input I could also assign a value it is equal to 53 so I want to do something 53 times I can even compute the value of n from some other expression which based on some previous computations in the program say that I know how to do these iteration so many times so there are multiple ways of obtaining L but having opt I now have the counting mechanism statements so one additional statement which is ultra visual completely there is nothing to do with our program is inserted they&#39;re called count equal to up next it says while count less than equal to n do the following so there is a block of statements which are to be repeated and after executing that block I want to say count is equal to count plus 1 now when I come out at the end of that block very obviously I will go back that&#39;s the nature of I and when I go back while we check the condition again but this time count will have become 2 I reiterate that again again count will increase I will go back out will become 3 then it will become 4 sometimes it will be equal to n but still a less iteration I have to continue so I will complete it count will be added by 1 and it will be greater than n then I go back this time the darvon will say sorry count is not less than equal to n get out and I will get up so it is a very simple mechanism please note I require certain artificial statements to implement iteration control by counting the first artificial statement is assignment to n the second ultra visual statement is actually the condition check the condition has nothing to do with what you are computing it has to do with counting so he is count less than equal to L then carry on otherwise get up and finally after the iteration block the last additional ultra visual instruction is incrementing the count so I increment the count by 1 there are radiations possible for example suppose I want to execute this iteration n times I start with count equal to 1 but I say whether higher count is less than equal to 2 star M some arbitrary I still want to execute the iteration n times what will I have to do well if I say count is equal to count plus 2 count will increase by 2 1 3 5 7 there could however be a problem depending upon whether n is all or even you can just cross-check that but there are variations possible we use this now to find some of n numbers so this is the program so it is starting with definition of integer a sum is equal to zero it is initialized n is defined and additionally I am defining int count notice that the first statement says gives number of values to be added by input n I said count equal to 1 while count is less than equal to n what do I have to do read a number and I need to sum so that is what saying into the next number inputted sum is equal to sum plus a that strictly is the iterative block that I have but additionally I say count is equal to count plus 1 so you agree that this program will do the needful it will add n given numbers this trick can be used to solve any problem so these are lists of problems adding a fixed number of terms of a sequence calculating average marks for a given number of students calculating factorial L this factorial L is an interesting problem you all know the definition of factorial n right I agree is the definition of factorial n the way we calculate it iteratively is very similar in principle to the way we accumulate some observe that in the previous example we had a very lower object called sum and we were adding values to it so every iteration some was changing okay by the way that is the reason why it is called iteration and not repetition the repetition is you merely repeat the same action again and again eater Asian is there every repetition causes something to change that is what is iteration and that is why the word iteration now here what should change so what we can do is we can have a location which will calculate let us say we call it fact and we will have another location which will have each of these terms one by one and I will keep multiplying that with fact instead of adding it to fact then I will get the cumulative product so I need to find a product actor now just as we start some equal to zero we should start some factor equal to one let us see if we&#39;re to find out factorial for what will happen here I have to now multiply this one successively by two three and four where will I get these numbers well it so happens that my counting mechanism is actually generating these numbers for count is initially 1 then 2 then 3 then 4 then 5 and so on so if I put count let&#39;s say this is my count initially this is 1 in the first iteration I multiply 1 by 1 is the artificial this thing nothing will happen this one will be replaced by 1 actually next I will increment count by 1 to 2 and in that iteration block if I multiply 2 with fact to get a new value of fat I will get 2 here next iteration the count becomes 3 I will get multiplied 3 with fact and replace the value of fat so effectively my statement is going to be fact is equal to fact star town I read that is though just as some is equal to some plus a value fact is equal to fact star count and the count is internally generated I do not have to depend on it so next time these three will become fourth I will multiply this 4 sorry first 3 and 2 is multiplied so this will have become 6 now count becomes 4 4 gets multiplied by 6 it becomes 24 and suppose I was to calculate for this 4 will now become 5 and next time when I come back for iteration it is a sorry 5 is greater than 4 get out so that is how I can simply calculate factorial here is a program which does that so you can see given number whose factor is needed I input M now I set up my counting mechanism count is equal to 1 while count is less than equal to n fact M is equal to fact n star count I have chosen to use the name fact M to represent factorial of some value and I add 1 to the count you all agree that this iteration will correctly calculate factorial L so it&#39;s very simple except that I need these artificial statements for setting up counting mechanism in exactly the similar way if I want to keep on doing some counting till L I look for some simpler mechanism unlike those abbreviations that I discussed where I advise please don&#39;t use them here is an abbreviation which is actually quite useful and very extensively used in C++ program this mechanism is called the false statement this false statement is a very spacious statement what that does is it permits you to define three things in one place in your program after all in counting mechanism what do we need we need an initial value we need a condition for continuation and we need an increment if we can prescribe all these three things typically at the beginning of the block and keep in mind the logic that while these three things are specified the first thing is that before you do anything in this block that is initialization of the cup the next thing you do the checking of the condition every time you come to the iteration and the last thing that specified which is the increment you do only when you completed one it so this is what it says the instruction permits us to define these three things and these actions are defined at the beginning of the iterative block so this is the nature of the false statement for in bracket this is important to note you write three things separated by semicolons the first thing is count equal to one typical specification for initial action the next thing is the condition for continuation of the top so that is count less than equal to n iteration will continue as long as this condition is valid and the last specification is count plus plus which is count equal to count plus one remember I said that stand alone such post pre increments can be used whether you say minus minus a plus plus count or plus plus it means the same thing here say stand alone and it is indeed used in this sense in almost all false statements that you see in professional problem is a simpler thing but do you see now although I am writing all the three things in one statement at the beginning of my creative block those actions do not take place at that point the actions take place exactly as depicted by the earlier do-while implement so that is why the explanation is written it initializes the count before beginning the first iteration at the beginning of each subsequent iteration to check that condition and permit continue execution of the iteration only if that condition is satisfied and at the end of every iteration it will increment the count immediately after the iteration and go back so that is the simplest implementation of it by counting here is a program written to add n numbers using for state notice the program is very similar to what we had seen earlier which were implemented using do-while but we had artificial constraints on what number to be input so that zero can be taken as it then today earlier we saw how by counting we could include implement this algorithm using high state this is an implementation using form so you will notice that after reading the number of numbers to be read here and I am actually setting up F for iteration so for count equal to one count less than equal to n count plus plus can you tell me what this will do now in the translated algorithm it will set up count equal to one just outside this iteration board that statement will be executed next the condition will be J is count less than equal to n of course one may be less than equal to n because n would be five ten five thousand whatever and if so the iteration will be executed what does the iteration say enter the next number and it is added to some observe that what we were earlier doing artificially by writing count equal to count plus 1 in our dowhile implementation need not be written because that is part of the specification of the false statement the third part here this count equal to count plus plus will actually be executed at this point in the algorithm after completing it so we yeah how many numbers do you wish to add inside that until next number to be added yes because pre increment or post increment does not make any difference it is going to be a standalone operation no not after all that after a particular expression is evaluated the expression is that itself so the moment that is evaluated the value changes after post and pre does not apply to block of statements post entry applies to the evaluation within an expression when the only thing in the expression is that the value will change whether it is pre or post yes I will see that later but the point is what we are stressing at this juncture is a simple counting mechanism I start with 1 I want to count 1 2 3 4 5 6 n this is the mechanism integer agreed so let us keep that in mind everybody understands now how to set up an iteration an important point here was the algorithm was wrong because there is no C out number which is not required because when you type it you see it yourself you are going to type it okay the the point is we are discussing counting mechanism and unfortunately we concentrated on n number of other errors which are there in the program but it just shows that you are understood how counting works and I take it for granted by look at this program this finds maximum of n given numbers again it is very similar to finding out some except that we are not adding anything to sum but we start with the max number notice that we have n numbers given in this so I take the first number outside the iteration to set up the right value of Max and notice that there is no artificial condition here which says that find out maximum of given n positive integers or something the number that comes in could be any number and therefore I cannot make any assumption on max so I read the first number assign it to max now I have only n minus 1 numbers left to read and that is why the iteration specifies for I count equal to 1 count less than equal to n minus 1 count plus sum of n natural numbers in exactly the same way that we calculated factorial n I do not need any input so I simply set up an iteration for I equal to 1 I less than equal to n I is equal to I plus 1 sum is equal to sum plus I so instead of count I am using an object I whose value is changing because of the false statement and I am adding in every iteration that value of I to count so count we&#39;ll start with some we&#39;ll start with zero then one will be added two will be added free will be added up to N and when n iterations are over the control will come out printing this up okay in exactly the same way the factorial can be found notice that in the previous example of the file iteration when we implemented factorial L we actually started with fact equal to 1 but we multiplied that 1 by 1 again which was not necessary since I presume that n is larger than 2 because you won&#39;t use a computer to find factorial 2 hopefully so it will be a number larger than 2 3 4 so I start with fact equal to n factorial equal to 1 this time I am using the name n n factorial and I start the iteration count from I equal to 2 to n now what will happen is n factorial will get multiplied by the current value of I which is 2 at the beginning then 3 then 4 then 5 I will complete up to n so this is yeah it will not have any impact how many times I have said that whether you write plus plus ion I plus plus as long as it is a standalone statement it is not part of any other expression there is no difference in the implementation plus plus I is same as I plus 1 I is equal to I plus 1 I plus plus is also same as I is equal to I plus 1 there is no difference between these two when it is a standalone statement it has an impact only if it is part of a larger expression 3x square plus plus plus I minus something something then only it has a different meaning so this is a state-level statement here although it is part of the false specification please remember 4 gives 3 specifications the initialization part the condition part and the increment part and these 3 are independent specifications they have nothing to do with each other so it is not considered part of a larger expression and therefore there is no conclude this question is important because you will find in many books programs which will use the counting mechanism as minus minus IR plus plus I and I use as AI plus and therefore some confusion could be possible but it should be avoided this is no confuse both will implement a increment by one is that is that okay no right now we come to the general format and semantics of the false statement but actually what you have these three parts of the specification has not necessarily three simple statements like count equal to 1 or count plus plus the initial part can be a series of specification called init group that condition however is only one that is the continuation can be give me complex candy and the last part is called increment group in that increment group several statements separated by comma can also be used in the initialization group several statements in they separated by comma can be used a comma is a separation operator in C++ and it effectively works as equivalent of semicolon it finishes one statement and starts the next day please note that in the increment group if you have prescribed two three four five actions separated by comma one of those actions could still be plus plus J or J plus plus and that will still be a standalone instruction so that it will not have any impact on the camping you can read these variations at home and figure out what they do particularly see the last one fall in bracket semicolon semicolon bracket closed what am I saying initial condition none condition to be checked for continuation none increment now nothing this is actually in finite row this is equivalent of saying while one carry on doing so this is equivalent of a in finite row that is the C++ interpretation there are other multiple options shown for example if increment conditional increment statement is not written at all nothing is incremented okay so obviously you have to do something has to change the condition otherwise you will never get out of it anyway since most of you know Riemann integral I think we can both to this particular problem very quickly we observe that the computer cannot do integral calculus it can only do computation of value and therefore if I have to evaluate an integral I go back to the basic definition of integral integral of a function is actually the area under the curve between the two limits where I want to integer now area can be approximated so I will have a large area for example this is my function calculate the area under the curve y equal to 1 by X we understand what is significance of y equal to 1 by X the area under this curve between 1 and ay is actually the natural logarithm of a so log of a to the base e is nothing but the area under this curve and I had to calculate this area now I cannot do the measurement and the curve and so on so forth in terms of computer calculations I will have to calculate this area by approximating it I assume that there is a series of rectangles that I have and I keep adding the area of each rectangle say if I have 20 30 50 100 rectangles then the sum of all the areas of those red eléctrica tangles will be an approximation of this area people used to do these things manually and it was impossible to calculate say sum of thousand rectangle areas like this but machine can be used to do that so this is what I wish to do these are the rectangles whose areas I want to calculate now you can see that if this is my rectangle then this has some height and some wealth if all the tangles are same then I know what is the width suppose there were 100 rectangles I decide to use between 1 and a what will be the width of each individual rectangle a minus 1 by 100 a minus 1 by hauser whatever that is the way that is fixed the height of any rectangle suppose I measure the height at this point now if I know this which is X corner then I know 1 upon X is this point I can do that for every such point so I can get the height and therefore I can get the weight thing too height which is the area so this is what is shown here if there are n rectangles width of each rectangle is a minus 1 by N and to find out the height first I find out the x-coordinate of Erik time now here the x-coordinate of first rectangle is 1 because this is the this is the x-coordinate of positive x coordinate of second rectangle is 1 plus w third rectangle 1 plus 2 w in general for is rectangle the x-coordinate will be 1 plus I minus 1 into W agree very simple derivation and if this is the value of the x-coordinate what is the height here is 1 upon this so that is what we have done height H of is rectangle which is equal to 1 by X which is 1 upon that entire expression so this is simple derivation no problem now I know the height I know the will of is rectangle I have such a lyric tenders can you not see that I can set up a four iteration in every iteration I take one rectangle where I is 1 2 3 4 5 N and keep on adding to some it is like summing n values except that values are not being input but values have been calculated area of is rectangle is explicitly counted as W into H which is W into 1 by X which is W into 1 upon 1 plus I minus 1 into W this is the simple derivation and my program therefore automatically writes itself first I have to decide how many how many rectangles we say thousand if it is thousand width of rectangles taken together there is a minus 1 there for width of each one is a minus 1 by thousand x coordinate is this height is this an area of the rectangle is this this is just a consolidation of whatever we have discussed so far nothing new in this law it is useful however to write such things before you start writing your program so you know exactly what you want and now we write this program so look at this problem observe that I am now generalizing the program to say I had thousand rectangles like this so what am i doing area is zero I define W I calculate W as a minus 1 upon thousand I of course input the value of a then I set up the four iteration what does that fall say for I is equal to one semicolon I less than equal to thousand semicolon I is equal to I plus 1 so that means please do the following block of statements one thousand times starting with the value of I equal to one then I equal to 2 I equal to 3 etcetera it is important what value I takes because we are using I explicitly never computation what is the computation area is equal to area plus W star 1 upon 1 plus I minus 1 style of exactly the same formula that will work now nothing else is to be written you can wonder later on whether you will get the correct calculation because there are a lot of 1 upon this and so on and if an integer division occurs somewhere your son you will notice however when you examine this that no such problem will happen because W is defined as float and therefore while I minus 1 will be integer when it is multiplied by W it becomes float when that is added to 1 that becomes float and when one is divided by that whole quantity that 1 will become 1 point 8 however those of you who wish to be more meticulous might write everyone has one point 0 just to be on the safer self there is no harm in doing but notice that my entire program although I am adding areas of thousand rectangles does not have the housing statement and if I won&#39;t take the machine to add 1 million rectangles my program will remain the same what will change the thousand would it not make sense then to further generalize this program and say that instead of thousand I will input some end from the user say how many how many rectangles we want to add tell me in fact maybe interesting I will display the results on Moodle by the of this program where I execute it for one hundred thousand and ten thousand and he can compare what is the value of actual log with with the values that you get there is a further interesting what should I say modification possible because when you add a rectangle area observe that a portion of the area above the curve also gets added now you can take the height of that rectangle not to be the starting point but the end point but then you will lose so instead of taking this height which causes this much portion to be extra you can take this I but that will cause reduction in that so one suggestion is you calculate the area of the rectangle taking the first height into account calculate the area of the rectangle taking the second height into account and take the average because that will give you half of the a perfect angle portion which is likely to be closer to the truth will it make a difference not if you are a thousand ten thousand rectangle you note that when you have all rectangles it is not that you are adding some meaningful portion of that curve at a later stage but you are actually making the width of every rectangle smaller and therefore the approximation will be more accurate will comment more on this but we understand how easy it is you can solve the problem of any integration between limits using this approach that&#39;s why it is the Riemann integral is important because it can be used in multiple places we will quickly look at this interesting problem the another problem called him general numbers the I am introducing this problem is not the original him general small the problem is suppose I have to build a wall of four feet long and in that wall I have to lay bricks but I have bricks of two kites one is one one foot brick and the other is to feed break so short break in a long break the question that is being posed is in how many different ways can I lay the bricks to make four feet length so here I have written the possibilities I can choose all four bricks of one foot long so I have one one valve man I can choose the first brick to be two feet long and the other ones sharp I can choose one two one I can choose one one two or I can choose two bricks which are two feet long agreed so these are the various possibilities how many possibilities do we notice here 1 2 3 4 5 actually an exercise in combinatory but suppose I ask this question in how many ways this can be done if the length is 3 feet or if the length is 5 feet I have written down here the combinations if I have a 3 feet length wall then any line of bricks will have either 1 1 1 or will have 2 1 or will have went to there is no other possibility for four feet wall we have already listed and for five feet wall I will have more combination these are exhaustive combination they have been written however in a spatial fashion so that you can identify some relationship between the previous possibilities for 3 feet tall at a 4 feet wall in the five feet wall one of those possibilities observe this in a 3 feet wall and a 4 feet wall I have all combinations of 3 feet wall with 1 one foot brick added to it that makes it four feet book I have originally some combinations I&#39;m selling the possibilities are the five feet wall I have all the possibilities of the four feet wall and I did one foot break there so that all of them becomes the possibilities for five feet wall what are the additional possibilities in the five feet wall 1 1 1 2 2 1 2 1 2 2 notice that these three possibilities have a larger brick at the end but all the three possibilities if you remove that to algebraic come from the possibilities of 3 feet or 3 feet tall had one one one two one one two if I add 2 to it I get all the possibilities of 5 feet one so I noticed that possibilities for five feet wall is actually equal to the total number of posse it is 4/4 we&#39;d wall by adding one foot break plus the total number of possibilities for three feet wall by adding it to fit me simple this is actually called a recurrence relation the original problem of the hem Chandra was a musical problem him general lived in 11th century in India and he said Voytek meter which is made of short syllables and long syllables so long syllable is two beats and short syllable is one here is an example of poetic meter somebody some of you might know this poem Yahoo an endo to Shara and Avila say char will be credited so these are the beats that you see that what him gender opposed the problem was if I am designing a poetic meter with eight beats how many ways are there to fill up these eight bits that was his mathematical problem and then he gave a solution in 1100 something he gave a solution he says by the method of ping girl it is enough to observe that the last beat is long or short Bingle had written this mathematical sutra he lived 200 before Christ 200 years before Christ came to the Rose 1100 years ad so this is an important point which preserve Rama day made his lecture three years ago and I make it every time copy if necessary and if permitted but give credit the very fundamental actual of professional life that is why you will find that when you write research papers and you quote whether somebody else has done something you always quote you cite that reference saying this I read it in this book or this place so that is I am NOT taking the credit somebody assisting is to be given liquid mingle I did by the way a whole lot of things and several of his sutra have subsequently been incorporated the point of the hymn Chandler solution now is that if by method of Pingala if I observe what is the last bit is longer short I can get the classification and eight bit pattern can be made of taken me seven bit pattern and add a short bit or take any six bit pattern and I&#39;ll a long wait just like the brick problem and this gives us a recurrence relation number of 8-bit patterns equal to the number of 7bit patters plus number of six bit patterns but I cannot solve this problem then I must no wonder the number of seven bit patterns of lol number of six meter number of seven bit patterns Intel is defined by number of 68 patterns and number of five bit so if I start backward I say H n which is the total number of patterns within bits H 8 will be H 7 plus h 6 in general HN is equal to HN minus 1 plus HN minus 2 this is called a recurrence relation and we need to know its seven and a six for which we need to know H five for which we need to know H four etcetera so you start always from the first thing H 1 number of patterns with one big only one say short bit H 2 number of patterns with two bits there are exactly two patterns possible s s and L nothing else is possible now you know H 1 and H 2 Bristow H 3 is equal to H 2 plus H 1 which is 2 plus 1 H 4 is equal to H 3 plus h 2 h 5 is equal to h 4 etcetera h n will be equal to now I have three values one value is the current H n which I want to compute one value is a previous value and one value is the mixed value which I want to compute so I have next current and previous suppose I set up an iteration in which I have these three locations current previous and next I initialize some value to current some value to previous which is H 1 and H 2 I can now calculate next which will be H 3 and if I now set up an iteration but before every iteration I keep shifting the well I will take the current value and put it in previous next value put it in current and go to the next iteration and if I keep on doing this I can generate in numbers in in this M generosity so this is the program the integer definition is used to define H 3 and H and there is a variable called H next I hope you understand the significance of these three names H brave is a previous value H current is the current value and H next is what I have to calculate these three locations initially contain one two and unknown one and two represent H 1 and H 2 respective ok now I set up an iteration for I equal to 3 I less than equal to n I plus plus I already taken in as input suppose M is 10 then the iteration will begin with I equal to 3 what will it do it will calculate H next is equal to H pre plus h correct these are three locations by the way they have nothing to do with that whatever with the value of I there will be only 3 location what will be the value of H makes that this time H next will be equal to first iteration the first iteration what will be the value H breve is 1 h current is 2 so 2 plus 1 3 its next will have a value 3 now for preparation of the next iteration I do not have to do anything about counting that is being done but I need to shift these values so that next time as 4 is calculated next time H 5 is calculated and all these calculations happen in a location called H next is that is this here so that&#39;s it these numbers generate mathematics from poetry and represent a extremely interesting model you might have heard of golden ratio successive terms the ratio of successive terms tends to that limit these are commonly known as Fibonacci numbers how many of you have heard of Fibonacci numbers all of you none of you knew about himself it is not uncommon to forget your own heritage when you start believe believing that anything great can only be done by friends and not by us you never look for old mathematical exploitation how many of you have tried to read yes real about whatever happened in this country whatever happened in the entire Middle East Fibonacci has admitted that he learned these things from an Arabian scholar in North Africa to whom he had gone to learn the Hindu numerals and such things the entire algebra for example was developed by Arabic scholars all of that is now treated as Western knowledge nothing wrong in it a whole lot of knowledge has been added by these scholars all across the world including Western scholars so the idea is not to belittle any effort but when your own heritage is so strong so did not interest you to know what is that and you don&#39;t have to read big history books just go to Wikipedia just us Indian mathematics just for your own interest I would suggest you read it I will close this thank you very much [Music]

Transcript for:Lecture Notes on Iteration Using For-Statement in C++

Transcript for:
Lecture Notes on Iteration Using For-Statement in C++