Solved

Help with algorithm

Posted on 2000-02-13
2
210 Views
Last Modified: 2006-11-17
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
Comment
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
  • Learn & ask questions
2 Comments
 

Author Comment

by:milalik
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

by:
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

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
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.

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question