C++ Josephus 2

This programs involves manipulating a substring of a string

Page 1 of 1

10 Replies - 4013 Views - Last Post: 23 September 2010 - 08:44 PM Rate Topic: -----

#1 qwert12345   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

C++ Josephus 2

Posted 21 September 2010 - 04:04 AM

Write a program for what is called the Josephus problem>

The Josephus problem is the following: n people called a, b, c, d,...(starting
with index 0 to index n-1 are arranged in a circle facing the center) with a in
the position of 12 o'clock and the others arranged clockwise so that the last
person is immediately to the right of a.

let k>=1 be an integer : the so called "skip" number.

illustration using n=10 ( a thru j) and k=3.

People: abcdefghij

a kills "a+3" i.e., d surviving people now: abcefghij
then the person next to the killed person (i.e., to the left of d, in this case e)
e) kills "e+3" (h) surviving people now: abcefgij
then the person to the left of h (=i) kills "i+3" (B) WATCH
surviving people now: acefgij
then the person to the left of b (=c) kills "c+3" (g)
surviving people now: acefij

and so on until only k (=3) people are left

your program should display the sequence of who kills who and the
survivors in clockwise order starting from the 12 O'clock position


This is the My Output:

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills d
Suvivors : ebcdefghi e kills d
Suvivors : ebcdefgh e kills d
Suvivors : ebcdefg e kills d
Suvivors : ebcdef e kills d
Suvivors : ebcde e kills d
Suvivors : ebcd e kills d
Josephus Program Written By Jasmin Prewitt
Press any key to continue . . .

As you can see the first part is good but my program only killed d and d is still a suvivors and a should be a suvivors but its killed off some how...

This is what the output should look like:


for n=10, k=3

========================
abcdefghij k=3

suvivors
--------
abcdefghij : a kills d
abcefghij : e kills h
abcefgij : i kills b
acefgij : c kills g
acefij : i kills c
aefij : e kills j
aefi : a kills i

final survivors are:
aef

#include <iostream>
#include <cstring>
using namespace std;

int main() 
{
   int NumberofPeople;
   int SkipNumber;
   int Suvivors = 0;
   int FinalSuvivors = 0;
   int NextPerson = 0;
   int StartingPoint = 0;
   int CurrentPoint = 0;
   char People[]  = "abcdefghijklmnopqrstuvwxyz";
   
cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
cout << "Enter Number of People: ";
cin  >> NumberofPeople;
    while (NumberofPeople > 26) 
        {
                cout << "ERROR: The Number of People is Too Big." << endl;
                cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
                cout << "Enter Number of People: ";
                cin  >> NumberofPeople;
        }

        
        
    
cout << "Skip Number Can Not Be No More than 25." << endl; 
cout << "Enter Skip Number: ";
cin  >> SkipNumber;

     while (SkipNumber > 25) 
        {
                cout << "ERROR: The Skip Number is Too Big." << endl;
                cout << "Skip Number Can Not Be No More than 25." << endl; 
                cout << "Enter Skip Number: ";
                cin  >> SkipNumber;
                
        }
        
cout << "People: " ;
  for (int tempsize = 0; tempsize < NumberofPeople; tempsize++ )
            {
               Suvivors++;
               cout << People[tempsize];
               
            }
        
cout << endl;
cout << "Skip Number : " << SkipNumber << endl;
cout << "---------------------------------------" << endl;

   while(Suvivors != SkipNumber) 
   { 
    cout << "Suvivors : " ;   
        for(int tempsize = 0; tempsize <= Suvivors -1; tempsize++)
        {
              cout << People[tempsize];  
        }
    cout <<" " << People[StartingPoint] << " kills " << People[StartingPoint + SkipNumber] << endl;
    People[CurrentPoint] = People[StartingPoint + SkipNumber] + 1;
    People[StartingPoint] = People[CurrentPoint];
    --Suvivors;
   
        
   }
      

        system("pause");
        return 0;


}




Is This A Good Question/Topic? 0
  • +

Replies To: C++ Josephus 2

#2 CTphpnwb   User is offline

  • D.I.C Lover
  • member icon

Reputation: 3810
  • View blog
  • Posts: 13,833
  • Joined: 08-August 08

Re: C++ Josephus 2

Posted 21 September 2010 - 07:48 AM

You're just shrinking the size of People[] by one, but you need to shift the characters to the left as well.
Was This Post Helpful? 0
  • +
  • -

#3 qwert12345   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: C++ Josephus 2

Posted 21 September 2010 - 03:47 PM

View PostCTphpnwb, on 21 September 2010 - 06:48 AM, said:

You're just shrinking the size of People[] by one, but you need to shift the characters to the left as well.



How do I shift the characters to the left?? By using another for loop in the while loop
Was This Post Helpful? 0
  • +
  • -

#4 NickDMax   User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: C++ Josephus 2

Posted 21 September 2010 - 04:08 PM

To be honest it would be best if you were to write a function to do it... but basically you need a little loop to shift letters down one place in the array.

example (note you may wish to write your own version that makes more sense to you -- in here I used pointers pretty heavily).

#include <iostream>

using namespace std;

void deleteChar(char* str, int index);

int main() {
    char test[] = "observe";
    cout << "Before: " << test << endl;
    deleteChar(test, 0);
    deleteChar(test, 0);
    deleteChar(test, 2);
    deleteChar(test, 2);
    cout << "After: " << test << endl;
    return 0;
}


void deleteChar(char* str, int index) {
    char *ptr = str;
    //first make sure that index is inside the string (note strings are teminated by a null)
    for (int i = 0; i < index && *ptr!=0; ++i, ++ptr) { /*do nothing*/ } 
    //ptr now points to the index location.
    str = ptr++;
    //str point to index location and ptr points to index + 1
    while (*str!=0) { //loop until str is a null
        *str = *ptr;
        str++;
        ptr++;
    }
}

Was This Post Helpful? 0
  • +
  • -

#5 Alex6788   User is offline

  • kitties == adorable


Reputation: 144
  • View blog
  • Posts: 1,667
  • Joined: 15-July 10

Re: C++ Josephus 2

Posted 21 September 2010 - 04:14 PM

Just a little helpful tidbit don't use
system("pause"); 
unless your teacher makes you. Use
cin.get();
instead and sometimes that won't work if there is already input in the buffer then use
cin.ignore();
cin.get();


Hope i was of help and if i was please click the green plus button in the bottom right hand corner of this post.

This post has been edited by Alex6788: 21 September 2010 - 04:15 PM

Was This Post Helpful? 0
  • +
  • -

#6 qwert12345   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: C++ Josephus 2

Posted 22 September 2010 - 05:53 PM

View PostNickDMax, on 21 September 2010 - 03:08 PM, said:

To be honest it would be best if you were to write a function to do it... but basically you need a little loop to shift letters down one place in the array.

example (note you may wish to write your own version that makes more sense to you -- in here I used pointers pretty heavily).

#include <iostream>

using namespace std;

void deleteChar(char* str, int index);

int main() {
    char test[] = "observe";
    cout << "Before: " << test << endl;
    deleteChar(test, 0);
    deleteChar(test, 0);
    deleteChar(test, 2);
    deleteChar(test, 2);
    cout << "After: " << test << endl;
    return 0;
}


void deleteChar(char* str, int index) {
    char *ptr = str;
    //first make sure that index is inside the string (note strings are teminated by a null)
    for (int i = 0; i < index && *ptr!=0; ++i, ++ptr) { /*do nothing*/ } 
    //ptr now points to the index location.
    str = ptr++;
    //str point to index location and ptr points to index + 1
    while (*str!=0) { //loop until str is a null
        *str = *ptr;
        str++;
        ptr++;
    }
}



so now I'm trying to create a function that will "kill" the chars of the string off one by one and I'm still getting the same kinda output, which is still just shrinking the size of People[] by one:

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills e
Suvivors : fbcefghij f kills f
Suvivors : gbcfghij g kills g
Suvivors : hbcghij h kills h
Suvivors : ibchij i kills i
Suvivors : jbcij j kills j
Suvivors : kbcj k kills k
Press any key to continue . . .


with this code:
#include <iostream>
#include <cstring>
using namespace std;
void KillChar(char* temp, int index);
int main() 
{
   int NumberofPeople;
   int SkipNumber;
   int Suvivors = 0;
   int FinalSuvivors = 0;
   int NextPerson = 0;
   int StartingPoint = 0;
   int CurrentPoint = 0;
   char People[]  = "abcdefghijklmnopqrstuvwxyz";
   
cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
cout << "Enter Number of People: ";
cin  >> NumberofPeople;
    while (NumberofPeople > 26) 
        {
                cout << "ERROR: The Number of People is Too Big." << endl;
                cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
                cout << "Enter Number of People: ";
                cin  >> NumberofPeople;
        }

        
        
    
cout << "Skip Number Can Not Be No More than 25." << endl; 
cout << "Enter Skip Number: ";
cin  >> SkipNumber;

     while (SkipNumber > 25) 
        {
                cout << "ERROR: The Skip Number is Too Big." << endl;
                cout << "Skip Number Can Not Be No More than 25." << endl; 
                cout << "Enter Skip Number: ";
                cin  >> SkipNumber;
                
        }
        
cout << "People: " ;
  for (int tempsize = 0; tempsize < NumberofPeople; tempsize++ )
            {
               Suvivors++;
               cout << People[tempsize];
               
            }
        
cout << endl;
cout << "Skip Number : " << SkipNumber << endl;
cout << "---------------------------------------" << endl;

   while(Suvivors != SkipNumber) 
   { 
    cout << "Suvivors : " ;   
        for(int tempsize = 0; tempsize <= Suvivors -1; tempsize++)
        {
              cout << People[tempsize];  
        }
        
       KillChar(People, StartingPoint +SkipNumber);  
    cout <<" " << People[StartingPoint] << " kills " << People[StartingPoint + SkipNumber] << endl;
    People[CurrentPoint] = People[(StartingPoint + 1) + SkipNumber];
    //People[StartingPoint] = People[CurrentPoint];
    --Suvivors;
   
        
   }
      

        system("pause");
        return 0;


}


void KillChar(char* temp, int index) {
    char *ptr = temp;
    
    for (int i = 0; i < index && *ptr!=0; ++i, ++ptr) 
    { } 
    
    temp = ptr++;
    
  
    
    while (*temp!=0) 
    { 
        *temp = *ptr;
        temp++;
        ptr++;
    }
}


Was This Post Helpful? 0
  • +
  • -

#7 n8wxs   User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: C++ Josephus 2

Posted 22 September 2010 - 06:59 PM

You are not doing modulus arithmetic on the array indicies. As the array shrinks you need to 'wrap' around it's length. Like this:

...
Suvivors = NumberofPeople;

while(Suvivors != SkipNumber) 
{ 
    cout << "Suvivors : " ;   

    for(int tempsize = 0; tempsize < Suvivors; tempsize++)
    {
        cout << People[tempsize];  
    }

    cout <<" " << People[StartingPoint] << " kills " << People[(StartingPoint + SkipNumber) % Suvivors] << endl;

    StartingPoint = (StartingPoint + SkipNumber) % Suvivors;

    KillChar(People, StartingPoint);  

    --Suvivors;
}

cout << "Final survivors: ";

for (int i = 0; i < Suvivors; i++)
    cout << People[i];

cout << endl;
...



Output:

Quote

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills d
Suvivors : abcefghij e kills h
Suvivors : abcefgij i kills b
Suvivors : acefgij c kills g
Suvivors : acefij i kills c
Suvivors : aefij e kills j
Suvivors : aefi k kills i
Final survivors: aef

Hit ENTER to continue...

This post has been edited by n8wxs: 22 September 2010 - 07:00 PM

Was This Post Helpful? 0
  • +
  • -

#8 qwert12345   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: C++ Josephus 2

Posted 23 September 2010 - 04:58 AM

View Postn8wxs, on 22 September 2010 - 05:59 PM, said:

You are not doing modulus arithmetic on the array indicies. As the array shrinks you need to 'wrap' around it's length. Like this:

...
Suvivors = NumberofPeople;

while(Suvivors != SkipNumber) 
{ 
    cout << "Suvivors : " ;   

    for(int tempsize = 0; tempsize < Suvivors; tempsize++)
    {
        cout << People[tempsize];  
    }

    cout <<" " << People[StartingPoint] << " kills " << People[(StartingPoint + SkipNumber) % Suvivors] << endl;

    StartingPoint = (StartingPoint + SkipNumber) % Suvivors;

    KillChar(People, StartingPoint);  

    --Suvivors;
}

cout << "Final survivors: ";

for (int i = 0; i < Suvivors; i++)
    cout << People[i];

cout << endl;
...



Output:

Quote

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills d
Suvivors : abcefghij e kills h
Suvivors : abcefgij i kills b
Suvivors : acefgij c kills g
Suvivors : acefij i kills c
Suvivors : aefij e kills j
Suvivors : aefi k kills i
Final survivors: aef

Hit ENTER to continue...

for your version of this program, did you use the KillChar function that is in my program?? That's not deleting the letters one by one in my program and I don't know why.

void KillChar(char* temp, int index) {
    char *ptr = temp;
    
    for (int i = 0; i < index && *ptr!=0; ++i, ++ptr) 
    { } 
    
    temp = ptr++;
    
  
    
    while (*temp!=0) 
    { 
        *temp = *ptr;
        temp++;
        ptr++;
    }
}


Was This Post Helpful? 0
  • +
  • -

#9 janotte   User is offline

  • code > sword
  • member icon

Reputation: 991
  • View blog
  • Posts: 5,141
  • Joined: 28-September 06

Re: C++ Josephus 2

Posted 23 September 2010 - 06:44 AM

Put a comment for every line of code in your killChar function immediately above the line.
Exactly explain what you think each line does.

Do those comments add up to a set of instructions that will get what you need done, done?
Try it and see.
Was This Post Helpful? 0
  • +
  • -

#10 qwert12345   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 169
  • Joined: 26-October 08

Re: C++ Josephus 2

Posted 23 September 2010 - 08:16 PM

View Postjanotte, on 23 September 2010 - 05:44 AM, said:

Put a comment for every line of code in your killChar function immediately above the line.
Exactly explain what you think each line does.

Do those comments add up to a set of instructions that will get what you need done, done?
Try it and see.


Well, KillChar function is really taken from NickDMax's example of deleting a letter from a string in a function called deleteChar.

Comparing the two outputs of my program with and without the function KillChar, the function is just deleting the first letter of the string after each turn and for the straight points, its just going down the string and the same thing is happening for the letters in the skip number position of the string.

I'm thinking that the line:
People[StartingPoint] = People[(StartingPoint +1) + SkipNumber % Suvivors];


would solve this problem, because it should assign the new starting position in the string, but i think not having a place to store the starting point letters and the killed letter in two different new strings, its messing up my program.


Output without KillChar function:

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghijkl a kills d
Suvivors : ebcdefghijk e kills d
Suvivors : ebcdefghij e kills d
Suvivors : ebcdefghi e kills d
Suvivors : ebcdefgh e kills d
Suvivors : ebcdefg e kills d
Suvivors : ebcdef e kills d
Suvivors : ebcde e kills d
Suvivors : ebcd e kills d

Final 3 Survivors are :
ebc
Press any key to continue . . .

Output with KillChar function:

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghijkl a kills d
Suvivors : bcdefghijkl b kills e
Suvivors : cdefghijkl c kills f
Suvivors : defghijkl d kills g
Suvivors : efghijkl e kills h
Suvivors : fghijkl f kills i
Suvivors : ghijkl g kills j
Suvivors : hijkl h kills k
Suvivors : ijkl i kills l

Final 3 Survivors are :
jkl
Press any key to continue . . .

This post has been edited by qwert12345: 24 September 2010 - 02:44 AM

Was This Post Helpful? 0
  • +
  • -

#11 n8wxs   User is offline

  • --... ...-- -.. . -. ---.. .-- -..- ...
  • member icon

Reputation: 972
  • View blog
  • Posts: 3,878
  • Joined: 07-January 08

Re: C++ Josephus 2

Posted 23 September 2010 - 08:44 PM

The People array is not sorted. It is simply shortened by remove a letter and shifting left the remaining letters in the array.

This code:

#include "stdafx.h"

#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>

using namespace std;

void KillChar(char*, int);

int _tmain(int argc, _TCHAR* argv[])
{
    int NumberofPeople;
    int SkipNumber;
    int Suvivors = 0;
    int FinalSuvivors = 0;
    int NextPerson = 0;
    int StartingPoint = 0;
    int CurrentPoint = 0;

    char People[]  = "abcdefghijklmnopqrstuvwxyz";

    cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
    cout << "Enter Number of People: ";
    cin  >> NumberofPeople;

    while (NumberofPeople > 26) 
    {
        cout << "ERROR: The Number of People is Too Big." << endl;
        cout << "Number of People Can Not Be No More than 26 (a thru z)" << endl;
        cout << "Enter Number of People: ";
        cin  >> NumberofPeople;
    }

    cout << "Skip Number Can Not Be No More than 25." << endl; 
    cout << "Enter Skip Number: ";
    cin  >> SkipNumber;

    while (SkipNumber > 25) 
    {
        cout << "ERROR: The Skip Number is Too Big." << endl;
        cout << "Skip Number Can Not Be No More than 25." << endl; 
        cout << "Enter Skip Number: ";
        cin  >> SkipNumber;
    }

    cout << "People: " ;
    for (int tempsize = 0; tempsize < NumberofPeople; tempsize++ )
    {
        cout << People[tempsize];

    }

    cout << endl;
    cout << "Skip Number : " << SkipNumber << endl;
    cout << "---------------------------------------" << endl;

    Suvivors = NumberofPeople;

    while(Suvivors != SkipNumber) 
    { 
        cout << "Suvivors : " ;   

        for(int tempsize = 0; tempsize < Suvivors; tempsize++)
        {
            cout << People[tempsize];  
        }

        cout <<" " << People[StartingPoint] << " kills " << People[(StartingPoint + SkipNumber) % Suvivors] << endl;

        StartingPoint = (StartingPoint + SkipNumber) % Suvivors;

        KillChar(People, StartingPoint);  

        --Suvivors;
    }

    cout << "Final survivors: ";

    for (int i = 0; i < Suvivors; i++)
        cout << People[i];

    cout << endl;

    cin.clear();
    cin.sync();
    cout << endl << "Hit ENTER to continue..." << endl;
    cin.get();

    return 0;
}

void KillChar(char* temp, int index) {
    char *ptr = temp;

    for (int i = 0; i < index && *ptr!=0; ++i, ++ptr) 
    { } 

    temp = ptr++;

    while (*temp!=0) 
    { 
        *temp = *ptr;
        temp++;
        ptr++;
    }
}




produces this output:

Quote

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills d
Suvivors : abcefghij e kills h
Suvivors : abcefgij i kills b
Suvivors : acefgij c kills g
Suvivors : acefij i kills c
Suvivors : aefij e kills j
Suvivors : aefi k kills i
Final survivors: aef

Hit ENTER to continue...


Edit:

This line is wrong: Suvivors : aefi k kills i

The case of the last element of the current array being removed means the starting position needs to reset:

...
while(Suvivors != SkipNumber) 
{ 
    cout << "Suvivors : " ;   

    for(int tempsize = 0; tempsize < Suvivors; tempsize++)
    {
        cout << People[tempsize];  
    }

    // reset if last position was removed
    if (StartingPoint == Suvivors)
        StartingPoint = 0;

    cout <<" " << People[StartingPoint] << " kills " << People[(StartingPoint + SkipNumber) % Suvivors] << endl;

    StartingPoint = (StartingPoint + SkipNumber) % Suvivors;

    KillChar(People, StartingPoint);  

    --Suvivors;
}
...



Output:

Quote

Number of People Can Not Be No More than 26 (a thru z)
Enter Number of People: 10
Skip Number Can Not Be No More than 25.
Enter Skip Number: 3
People: abcdefghij
Skip Number : 3
---------------------------------------
Suvivors : abcdefghij a kills d
Suvivors : abcefghij e kills h
Suvivors : abcefgij i kills b
Suvivors : acefgij c kills g
Suvivors : acefij i kills c
Suvivors : aefij e kills j
Suvivors : aefi a kills i
Final survivors: aef

Hit ENTER to continue...

This post has been edited by n8wxs: 24 September 2010 - 12:13 PM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1