Reading:
Chapters 2 (all), 4 (4.1--4.9), 5 (5.1--5.4, 5.6), 6 (6.1--6.3, 6.8),
7 (7.1--7.3), 10 (10.1--10.4)
Also, be sure to look through the "Points to Remember" sections of these
chapters.
Topics:
Given the duration of a period of time in minutes, express it in weeks, days, hours and minutes.
The following code segment assumes that a function bool is_prime( int x ) that returns true if its argument is a prime number and false otherwise, is available.
int primes_found = 0, x=2;
while( primes_found <= 500 ){
if( is_prime(x) ){
cout << x << endl;
primes_found++;
}
x++;
}
The following code implements Euclid's Algorithm, which is based on the observation that for any positive integers a, b such that a > b GCD(a,b) = GCD(a-b,b). The subtraction eventually gets the numbers down to their GDC.
int c;
if( a <=0 || b<= 0 ){
cout << "Bad input: exiting. ";
exit(-1);
}
while( a> 0 && b> 0 ){
// swap a,b if a < b
if( a < b ){ c=a; a=b; b=c; }
// we have ensured a <= b
a = a-b;
}
cout << b ; //this is the result -- why?
Step through Euclid's algorithm for a few pairs of numbers,
and then step through the code to see how this implementation
works.
Instead of drawing squares we are going to print a pattern of '-' and '*' (for black and white squares). The main idea of the solution is the two nested loops. The following solution takes advantage of the fact that black and white squares of a chessboard alternate.
int N;
cout << "Enter Board Size: ";
cin >> N;
bool white = false; // is this square white?
for( int i=0; i < N; i++){
for( int j=0; j < N; j++){
if( white ) {
cout << "-";
white = false; // change the value to its opposite
}
else { // black
cout << "*";
white = true;
}
}
cout << endl; // go to the next row
}
Printing only results in the value being displayed (on the
screen). It cannot be used in subsequent computations. On
the other hand, the return operator allows for
reuse of the returned value, say, in an assigment or an
arithmetic expression. Standard mathematical functions like
abs and sqrt do not print anything, but
return their results, which makes possible statements like
x = 1.0 + sqrt(5);
Local variables get destroyed, together with the rest of the activation record of the function. The only value that survives is the value return-ed from the function.
A call by reference can be used to assign the results to some variables from the caller function. The following example explains the quadratic equation formula.
// this program solves quadratic equations
int main(){
double a, b, c, x1, x2;
while( true ){ // forever
cout << "Enter a, b, c of a quadratic equation : ";
cin >> a, b, c;
bool ok;
ok = solve_quadratic( a, b, c, x1, x2 );
if( ok ) // equation had solutions, print them
cout << "The solutions are " << x1 << ", " << x2 << endl;
else // there were no solutions, x1, x2 were not set
cout << "Sorry, no solutions for this equation\n";
}
}
// this function returns true if solutions were found, and
// false if there were none. This is done to let the
// calling program know if sol1 and sol2 were changed
bool solve_quadratic( double a, double b, double c, // coeffs
double& sol1, double& sol2 ){
double D = b*b - 4*a*c; // the discriminant
if( D < 0 )
return false; // no solutions exist, indicate failure
else {
double sq = sqrt(D);
sol1 = (-b + sq)/(2*a);
sol1 = (-b - sq)/(2*a);
return true; // indicate success
}
}
Left as an exercise.
void swap( int& x, int& y ){
int z = x;
x = y;
y = z;
}
Left as an exercise.
Assume the following declarations:
const int N = 10;
double a[N];
// then a gets initialized
double sum = 0;
for( int i=0; i < N; i++ )
sum += a[i];
cout << "Sum = " << sum << ", Average = " << sum/N << endl;
The idea is to traverse the array (same as in all other such problems), keeping track of the largest and smallest array element seen so far:
double min = a[0], max = a[0];
for( int i=0; i < N; i++ ){
if( max < a[i] ) max = a[i];
if( min > a[i] ) min = a[i];
}
cout << "Max = " << max << ", Min = " << min << endl;
I will assume here that the character array is in fact an old "C-style" zero-terminated string, declared somewhere above as char str[ ] .
int k=0; // current character position
int counter = 0; // the counter
while( str[k] != '\0' ){
if( ch == str[k] ) counter++;
}
cout << "Character " << ch << " occurs in "
<< str << counter << " times.\n";
What follows is called BubbleSort. Find another method in your text.
bool any_swaps = true;
while( any_swaps ){ // while there were swaps on the previous
// pass, make another pass.
for( int i=0; i < N-1 ; i++ ){ // note N-1 -- why?
any_swaps = false; // reset swap flag
if( a[i] > a[i+1] ){ // disorder, so swap
double aux = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
any_swaps = true;
}
}
}
// there were no swaps on the last pass, i.e. the array is
// now ordered
Notice that the body of the while loop can be used to check if the array is ordered.
Left as an exercise -- highly recommended!
All such functions require at least two arguments -- the name of the array (actually, the pointer to the first element of the array in the memory), and the length of the array (required for the loop that traverses the array)
double array_sum( double x[ ], int len ){
double sum;
for( int i=0; i < len; i++ )
sum += x[i];
return sum;
}
bool array_compare( double x[ ], double y[ ], int len ){
for( int i=0; i < len; i++ ){
if( x[i] != y[i] ) return false; // return immediately
}
return true; // if the loop finished, then all elements were equal
}
Like with an array, you can access individual characters in a string by using the subscript operator [ ]. Unlike an array, the C++ string allows many operations such as concatenation ("+"). A string also knows it length, returned for the particular string by the member function .length().
int CountVowels( string s ){
int count = 0;
char ch;
for( int k=0; k < s.length(); k++){
ch = s[k]; // extract k-th character
if( ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
count++;
}
return count;
}
string InvertString( string s ){
string res = ""; // result
for( int k = s.length()-1 ; k >=0 ; k--) res += s[k];
return res;
}
string SquashString( string s ){
string res = ""; // result
for( int k=0 ; k < s.length(); k++ ){
if( s[k] != ' ' ) res += s[k];
}
return res;
}
string ToLowerCase( string& s ){ // pass by reference
for( int k=0 ; k < s.length(); k++ ){
if( s[k] >= 'A' && s[k] <='Z' ) // s[k] is uppercase
s[k] = s[k] - 'A' + 'a'; // s gets changed here
}
}
Left as an exercise -- highly recommended!
97 dec. = 1100001 bin. , 1011010 bin. = 90 dec.
The representation of -N (for a positive integer N) can be obtained as follows:
As unsigned, the leftmost bit stands for 128's, so 10110101 = 128 + 32 + 16 + 4 + 1 = 181 dec.
As signed, the leftmost bit stands for the sign, and the rest for the two's complement. Inverting the right 7 bits 0110101 we get 1001010 bin. = 74 dec. So '10110101' stands for -75 .
See my tutorial on files.