Solved

Help with algorithm

Posted on 2000-02-13
2
207 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
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

Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

Question has a verified solution.

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

Suggested Solutions

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
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.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

770 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