Solution Library

Implementing Josephus Problem Using C++ Program

Question

Use a circular list to implement the Josephus Problem.  In the Josephus Problem, there is originally a circle of people numbered from one to n.  Some number is chosen as the starting person, and an interval of size m is selected.  Then, starting at the chosen person, every mth person is eliminated until only one person remains.  The output should be a list of the eliminated people in the order of elimination, and a statement of which person remains.  Do this once with the circular list class implemented with nodes and pointers and once as a circular array with some method of designating a person as "not there."  The two implementations of the circular list should be designed to require no change to the code outside the circular list class.  Both circular list classes should have functions AdvanceN(n) and DeleteThis(x), where AdvanceN(n) returns a new position in the list that is n places further on, and DeleteThis(x) deletes person x and returns the position previous to x.

·    Solve without using a Template
·    there are two parts to this question - Do this once with the circular list class implemented with nodes and pointers and once as a circular array (do not use pointers here.  Integers will work fine) with some method of designating a person as "not there."
·    The program should allow the user to cin >>startingPerson and cin>>intervalSize
The class(es) should be declared in a separate .h file(s).

Summary

The question belongs to Computer Science and it discusses about writing a program in C++ which implements Josephus problem. Josephus problem is a classical problem on counting out people. This problem has been implemented and solved using C++ program.

Total Word Count NA

Download Full Solution

Comments

  • HWA
    Rasha

    this is a very good website

  • HWA
    maani

    I have 50 questions for the same test your page is showing only 28

  • HWA
    joeanne

    hi can you please help or guide me to answer my assignments. thanks

  • HWA
    joeanne

    hi can anyone help or guide me to my assignments. thanks

  • HWA
    Monik


  • HWA
    Cristina

    This solution is perfect ...thanks

  • HWA
    Janete

    Hello Allison,I love the 2nd image that you did! I also, had never heard of SumoPaint, is something that I will have to exolpre a bit! I understand completely the 52 (or so) youtube videos that you probably watched. Sometimes they have what you want, sometimes they don't! However, it is always satisfying when you are able to produce something that you have taught yourself. Great job!Debra 0 likes

  • HWA
    Sandeep

    Perfect bank of solution. 

  • HWA
    Oxana

    great !

  • HWA
    Paul Brandon-Fritzius

    thanks for the quick response. the solution looks good. :)

  • HWA
    tina Johnson

    thnx for the answer. it was perfect. just the way i wanted it. 

  • HWA
    Giuseppe

    works fine.