Solved

# Help with algorithm

Posted on 2000-02-13
211 Views
I got this algorithm for a function that solves Josephus algorithm. and I will like to translate it to c++.
In C langiage:

#include <stdio.h>
#include <stdlib.h>

int josef(int num, int skip)
{
char *vec;
int i;
int curPtr;
int numLive = num;

vec = (char *)malloc(num+1);
for(i=1 ; i<=num ; i++)
vec[i] = 1;

curPtr = 1;
while(numLive > 1)
{
i = 1;
while(i<skip)
{
curPtr++;
if(curPtr > num)
curPtr = 1;

if(vec[curPtr])
i++;
}

vec[curPtr] = 0;  /* KILL him*/

curPtr++;
if(curPtr > num)
curPtr = 1;

numLive--;
}

/* Find the one LIVE */
for(i=1 ; i<=num ; i++)
if(vec[i])
return(i);

return(-1);
}

What I have done so far in C++:

Jos(n,m)
for i=0 to n
{a[i]=i+1;}
while n>i  do
for i=0 to n
{
if( a[i]!=0)
{
count=count+1;
if (count==m)
{
a[i]=0;
count=0;
}
}
}

I'm I doing it okay?
what else do I need?
0
Question by:milalik
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

Author Comment

ID: 2517044
josephus problem is related to the following. Begining with n people arranged in a circle. Starting with the first person, count continuosly around the circle removing every m-th person until only one remains.Example n=7 and m=3
1,2,3,4,5,6,7
1,2,4,5,6,7
1,2,4,5,7
1,4,5,7
1,4,5
1,4
4
0

LVL 22

Accepted Solution

nietod earned 100 total points
ID: 2517076
The C code _IS_ C++ code.  So you can just use that.  however it can be made a little more "C++ish"  (Also it has a memory leak that this fixes.)

#include <stdio.h>
#include <stdlib.h>

int josef(int num, int skip)
{
char *vec = new char[num + 1];
int numLive = num;

for(int i=1 ; i<=num ; i++)
vec[i] = 1;

int curPtr = 1;
while(numLive > 1)
{
int i = 1;
while(i<skip)
{
curPtr++;
if(curPtr > num)
curPtr = 1;
if(vec[curPtr])
i++;
}

vec[curPtr] = 0;  /* KILL him*/
curPtr++;
if(curPtr > num)
curPtr = 1;
numLive--;
}

int RetVal = -1;

/* Find the one LIVE */
for(int i=1 ; i<=num ; i++)
if(vec[i])
{
RetVal = i;
break;
}

delete [] vec;
return (RetVal);
}
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
###### Suggested Courses
Course of the Month11 days, 3 hours left to enroll