Link back to syllabus

  1. If you have not already done so, test your reverse_llist function from Tuesday’s class.

  2. A children’s game is played like this: n children stand in a circle. One child (call her child 0) starts counting by saying “1”. The child to 0’s right (call him child 1) then continues the count by saying “2”. The counting continues, until a child gets to the number k. The child who says k then leaves the circle. Counting resumes at 1 with the child to the right of the child who just left. Once again, the child who counts “k” leaves. This process continues until only one child is left.

The question is: given n and k, which child is the last one remaining?

For example, suppose n = 7 and k = 4. We start like this:

Child:  0  1  2  3  4  5  6
Count:  1  2  3  4

So, child 3 is out. Resume with child 4 counting:

Child:  0  1  2  4  5  6
Count:           1  2  3
        4

Now, child 0 is out.

Child:  1  2  4  5  6
Count:  1  2  3  4

Child:  1  2  4  6
Count:           1
        2  3  4

Child:  1  2  6
Count:        1
        2  3  4

Child:  1  2
Count:  1  2
        3  4

Child:  1

Thus, child 1 wins.

Solve this problem by writing a program that asks for n and k and reports who wins. According to the example above, if the user enters in 7 and 4, your program should report 1.

Your program should use a circular linked list. Use the llist_node.[ch] files, not the llist.[ch] files. Edit as necessary. Use valgrind to make sure you have not leaked any memory or committed any other memory malfeasance.