Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Help with algorithm

Posted on 2000-02-13
2
Medium Priority
?
212 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 400 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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
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…

670 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