CS1101C Practical Exam

Session 5 (1800 - 1945 hours)

Amnesty

The name of your C program file must be called amnesty.c, files with any other name will not be marked.

The deadline for this lab is Wednesday 14 November 2007, 19:45:59 hours. Strictly no submissions will be accepted after the deadline.

Background

A king has decided to grant amnesty to N prisoners who are locked up in a tower with prisoners locked in individual prison cells. The cells are arranged in a circular manner with the doors of the cells facing the center of the tower. The prison cells are numbered anti-clockwise from 1 to N such that when all prisoners are looking out the door at one another, prisoner N will be on prisoner 1's left.

To determine the order of prisoners to be freed, the king ordered his two jailers to free the prisoners one by one. Starting from prisoner 1 and moving anti-clockwise, one jailer counts off k prisoners, while the other jailer starts from prisoner N and moves clockwise, counting m prisoners. The two chosen prisoners are then released; both jailers might pick the same prisoner. On the next day, each jailer starts counting again from where they have left off the previous day. Note that the two prisoners leave the cells together, so it is possible for one jailer to count a prisoner already selected by the other jailer.

Text File

A text file called “amnesty.txt” has been copied into your directory by the pesetup command. This text file contains an unknown number of lines each a triplet consisting of the three positive integer values separated by spaces. The triplet consists of values for N, k and m. The sample text file contains the following lines:

10 4 3
9  3 4

Task

Your task is to write a program that successively reads in the three numbers (k > 0; m > 0; 0 < N <= 20) and determines the order in which the prisoners are released.

You are allowed to write your program in anyway you wish, but you are reminded to adhere to the principles of modularity. Write a comment on top of each function, justifying how the function implementation follows the principles of abstraction, cohesion, and coupling.

Sample Output

The following is the sample output using the above sample text file. Remember that we will test your program with other input files. 
$ gcc -Wall amnesty.c -o amnesty
$ ./amnesty
(4 8) (9 5) (3 1) (2 6) (10 10) (7 7)
(3 6) (7 1) (2 4) (9 9) (5 5) (8 8)

$

Note that the each pair of values, say (x y) denotes two different prisoners that were freed by the two jailers within the same iteration. (x x) denotes both jailers choosing the same prisoner for release. You may assume the following:

We will test your programs with other (more complicated) text input files.

Notes

Do not use any structures or any form of dynamic memory allocation (using malloc or calloc) in your program, else no credit will be given.

Remember to submit your program frequently using the submit amnesty.c command, and check your submission using the check command.

All the best!

UNIX commands

Some useful UNIX commands (in case you forgot what you did in Lab 0):

  1. “dir”: lists all the files in the directory.
  2. “cp a.txt b.txt”: copies a.txt to b.txt.
  3. “mv a.txt b.txt”: moves / renames a.txt to b.txt.
  4. “cat a.txt”: shows the contents of a.txt.