My pseudocode in C is the following ( i will implement this as doubly linked list ), i'm having trouble figuring out the traverse part, how do i know the node i have alreadt traversed?and I also have trouble in the bold part of the question. Thanks for any help :
================================================== =====================
void initialize_list(name_of_list *a);
void insert_end(name_of_list *a);
void traverse_and_find(N) (name_of_list *a); <==== how to implement this function???
{
find the Nth elemet, Mark it,
then start counting N times again
delete the last one
}
/************************************************** **/
main()
{
while (insert_data != 9999) /* insert the data */
{
insert_end ( ) / *insert data at end */
M = M + 1 /* Missionary count */
}
scanf (N) /* pick a number */
if ( M %2 == 0) /* even number, clockwise*/
for (i = 1 to M-1)
traverse_and_find(N) /* traverse and fin */
else /* odd number, counterclock */
for ( i = 1 to M-1)
traverse_and_find( N ) /* traverse and delete */
}
Ok following is the problem, Thanks for any help:
A band of M missionaries is surrounded by a tribe of cannibals. The cannibals, being folks of small appetite, only demand one of them for dinner each day. The missionaries find drawing straws distasteful for people of their learning and sophistication. Instead, they form a circle and pick an integer N out of a hat. Then beginning with the first missionary in circle (We will tell you who the first one is), they start to count from one to N. The direction in which the count proceeds depends on the initial number of missionaries in the circle. If there are an even number of them, the count goes clockwise; otherwise, it goes counter-clockwise. Whenever N is reached, that missionary steps out of the circle and the count re-starts with the next person (note that the direction of the count does not change until the dinner du jour is decided). This process repeats until only one missionary is left in the ``circle'', who is the unfortunate one.
For example, say that you have four missionaries A, B, C and D forming a circle clockwise in that order: On the first day, they pick 3. There are four of them so the count goes clockwise for the day. C is the first person out of the circle, B is the second and D is the third; A is consumed. On the second day, the new circle is C, B, D, and the count goes counter-clockwise. They pick 6. B is the first one out and D the second; C is consumed. On the third day, the new circle is B,D. They pick 1. B is the first one out and D is eaten. On the last day, B is consumed. So the order in which they are consumed is A,C,D,B.
