Use Of Loops
- As we break down algorithm into sub-algorithms, sooner or later we shall come across some iterative construct, that is, a loop, apart from conditional statements.
- A loop executing one more or one less time than the intended number is so common.
- To construct a loop we should be aware of three aspects:
- The initial condition that needs to be true before the loop begins execution
- The invariant relation that must hold before, during, and after each iteration of the loop
- The condition under which the loop must terminate
- The following design process is suggested to take care of these three aspects of algorithm development.
(1) To Establish Initial Condition
- Set the loop control variables, to values which are appropriate for solving the smallest instance of the problem in question.
- For example, suppose we want to add elements of the given array using a loop. The loop variables are, i the loop control variable which is also used as the array index and s, the current value of the sum. The smallest problem in this case is the sum of 0 numbers of elements. In this case s must be 0. Thus the initial condition is: i = 0, s = 0
- Try to extend the smallest problem to the next smallest. In doing this we will come to know what changes are to be done to the loop variables to achieve this change.
- For our example of summation of elements of an array the next smallest is the case of n = 1, in which case s must be equal to a[i]. Thus the solution for n = 1 can be derived from the solution for n = 0 by first considering the solution for i = 1: i = 1 s = a[1]
- Then the same can be re-written as: i = i + 1 Notes: i on RHS is 0 s= s + a[i] i is now 1
- The simplest termination condition occurs when it is known in advance the number of times the loop is to be iterated. In that case we can use a FOR structured programming construct.
- For example, to execute a loop 20 times, we may write: for i = 1 to 20 do …….. end for
No comments:
Post a Comment