5.5 Review Exercises


Exercise 5.5

  1. This program is supposed to find the first negative value in the array score. What does it do? 
    var score : array 1 .. 100 of int
var i : int
.
.
.
% assume values have been put in the array
i := 1
loop
   exit when i >= 100 or score(i) < 0
   i := i + 1
end loop
put "First negative value is at ", i

  2. A programmer using a square, two-dimensional array defined by 
    var board : array 1 .. MAX, 1.. MAX of int
    wanted to sum the elements along the main diagonal (the diagonal whose elements are board(1, 1), board(2, 2), and so on). To do this, the programmer wrote 
    var total : int := 0
for i : 1 .. MAX
   for j : 1 .. MAX
      total := total + board (i, j)
   end for
end for
    1. What does this fragment actually do?
    2. Write a fragment that does sum the elements in the main diagonal.
    3. Write a fragment that sums the elements of the other diagonal.

  3. How many elements can be stored in each array? 
    var a : array 0 .. 5 of char
var b : array -10 .. 10 of boolean
var c : array 'A' .. 'C', 0 .. 4 of real
var d : array 0 .. 10, -10 .. 0 of int

  4. What will be printed by the following program? 
    var list : array 1 .. 3 of int

for i : 1 .. 3
   list(i) := 3 - i
end for

put list(1) + 2, " ", list (1 + 2), " ", list(1) + list(2)

  5. Examine the following program fragment and then answer the questions that follow it. 
    const ROW_TOP := 5
const COL_TOP := 7
var matrix : array 1 .. ROW_TOP, 1 .. COL_TOP of char
    1. What type are the elements of matrix?
    2. What are the index types of matrix?
    3. How many elements can be stored in matrix?
    4. Write one or more instructions that will set all elements of matrix to blanks.

  6. Suppose that a is created by the declaration 
    var a : array 1 .. 3, 1 .. 4 of int
    What will be printed by the fragment 
    for row : 1 .. 3
   for col : 1 .. 4
      put a(row, col):3 ..
   end for
   put ""
end for
    after each of the following fragments have been executed?

    1. for row : 1 .. 3
   for col : 1 .. 4
      a(row, col) := row - col
   end for
end for 
    2. for row : 1 .. 3
   for col : 1 .. 4
      if row = col then
         a(row, col) := 1
      else
         a(row, col) := 0
      end if
   end for
end for 
    3. var i : int := 0
for row : 1 .. 3
   for col : 1 .. 4
      i := i + 1
      a(row, col) := i
   end for
end for 
    4. var i : int := 0
for decreasing col : 4 .. 1
   for row : 1 .. 3
      i := i + 1
      a(row, col) := i
   end for
end for

  7. Determine the output of the following program if it is given input of

    I'LLJUSTFLIPOVER

    const MAX := 4
var matrix : array 1 .. MAX, 1 .. MAX of char
var temp : char

for i : 1 .. MAX
   for j : 1 .. MAX
      get matrix(i, j)
      put matrix(i, j) ..
    end for
    put ""
end for

for i : 1 .. MAX
   for j : i + 1 .. MAX
      temp := matrix(i, j)
      matrix(i, j) := matrix(j, i)
      matrix(j, i) := temp
    end for
end for

put ""
for i : 1 .. MAX
   for j : 1 .. MAX
      put matrix(i, j) ..
   end for
   put ""
end for

  8. The Sieve of Eratosthenes is the name given to an algorithm for finding prime numbers (numbers greater than one, having no exact divisors other than one and themselves). The sieve starts by considering all numbers greater than one as possible primes.

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

    The first number in this list, two, must be prime but all multiples of two cannot be prime and hence can be eliminated from the list to give us

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

    The next number still in the list, three, must also be prime since it was not eliminated when we found multiples of two. We can, however, eliminate all multiples of three to obtain

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

    In the algorithm, this process continues (eliminating multiples of five, seven and so on) until it is no longer posssible to eliminate any multiples of values left in the table. These values that remain must all be prime.

    Write a program to implement Eratostenes' Sieve. You might find it useful in your program to use the variable 

    var sieve : array 2 .. MAX of boolean
    to maintain a record of the numbers that are possible primes.