CS101 Computer Programming and Utilization

(1)

CS101 Computer Programming and Utilization

Milind Sohoni

September 19, 2006

Milind Sohoni () CS101 Computer Programming and Utilization September 19, 2006 1 / 26

(2)

1 So far

2 Functions-PCAL implementation

3 call by value

4 call by reference

5 The calender problem

6 The gcd problem

(3)

The story so far ...

We have written some non-trivial programs We have seen various control flows.

We have seen multi-dimensional arrays and thechardata type.

We saw how to get formatted output.

We saw the use of functions

More Functions

We see in this talk (i) how functions are implemented, (ii) and certaincalling methods. Finally, we solve some more non-trivial problems. Again

www.cplusplus.com/doc/tutorialfor reference.

(4)

How are functions implemented?

Consider the following simple C++ code:

#include <iostream.h>

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

What issues arise in the

translation of C++ intp PCAL?

What is the translation of a function into PCAL?

How is the

argument/parameter to be passed to the function?

How is the output to be received?

How is the control flow to be implemented?

(5)

How are functions implemented?

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

What issues arise in the

translation of C++ intp PCAL?

What is the translation of a function into PCAL?

How is the

argument/parameter to be passed to the function?

How is the output to be received?

How is the control flow to be implemented?

Allot different memory segments for the function and the amin program.

a output N x y

M10 M11 M1 M2 M3

(6)

How are functions implemented?

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

a output N x y

M10 M11 M1 M2 M3

Translate the function:

150 RCL M10;

M11=M10 DIV 2;

1 TEST 25

And the main program

22 M10=M1 %copy N into input 23 1

24 TEST 150

25 M2=M11 % copy output into x

(7)

How are functions implemented?

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

Translate the function:

150 RCL M10;

M11=M10 DIV 2;

RCL 13 TEST 26 M13=M13+10 TEST 30

And the main program

22 M10=M1 %copy N into input 23 M13=5

24 1

25 TEST 150

26 M2=M11 % copy output into x 27 M10=M2 %copy x into input 28 M13=-5

29 1

30 TEST 150

31 M3=M11 % copy output into y

(8)

Call by Value

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

In other words,

There is a separation of memories.

The contents (values) of the input arguments are copied out into appropriate registers of the function.

The function works out the answer.

The output is copied back into appropriate registers in the calling program.

Execution resumes.

This procedure is calledCALL BY VALUE.

(9)

Call by Reference

int by2(int a) {

return(a/2);

}

int main() {

int N,x,y;

cout << "N?";

cin >> N;

x=by2(N);

y=by2(x);

xout << y;

}

There is another possible scenario:

Create the function body as before.

RCL M10;

M11=M10 DIV 2 For every function call,insert the function codein the main program, suitably modified:

RCL M1 M2=M1 DIV 2 Thus, the program code of the function is copied out into the main body and actually acts on the variables of the main program.

This is calledCall by Reference.

(10)

x y

return(y) y=f( x );

d=f( a );

nextline;

x

a a a x

d

nextline;

Call by Value Call by Ref.

(11)

int by2ref(int& a) {

b=a/2;

a=a-2;

return(b);

}

int by2value(int a) {

b=a/2;

a=a-2;

return(b);

}

int main() {

N=10;

o1=by2value(N);

o2=by2ref(N);

o3=by2value(N);

}

The observed outputs will be:

o1 o2 o3

5 5 4

This is because:

The first call by valueby2val copied out N into its own space and returned the value 5.

The second call by reference by2refused the memory locationN in its working and changed it to 8.

The third call will now reflectN/2 = 4.

(12)

int by2ref(int& a) {

b=a/2;

a=a-2;

return(b);

}

int by2value(int a) {

b=a/2;

a=a-2;

return(b);

}

int main() {

N=10;

o1=by2value(N);

o2=by2ref(N);

o3=by2value(N);

}

How do I specifyCall by Reference?:

Put an ”&” after the type declaration that you want passed by reference. A function may have some arguments by value and others by reference.

The calling syntax remains the same. Everything else remains the same.

The caller does not know, without looking at the function definition, if his input parameters are going to change!.

Arrays (and large structures) are ALWAYS paased by reference.

(13)

Uses of Call by reference

Having more than one outputs from a function.

void next(int& delx, int& dely, int x, int y, int M, int N, int map[40][40]) {

// returns the infinitesimal motion of water in the // map at position (x,y)

}

(14)

Uses of Call by reference

Modify an existing data structure

calender.cpp

Input: start day and number of days.

Output: The calender for the month

[sohoni@nsl-35 talk8]$ ./a.out start and days

3 30

0 0 0 1 2 3 4

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 0 0

[sohoni@nsl-35 talk8]$ ./a.out start and days

6 31

30 31 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

(15)

void month(int start, int days, int &finish, int A[5][7]) {

int i,j,date=1;

for (i=0;i<5;i=i+1) { for (j=0;j<7;j=j+1)

A[i][j]=0;

};

for (i=start;i<7;i=i+1) {

A[0][i]=date;

date=date+1;

};

Initialize the matrix to all zeros.

Maintain a date.

Fill up first row separately.

0 0 0 1 2 3 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

(16)

i=1; j=0;

while (date<=days) {

A[i][j]=date;

date=date+1;

if ((j==6)&&(i==4)) {

i=0;

j=-1;

};

if (j==6) {

i=i+1;

j=-1;

};

j=j+1;

};

finish=j;

return;

}

Start now with the second row.

Twolooping tricks

I At the end of a row.

I At the very end.

Note that (2) occurs before (1) above.

0 0 0 1 2 3 4

5 6 7 8 9 10 11

∗ 0 0 0 0 0 0

0 0 0 0 0 0 0

(17)

The main program is trivial Note thepretty printing.

int main() {

int i,j, st, fin, days, mymonth[5][7];

cout << "start and days \n";

cin >> st >> days;

fin=0;

month(st,days,fin,mymonth);

for (i=0;i<5;i=i+1) {

for (j=0;j<7;j=j+1)

printf("%3d",mymonth[i][j]);

cout<<"\n";

};

return(0);

}

(18)

Uses of Call by reference

The GCD problem

Recall that ifg is thegcdofm andn, then

g=αm+βn Write a program to compute g, α, β.

We useEuclid’s algorithm.

Ablue moonis the second full moon in a month.

ASankashtiis a chaturthiwhich falls on a Monday.

IsFriday, the 13threally very rare?

Given a numbernand a prime P, is there anmsuch that n·m= 1 mod P?

current desired North

star 153 years 23 years

(19)

astronomy...

Actually, things are more complicated than this:

Sun

Earth Moon

Rahu Ketu

RahuandKetuareimaginary planetswhich correspond to the intersection of the orbit of the moon with the plane of the orbit of the sun and earth.

Hence the mythology thatthe moon ate up rahu/ketu and an eclipse occurred.

(20)

Uses of Call by reference

The GCD problem

Recall that ifg is thegcd ofm andn, then

g=αm+βn Write a program to computeg, α, β.

(21)

Uses of Call by reference

The GCD problem

Recall that ifg is thegcd ofm andn, then

g=αm+βn Write a program to computeg, α, β.

Ifm>nandm=n·q+r, then gcd(m,n) = gcd(n,r)

This is used to reduce the two arguments systematically.

At each step ifm⁰ andn⁰ are such that

I gcd(m⁰,n⁰) = gcd(m,n).

I Eachm⁰,n⁰is a linear combination of m,n.

Thus for example:

gcd(153,23) = gcd(23∗6 + 15,23)

= gcd(23,15)

= gcd(15,8)

= gcd(8,7) = 1

(22)

Uses of Call by reference

Thus for example:

gcd(153,23) = gcd(23∗6 + 15,23)

= gcd(23,15)

= gcd(15,8)

= gcd(8,7) = 1 We begin with:

153 23

=

1 0 0 1

153 23

15 23

=

1 −6

0 1

153 23

23 15

=

0 1 1 −6

153 23

8 15

=

−1 7

1 −6

153 23

15 8

=

1 −6

−1 7

153 23

8 7

=

−1 7

2 −13

153 23

Finally:

1 =−3∗153 + 20∗23

(23)

Uses of Call by reference

#include <math.h>

void A(int a, int b, int& q, int& r) {

r=a%b;

q=(a-r)/b;

return;

}

(24)

Uses of Call by reference

#include <math.h>

void A(int a, int b, int& q, int& r) {

r=a%b;

q=(a-r)/b;

return;

}

We see here thatA(a,b,q,r) have four arguments.

The assumption is that a>b.

a,bare the input arguments, passed by value.

q,rare the output arguments, passed by reference.

The function implements:

a=b∗q+r

(25)

Uses of Call by reference

Lets look at the main program:

M,Nare read in with M>N.

m,nare the running

arguments with the following invariants.

I m>n.

I

m = x[0]∗M+x[1]∗N n = y[0]∗M+y[1]∗N The next pair is

(m,n)→(n,r), where r = m−q∗n

= (x[0]−q∗y[0])∗m +(x[1]−q∗y[1])∗n

int main() {

int ...,x[2],y[2],t[2];

x[0]=1; x[1]=0; y[0]=0; y[1]=1;

cout << "M>N?\n";

cin >> M >> N;

m=M; n=N;

A(m,n,q,r);

while (r!=0) {

m=n; n=r;

t[0]=x[0]-q*y[0];

t[1]=x[1]-q*y[1];

for (int i=0;i<2;i=i+1) { x[i]=y[i];

y[i]=t[i];

}

A(m,n,q,r);

}

cout << ...

}

(26)

Uses of Call by reference

[sohoni@nsl-13 lectures]$ ./a.out M>N?

99 87

gcd=3 alpha=-7 beta=8

[sohoni@nsl-13 lectures]$ ./a.out M>N?

115 78

gcd=1 alpha=19 beta=-28

int main() {

int ...,x[2],y[2],t[2];

x[0]=1; x[1]=0; y[0]=0; y[1]=1;

cout << "M>N?\n";

cin >> M >> N;

m=M; n=N;

A(m,n,q,r);

while (r!=0) {

m=n; n=r;

t[0]=x[0]-q*y[0];

t[1]=x[1]-q*y[1];

for (int i=0;i<2;i=i+1) { x[i]=y[i];

y[i]=t[i];

}

A(m,n,q,r);

}

cout << ...

}

(27)

Uses of Call by reference

Processing a large data-structure locally, without making copies.

Layer Fill

Fill up ann×N array in layers.

1 1 1

1 2 1

1 1 1

1 1 1 1

1 2 2 1

1 1 1 1

Strategy:

Start with the outermost layer.

Each call fills up thek-th layer and calls recursively, for the next layer.

s s s k

recursive call Outer Call

Current call

(28)

void layer(int a[10][10],int k, int N, int start) { int low,hi,i,j;

low=k; hi=N-k;

if (low+1==hi){

a[low][low]=start;

return;

}

for (i=low;i<hi;i=i+1) { for (j=low;j<hi;j=j+1)

{if ((i==low) || (i==hi-1)

|| (j==low) || (j==hi-1)) a[i][j]=start;

};

if (low+1==hi-1) return;

layer(a,k+1,N,start+1);

return;

}

(29)

low=k; hi=N-k;

if (low+1==hi){

a[low][low]=start;

return;

}

{if ((i==low) || (i==hi-1)

};

return;

}

Whats Happening

Thered code is the meat of the procedure.

The green code is to terminate/continue the recursion.

ais already filled correctly for 1,2,...,k-1.

hi,lowlocate the boundaries.

ais modified at the boundary and then a recursion.

(30)

low=k; hi=N-k;

if (low+1==hi){

a[low][low]=start;

return;

}

{if ((i==low) || (i==hi-1)

};

return;

}

layer.c

a: arrayalways passed by reference, no need to declare it as such.

k: layer to start N: array size

start: the entry for layer k

int main() {

int a[10][10], N,i,j;

cout << "N?\n";

cin >> N;

layer(a,0,N,1);

}

(31)

Assignments

Write a program which on inputN andk, outputs the ^N_k

subsets of {1, . . . ,N}in an array of sizek× ^N_k

. For example, for the input 4,2 the following output is expected (upto column re-ordering):

1 1 1 2 2 3

2 3 4 3 4 4

LetAbe anN×Nentries 0-1. Givenp= (i0,j0) and p⁰ = (i1,j1), we must check if there is a path in the matrix fromp top⁰ which moves

left/right/up/down,but does not visit any point (i,j) such that A[i][j]=0.

See example below:

1 1 1

1 1

1 1 1

1 1

1 1 1

1 0

0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0

0 0

(2,0) (2,4)