. Problem 1035--(Josephus (circle) 1: Introduction Description: problem Primary

Question

. Problem 1035--(Josephus (circle) 1: Introduction Description: problem Primary level) Problem description and f any) background of the algorithms. n,1,m, ,m, n1, 2, , n, Josephus (circle) problem: Josephus problem is a math puzzle with a grim description: nprisoners are standing on a circle, sequentially numbered from 1 to n. An executioner walks along the circle, starting from prisoner 1, removing every m-th prisoner and killing him. As the process goes on, the circle becomes smaller and smaller, until only one prisoner remains, who is then freed (As a result, we can also get the killing , For example, if there are n = 5 prisoners and m = 2, the order the prisoners are killed in (let's call it the "killing sequence") will be 2, 4, 1, and 5, and the survivor will be E3. (Asa result, we can also get the killing sequence: 2 4 1 5 Given any two positive integers n, m0.find out the king seguence. Tips: use a circularly linked list. () More details: http:rosetacode.org/wikiJosephus problem httpslen.wikipedia.org/wikilJosephus problem) Input: Two Positive integers: n and m. The output sequence Sample Input 4 17 Sample Output 1342 2: Algorithm Specification Description (pseudo-code preferred) of all the algorithms involved for solving the problem, including specifications of main data structures 3: Testing Results Table of test cases. Each test case usally consists of a brief description of the purpose of this case, the expected result, the actual behavior of your program, the possible cause of a bug if your program does not function as expected, and the current statuspass"or 4: Analysis and Comments Analysis of the time and space complexities of the algorithms. Appendix: Source Code (in C/C++)

Explanation / Answer

PROBLEM DESCRIPTION :

There are n prople ina circular queue waiting to be executed. In each step m-1 people are skipped and the mth person is executed and then the next n-1 prisoners are skipped and mth prisoner is executed. This takes place until a single prisoner is left who is set free.

PSEUDOCODE :

getKillingSequencew(m, n)

Integer killingArray[n] //To store the sequence

int k =0

// Create a circular linked list of

// size n.

Node head

Node prev = head

for i = 2 to n

prev.next = new Node(i)

prev = prev.next

end

// Connect last node to first

prev.next = head;

/* while only one node is left in the

linked list*/

Node ptr1 = head

ptr2 = head

while(ptr1.next not equal to ptr1)

// Find m-th node

count =1

while(count not equal to m)

ptr2 = ptr1

ptr1 = ptr1.next

count = count +1

end

/* Remove the m-th node */

ptr2.next = ptr1.next

killingSequence[k++] = ptr1.data;

ptr1 = ptr2.next

end

killingSequence[k] = ptr1.data //Last prisoner

Print killingSequence[n]

  

ANALYSIS :

Time complexity is O(m * n) as for each execution m steps are taken and every prisoner will be executed except one. So, Number of times loop will run is m*n.

So, the complexity is O(m*n).

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.