CS211 - Algorithms and Data Structures II

Department of Computer Science, NUIM



T Naughton, CS NUIM

Solutions for Tutorial 3







Problem 1A.1



#include<iostream>



void main(void){



  int n;     // integer read in

  int line;  // counter for lines

  int count; // counter for blanks and 'a's



  cout << "Please enter a nonnegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  line = 0;

  while (line < n){



    count = 0;

    while (count < line){

      cout << ' ';

      count++;

    }

    count = 0;

    while (count < (line+1)){

      cout << 'a';

      count++;

    }

    cout << endl;



    line++;

  }



  cout << "Goodbye!" << endl;



}









Problem 1B.1



#include<iostream>



void main(void){



  int n;     // integer read in

  int line;  // counter for lines

  int count; // counter for blanks and '*'s



  cout << "Please enter a nonnegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  line = 0;

  while (line < n){



    count = 0;

    while (count < line){

      cout << ' ';

      count++;

    }

    count = 0;

    while (count < (n-line)){

      cout << '*';

      count++;

    }

    cout << endl;



    line++;

  }



  cout << "Goodbye!" << endl;



}









Problem 2A.1



#include<iostream>



void main(void){

  int n;    // input from user

  int row;  // counter for rows

  int counter;



  cout << endl << endl << "Please enter a nonegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  /*

  ** Write out the upper triangle. This will entail, at each row,

  ** writing out (row) spaces and (n - row) stars.

  */

  row = 0;

  while(row < n){



    // write out the correct number of spaces

    counter = 0;

    while (counter < row) {

      cout << ' ';

      counter++;

    }



    // write out the correct number of stars

    counter = row;

    while (counter < n) {

      cout << '*';

      counter++;

    }



    cout << endl;

    row++;

  }



  /*

  ** Write out the lower triangle. This will entail, at each row,

  ** writing out (n-row-1) spaces and (row+1) stars.

  */

  row = 0;

  while(row < n){



    // write out the correct number of spaces

    counter = 0;

    while (counter < (n-row-1)) {

      cout << ' ';

      counter++;

    }



    // write out the correct number of stars

    counter = 0;

    while (counter < (row+1)) {

      cout << '*';

      counter++;

    }



    cout << endl;

    row++;

  }



  cout << "Goodbye!" << endl;

}









Problem 2B.1



#include<iostream>



void main(void){

  int n;       // input from user

  int count1;  // counter for stars & rows

  int count2;  // counter for spaces



  cout << endl << endl << "Please enter a nonegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  /* write first line

  */

  count1 = 0;

  while(count1 < n){

    cout << '*';

    count1++;

  }

  cout << endl;



  /* write middle lines

  */

  count1 = 0;

  while (count1 < (n-2)){

    count2 = 0;

    cout << '*';

    while (count2 < (n-2)){

      cout << ' ';

      count2++;

    }

    cout << '*';

    cout << endl;

    count1++;

  }



  /* write last line

  */

  count1 = 0;

  while(count1 < n){

    cout << '*';

    count1++;

  }

  cout << endl;



  cout << endl << "Goodbye!" << endl;

}









Problem 2C.1



#include<iostream>



void main(void) {

  int n;    // input from user

  int row;  // counter for rows

  int counter;



  cout << endl << endl << "Please enter a nonegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  /*

  ** At each row, write a star, a space, and (n-row) stars.

  */

  row = 0;

  while (row < n) {

    cout << "* ";

    counter = 0;

    while (counter < (n-row)) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row++;

  }

  cout << "Goodbye!" << endl;

}









Problem T3.1



// Problem T3.1

// CS211 ADS2

// T Naughton, NUIM

#include<iostream>



/* With this program you will see how a little preparation goes a long

** way.

*/

void main(void) {

  int n;    // input from user

  int row;  // row counter for each section of the pattern

  int counter;

  int calc; // stores the result of a calculation



  cout << endl << endl << "Please enter a nonegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  /*

  ** There are three sections to this diagram.

  ** For each row of the first section, write out (n*n) stars.

  ** For each row of the last section, write out (n*n) stars.

  ** For each row of the middle section, write out (((n*n)-n)/2) stars

  ** followed by (n) Xs followed by (((n*n)-n)/2) stars.

  **

  ** Note, a good programmer would be able to work out two things here:

  ** (i) that ((n*n)-n) is even and so can always be divided by 2, and

  ** (ii) that (((n*n)-n)/2)+n+(((n*n)-n)/2)=(n*n)

  **

  ** Similarly, the first section has (((n*n)-n)/2) rows, the middle

  ** section has (n) rows, the last section has (((n*n)-n)/2) rows.

  */



  calc = ((n*n)-n)/2;

  // We have already determined that there will be no rounding errors

  // with this division.



  // The first section

  row = 0;

  while (row < calc) {

    counter = 0;

    while (counter < (n*n)) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row++;

  }



  // The middle section

  row = 0;

  while (row < n) {

    counter = 0;

    while (counter < calc) {

      cout << '*';

      counter++;

    }

    counter = 0;

    while (counter < n) {

      cout << 'X';

      counter++;

    }

    counter = 0;

    while (counter < calc) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row++;

  }



  // The last section

  row = 0;

  while (row < calc) {

    counter = 0;

    while (counter < (n*n)) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row++;

  }



  cout << "Goodbye!" << endl;

}









Problem T3.2



#include<iostream>



void main(void) {

  int n;    // input from user

  int row;  // row counter for the top section of the pattern

  int counter;

  int calc; // stores the result of a calculation



  cout << endl << endl << "Please enter a nonegative integer:" << endl;

  cin >> n;



  cout << endl << "Here we go:" << endl;



  /*

  ** We shall break this pattern into three sections.

  ** The first section has (n*n)/2 rows.

  ** The last section has (n*n)/2 rows.

  ** The middle section has (n*n)-(((n*n)/2)+((n*n)/2)) rows. This

  ** middle section will therefore contain one row if (n*n) is odd

  ** and zero rows if (n*n) is even (just as the pattern suggests).

  ** Prove that this means (n*n) rows in total. Remember that the

  ** divide operation on integers performs a floor (it rounds down).

  ** 

  ** For each row in the first section, we write out (row) stars,

  ** X, ((n*n)-(2*row)-2) stars, X, (row) stars. Prove that this is

  ** (n*n) characters in total.

  ** For each row (if any) in the middle section, we write out

  ** ((n*n)-1)/2 stars, X, ((n*n)-1)/2 stars. Prove that this is

  ** (n*n) characters in total.

  ** For each row in the last section we write out ((n*n)/2)-row-1

  ** stars, X, (n*n)-2-(((n*n)/2)-row-1)*2 stars, X, ((n*n)/2)-row-1

  ** stars. For this last section, however, it is probably more

  ** straightforward to simply print out the inverse of the first

  ** section.

  */



  calc = (n*n)/2; // calc is rounded down here.



  // The first section

  row = 0;

  while (row < calc) {

    // For each row in the first section, we write out (row) stars,

    // X, ((n*n)-(2*row)-2) stars, X, (row) stars.

    counter = 0;

    while (counter < row) {

      cout << '*';

      counter++;

    }

    cout << 'X';

    counter = 0;

    while (counter < ((n*n)-(2*row)-2)) {

      cout << '*';

      counter++;

    }

    cout << 'X';

    counter = 0;

    while (counter < row) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row++;

  }

  // (row) now contains the number of rows in the first section



  // The middle section has (n*n)-(((n*n)/2)+((n*n)/2)) rows.

  if ( ((n*n)-(((n*n)/2)+((n*n)/2))) > 0) {

    // For the middle section (if any), we write out

    // ((n*n)-1)/2 stars, X, ((n*n)-1)/2 stars.

    counter = 0;

    while (counter < ((n*n)-1)/2) {

      cout << '*';

      counter++;

    }

    cout << 'X';

    counter = 0;

    while (counter < ((n*n)-1)/2) {

      cout << '*';

      counter++;

    }

    cout << endl;

  }



  // The last section. Note: (row) contains the number of rows in

  // the first section of the pattern. We are going to decrement it

  // before each row so it now represents one less than the number

  // of rows remaining in our pattern.

  row--;

  while (row >= 0) {

    // Print out the inverse of the first section.

    // This means, for each row, we write out (row) stars,

    // X, ((n*n)-(2*row)-2) stars, X, (row) stars.

    counter = 0;

    while (counter < row) {

      cout << '*';

      counter++;

    }

    cout << 'X';

    counter = 0;

    while (counter < ((n*n)-(2*row)-2)) {

      cout << '*';

      counter++;

    }

    cout << 'X';

    counter = 0;

    while (counter < row) {

      cout << '*';

      counter++;

    }

    cout << endl;

    row--;

  }



  cout << "Goodbye!" << endl;

}