Name: Hw 03 Who Gets the Cake Solution
SKU: 9399
Price: 35.00 USD
Availability: InStock

Description

5/5 – (2 votes)

Learning Goals

==============

This assignment asks you to keep track of information using an array.

You need to learn how to write Makefile. This is the last assignment

giving you the complete Makefile. Starting from the next assignment,

you need to write your own Makefile.

Rules

=====

Imagine that there is a piece of cake and several people want it.

They decide who can have it by playing a game: They form a circle and

choose an integer k greater than one. They count 1, 2, 3, …, k. The

k-th person is eliminated. They restart from 1 and count to k again

to eliminate the next person whose number is k. They keep counting

until only one person is left. This person gets the cake.

Please notice that there are different definitions of this

problem. Your solution **must follow the definition here**. More

precisely, this is how the method works: There are n people,

represented by are n elements in an array. The elements are counted as

1, 2, 3, … When the value k is counted, this element is removed in

future counting and the next element starts as 1 again. When reaching

the end of the array, the counting *wrap around* to the beginning of

the array (skipping the elements that have already been eliminated).

Please notice that in C arrays, indexes *always* start at zero but in

this problem counting starts at one. Both n and k have to be greater

than one. It is possible that k is greater than n.

The following is an example when the array has 6 (n is 6) elements and

k is 3. The eliminated elements in each round are mared by `X`. The

elements eliminated earlier are marked by `Y`.

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 1 | 2 | X | 1 | 2 | X

Go to the beginning. Since index 2 has already been eliminated, it is

skipped. Index 3 is eliminated this time.

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 1 | 2 | Y | X | 1 | Y

Index 5 has already been eliminated and it is skipped. Index 1 is eliminated this time.

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 2 | X | Y | Y | 1 | Y

Index 4 is eliminated this time.

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 2 | Y | Y | Y | X | Y

The element of index 0 is left.

This is another example. The array has 6 elements and k is 4.

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 1 | 2 | 3 | X | 1 | 2

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | 3 | X | 1 | Y | 2 | 3

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | X | Y | 1 | Y | 2 | 3

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | Y | Y | X | Y | 1 | 2

array index | 0 | 1 | 2 | 3 | 4 | 5

————|—|—|—|—|—|—

count | Y | Y | Y | Y | 3 | X

The element of index 4 is left.

This is the third example. The array has 25 elements and k is 7.