10
Divide and Conquer Example
Assume you want to print a hollow square of “*”s with the length of each side read into the variable s.
The square might look like
* * * * *
* *
* *
* *
* * * * *
In pseudo code this might be
Print a line of stars
Print the middle lines
Print a line of stars
One may want a mainline program that looks like
int main()
{ int s;
cout << " enter the length of a side ";
cin >>s; //Read in length of side
printstars(s); //do top line
printmiddle(s); //call function
printstars(s); //do bottom line
return 0;
}
Writing subroutines with no return value:
Begin with function header:
void printstars(int s)
Continue with body:
{
// this subroutine prints a rows of *’s
for (int j = 1; j <=s; j++)
cout << "*";
cout << endl;
}
Similarly for the printmiddle function:
void printmiddle(int s)
{
for( int i=2; i <=s-1; i ++)
{ //print row i
cout << "*"; //print left hand *
for ( int j=1; j <=s-2; j++)
cout << " "; //print middle blanks
cout << "*" << endl; //print right hand *
}
}
Before int main() we need to tell the compiler what are the input and outputs of our function, we need a function prototype
void printstars(int s); //function prototype
void printmiddle(int s);
The structure of the program would then be:
void printstars(int s); //function prototypes
void printmiddle(int s);
int main()
{ int s;
cout << " enter the length of a side ";
cin >>s;
printstars(s); //do top line
printmiddle(s);
printstars(s); // do bottom line;
return 0;
}
void printstars(int s)
{ for (int j=1;j <=s; j++)
cout << "*";
cout << endl;
}
void printmiddle(int s)
{ for(int i=2; i <=s-1; i ++)
{ cout << "*"; //print left hand *
for (int j=1; j <=s-2; j++)
cout << " "; //print middle blanks
cout << "*" << endl; //print right hand *
}
}
The inner loop of printmiddle looks like printstars with a ‘ ‘ rather than a ‘*’. Could we make another subroutine that makes whatever character one wishes as in
void printchar(int s, char c)
{
for (int j=1;j <=s; j++) //print a line of whatever is
cout << c; //in c
}
The printmiddle would then be
void printmiddle(int s)
{
for(int i=2; i <=s-1;i ++)
{
cout << "*"; //print left hand *
printchar(s-2,' '); //print blanks
cout << "*" << endl; //print right hand *
}
}
and prinstars would not be needed and the mainline would be
int main()
{ int s;
cout << " enter the length of a side ";
cin >>s;
printchar(s,'*'); //do top line
cout <<endl;
printmiddle(s);
printchar(s,'*'); // do bottom line;
cout <<endl;
return 0; }
Exercises in interpreting and writing functions
For the following function headers, what is the type of the return value, and the number and types of the parameters
1. double average(double a, double b, double c)
2. double mpg(double miles, double gas)
3. float getcelcius(float fahrenheit)
4. int factorial(int n)
5. void factorialprint(int n)
6. void oddeven(int n)
What are the function prototypes for the above headers?
Sample bodies:
1. double average(double a, double b, double c)
double average(double a, double b, double c)
{
return (a+b+c)/3.0;
}
2. double mpg(double miles, double gas)
double mpg(double miles, double gas)
{ if (gas!=0.0)
return miles/gas;
else
return 0;
}
3. double getcelcius(float fahrenheit)
double getcelcius(float fahrenheit)
{
return 5.0/9.0*(fahrenheit-32);
}
4. int factorial(int n);
int factorial(int n)
{int prod=1;
for (int i =1; i<=n); i++)
prod=prod*i;
return prod;
}
5. void factorialprint(int n);
void factorialprint(int n)
{int prod=1;
for (int i =1; i<=n; i++)
prod=prod*i;
cout << " the factorial is " <<prod;}
6. void oddeven(int n)
void oddeven(int n)
{
if(n%2 ==0)
cout << n << " is even" << endl;
else
cout << n << " is odd" << endl;
}
How these might be used:
main()
{
cout << "average of 10 20 and 30 is "<< average(10.0,20.0,30.0);
oddeven(23);
cout << " 10 factorial is "<< factorial(n);
factorialprint(9);
cout << "miles per gallon is " <<mpg(250.0,10.4);
return 0;
}
Write function headers for
1. Findabs that accepts a double precision number and returns the numbers absolute value.
2. mult that accepts two floating point numbers and returns their product.
3. powfun that raises an integer passed to it to the power passed to it and returns the result
4. table that produces a table of the squares and cubes of the numbers from 1 to 10.
5. Sigma that returns the sum of the numbers from 1 to n, where n is passed to it.
6. Totalamount that has four parameters: quarters, dimes, nickles, and pennies and returns the total amount of money in a piggy bank.
7. max that computes the maximum of two numbers.
max can be used to find the maximum of n values that are read in as follows:
int a, maxn;
cin >> maxn; //the first value is put into max
for (int I=2, I<=n, I++)
{
cin >>a;
maxn=max(a,maxn)
}
Exercises for call by value and call by reference
1.Consider the code:
void swap(int &a, int & b)
{
int temp;
temp =a;
a=b;
b=temp; }
what does the following print ?
a=2;
b=4;
swap(a, b);
cout <<a<<b;
What does this code do?
cin >>a>>b>>c;
if (a>b) swap(a,b);
if(b>c) swap(b,c);
if (a>b) swap(a,b);
2.Consider the code:
void sum(int a, int & b)
{ a=a+b;
b=a+b;
}
what does the following print?:
a=2;
b=4;
sum(a,b);
cout <<a <<b;
3. Consider the code:
void sum(int &a, int & b)
{ a=a+b;
b=a+b;
}
what does the following print?:
a=2;
b=4;
sum(a,b);
cout <<a <<b;
4. Consider the code:
void sum(int &a, int b)
{ a=a+b;
b=a+b;
}
what does the following print?:
a=2;
b=4;
sum(a,b);
cout <<a <<b;
5. Consider the code:
int sum(int &a, int b)
{ a=a+b;
return a+b;
}
what does the following print?:
a=2;
b=4;
cout <<sum(a,b)<<a<<b;