CS1101C Practical Exam

Session 2 (1200 - 1345 hours)

Leader Selection Game

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

The deadline for this lab is Wednesday 12 April 2006, 13:45:59 hours. Strictly no submissions will be accepted after the deadline.

Preliminary

Given N persons and they sit around a table. We label the N persons by 1, 2, ..., N sequentially clockwise. They proposed a scheme to select a leader. Starting from person 1, a token is passed from a person to his neighbor in clockwise. After the token moves x steps clockwise, one person will get the token. If this is the first time the person get the token, he will swap places with the person who is floor(q/2) steps away from him clockwise (q is the number of persons remaining on the table); otherwise, he needs to leave the table. Finally, the person who is still on the table is selected to be the leader.

Our aim is to find out who is the leader.

Example

Suppose N=4 and x=2. The movement is as follows.

1234
^    (initially, the token is at 1)

1234
  ^  (after two moves, 3 gets the token and he swaps with 1.)

3214
  ^  (after two moves, 1 gets the token again. 1 leaves the table.)

324
^    (after two moves, 3 gets the token again. 3 leaves the table.)

24
 ^   (after two moves, 4 gets the token and he swaps with 2.)

42
^   (after two moves, 4 gets the token again. 4 leaves the table.)

2   (2 is still on the table. He is the leader.)

The Task

Write a program leader.c that requests N and x from the user. N and x are both positive integers, where N <= 1000 and x <= N. A sample run of the program is shown below. User input is denoted in bold.

$ gcc -Wall leader.c -o leader
$ leader
Enter the number of persons (N): 4
Enter the value of x: 2
The leader is: 2

Points to Note

For simplicity, we assume that the inputs from the user are always valid.
Do not use any two-dimensional arrays, structures, or File I/O in your program. One-dimensional arrays are fine; in fact, you would certainly need to use one-dimensional arrays.

You are reminded to follow the sample output exactly; else marks will be deducted.

Remember to submit your program using the submit leader.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):

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