IIT Bombay

(1)

CS 101

Computer Programming and utilization Dr Deepak B Phatak

Subrao Nilekani Chair Professor

Department of CSE, Kanwal Rekhi Building

IIT Bombay

Session 5, Iterative algorithms

Tuesday August 9, and Wednesday, August 10, 2011

IIT BOMBAY

(2)

IIT BOMBAY

Overview

• Increment and decrement operators – Precedence table for operators

• Need for iterative solutions

– Identification of a repetitive block – Flow chart of basic iteration

– Instructions required to specify iteration

• Announcements

– Clicker devices, Discussion sessions – Labs next week

– Special lectures

(3)

IIT BOMBAY

Some short-cuts in C++

• C++ provides for a few variants of some instructions – Make these simpler to write

– Should be used with care

• When an assignment operation changes the value of one object x = x + 3.75 * y;

k = k * (a + b)/c;

m = m - 1;

• Such assignments can be written as x += 3.75 * y;

k *= (a + b) /c;

(4)

IIT BOMBAY

Increment and decrement operators

• If we wish to increment the current value of m by 1 m = m+1;

• Special increment and decrement operators ++ and -- ++ m; is same as m = m+1;

-- n; is same as n = n-1;

• We can also use these operators in a ‘post’ form i++; is same as i=i+1;

j--; is same as j=j-1;

• What is the difference between ‘pre’ and ‘post’ operations?

– As stand-alone statements, both forms achieve the same result, namely increment or decrement the variable value

(5)

IIT BOMBAY

Pre and Post increment

• When such usage appears in a larger expression

– it is the original value which participates in the evaluation of expression in case of post increment

– It is the modified value which participates in the evaluation of expression in case of pre increment

• Example 1

int m, n, j; j = 5; n = 2;

m = j++ * n; // This same as m = j * n; j = j + 1;

– Effect on j will occur after the expression is evaluated

• Example 2

int m, n, j; j = 5; n = 2;

m = n*++j; // This is same as j = j + 1; m = j * n;

(6)

IIT BOMBAY

Precedence and associativity rules

1. ++ -- (post increment and decrement) left to right 2. ! (not) ++ -- (pre ... ) + (unary) – (unary) right to left 3. * / % left to right 4. + (addition) – (subtraction) left to right 5. < <= > >= (comparison) left to right 6. == != (comparison) left to right 7. && (logical and) left to right 8. || (logical or) left to right 9. ?: right to left 10 = += -= *= /= %= (assignment) left to right Parentheses () has the highest precedence

(7)

IIT BOMBAY

Finding maximum of five given numbers int a, b, c, d, e, max;

cin >> a >> b >> c >> d >> e;

max = a;

if (b > max) {max = b;}

if (c > max) {max = c;}

if (d > max) {max = d;}

if (e > max) {max = e;}

cout << max;

(8)

IIT BOMBAY

Need to specify repetition

• Many problems will deal with a large number of values, performing similar operations on each value

• In this case, we are required to write a separate instruction for each comparison which takes place with a different value

• For 10 values, we will have to write 9 comparison instructions

• What if the number of values are 100, or 1000, or more?

– The number of instructions will become very large

• Large Number of Lines of Code (LoC) should usually indicate the complexity of the solution, not just the size of code

(9)

IIT BOMBAY

Need to specify repetition

• We would like to define a ‘pattern’ or ‘block’ of instructions, and somehow instruct C++ to execute that block repeatedly

– Each execution of the block should handle a different value – The instructions in the block have to be same

• Same locations may have different values upon each execution

(10)

IIT BOMBAY

Identifying repeatable actions

• We first rewrite the program to input a value when needed int a, b, c, d, e, max;

cin >> a ; max = a;

cin >> b; if (b > max) {max = b;}

cin >> c; if (c > max) {max = c;}

cin >> d; if (d > max) {max = d;}

cin >> e; if (e > max) {max = e;}

cout << max;

(11)

IIT BOMBAY

Identifying repeatable actions

• We are interested in only finding the maximum

– We do not need different names for these values int a, max;

cin >> a ; max = a;

cin >> a; if (a > max) {max = a;}

cout << max;

(12)

IIT BOMBAY

Execution with some sample values

• Consider that input values are 3, 9, 2, 17, and 5 – Let us trace what happens during execution

a max int a, max;

cin >> a ; max = a;

cin >> a; if (a > max) {max = a;}

cout << max;

(13)

IIT BOMBAY

Extended program

• We will include an output instruction after each new value is input and after it is compared with max

i a, max;

cin >> a ; max = a;

cin >> a; if (a > max) {max = a;} cout << max;

cout << “Maximum of all 5 numbers is: ” << max << endl;

(14)

IIT BOMBAY

Identifying repeatable actions int a, b, max;

cin >> a; max = a;

cin >> a ;

if (a > max) { max = a;

}

cout << max;

(15)

IIT BOMBAY

Identifying repeatable actions ...

int a, max;

cin >> a; max = a;

cin >> a ;

if (a > max) { max = a;

}

cout << max;

(16)

IIT BOMBAY

Setting up an ‘infinite’ loop

cin >> a ;

if (a > max) { max = a;

}

cout << max;

(17)

IIT BOMBAY

How long to continue looping?

cin >> a ;

if (a > max) { max = a;

}

cout << max;

condition true

(18)

IIT BOMBAY

While statement

While statement of c++ sets up an iterative loop statement-before-the-block;

while (condition) { block-statement1;

block-statement2;

-- - }

next-statement;

• Condition is evaluated at the beginning of each iteration.

• The block is executed if the value is true

(19)

IIT BOMBAY

How to set a condition

• We need to define with care, the condition to be tested by our repetitive structure

– It should evaluate to ‘true’ for continuation of the loop

– Should evaluate to ‘false’ to get out, or exit from the loop

• Some value in the condition must change during each iteration

(20)

IIT BOMBAY

Effect of the ‘continuation’ condition

• If components of the condition do not change in any iteration

• it will always evaluate to either true or false

– The control will either keep repeating the loop infinitely

– Or control will come out without executing the body even once

(21)

IIT BOMBAY

Example of use of While statement ...

int a, max;

max = 0;

while (1) { cin >> a ;

if (a > max) { max = a;

}

cout << max;

}

(22)

IIT BOMBAY

While statement ...

int a, max;

while (1) { cin >> a ;

if (a > max) { max = a;

}

cout << max;

}

return 0;

(23)

IIT BOMBAY

Iterative solution

#include<iostream>

using namespace std;

int main(){

int a, max;

max =0;

while(1){

cout<<"enter the number:";

cin>>a;

if(a > max) {max = a;}

cout<<"max is "<<max<<endl;

}

(24)

IIT BOMBAY

(25)

IIT BOMBAY

Need for instructions to specify repetition

Modified Problem

– Finding the maximum in a set of positive integers, given as input one after another. Stop when value 0 is given. After reading each value, output the current maximum value

(26)

IIT BOMBAY

Iterative solution for finding maximum

#include<iostream>

int main(){

int a, max;

cin >> a; max =a;

while(a !=0){

if(a > max) {max = a;}

cout<<"max is "<< max << endl;

cout<<"enter the next number:";

cin>>a;

}

return 0;

(27)

IIT BOMBAY

Finding sum of given numbers

• Find the sum of a set of positive integers, given as input one after another. Stop when value 0 is given.

(28)

IIT BOMBAY

Iterative solution for finding sum

#include<iostream>

int main(){

int a, sum = 0;

cin >> a;

while(a !=0){

sum = sum + a;

cout<<"enter the next number:";

cin>>a;

}

cout << “Sum is “ << sum << endl;

return 0;

}

(29)

IIT BOMBAY

The ‘ do while’ construct

do { --- ---

} while (condition)

(30)

IIT BOMBAY

Looping for a given number of times

• Find the sum of N numbers given as input

(31)

IIT BOMBAY

Find factorial (N)

• N! = 1 x 2 x 3 x 4 … x N

• Essentially, we have to find the product of first N natural numbers

(32)

IIT BOMBAY

Announcement

• Clicker devices

– Will be used for attendance and for conducting quizzes – A user manual handout will be given on Friday

– We will do some simple testing on that day

• Make up lab and Discussion sessions on Saturday and Sunday

• Lab sessions

– Lab sessions: Please bring a lab notebook with you