In this whiteboard video, Professor Wool highlights the challenges, benefits and trade-offs of utilizing zero-touch automation for security policy change management. Watch and Learn!

I'm trying to find Josephus algorithm and haven't done so. Please I need help with this.

http://www.auto.tuwien.ac.at/~blieb/woop/welcome.html

1,2,3,4,5,6,7

1,2,3,5,6,7

2,3,5,6,7

2,3,5,7

2,3,7

2,3

2

the winner is # 3. I'm trying to develop an algorithm for a function

Jos(n,m)

two algorithms are in simple words

http://cut-the-knot.com/recurrence/j_solution.html

http://cut-the-knot.com/recurrence/r_solution.html

from

http://cut-the-knot.com/recurrence/flavius.html

I have the Java Applet Source Code for this if you are interested ...

m //place of person that would be gone

for a[i]=1 to n do

{

if a[m]found

a[i]=a[1+1]}

#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);

}

Your question is a matter of interest

as a theoretic problem.

Erecting a function that finds out the number that remains at last, is a matter of practical programming routine.

Do you know who was Josephus Flavius?

++++++++++++++++++++++++++

On the 1st century the Jews rebeled

against the Romans that ruled their territory. Joseph Ben-Matitiahu was

the Chief commander of the rebel at the

Galilee front (The northen part of Israel). The Jews defeated and found a sheleter at the fortress of Yodfat (which is about 30 Km. away from my place...) , surrouded by the Roman army.

As a last desperate step , they decided to commit a collective suicide.

I remeber a story describing the way how they choose the candidate to be killed next, in a 'round robin algorithm' as you present in your question.

Later on - Joseph Ben-Matitiahu crossed the lines , joined to the Romans , changed his genuine Hebrew name to Josephus Flavius and became the "official" documentator of the "Great rebel". His "The wars of the Jews" is the main source from which one can study the history of that period.

I think his caring for his people has oft been underated, and value underestimated. As an educated thinker, he tried to tell his people NOT to rebel against Rome due to probable outcome, not due to desire to become Roman. He had seen their armed forces while the zealots had not. They were certain they could handle the local police force (of Rome). Yet he tried to do his part, even if it meant in the military (filling a talent vacuum there). If it was going to be war, he'd help fortify what he could, even help them fight. But not to die without cause, for where would the culture be if everyone killed themselves off?

(altho in my mind the group in the cave were fanatical zealots, I may not recall whether there were any members of the group of people known as Zealots, but surely there was a fanaticism to first take on the Roman horde, then choose group suicide as the solution to a battle loss that does not involve having to be seen in defeat by others)

I doubt we can say he actually joined Romans, though it was thought he did at the time (a traitor, no less), being seen in their company more like he's an advisor rather than in a member of a chain gang; but at least it shows that he found a way to keep them from killing him and also get out of being a POW. This certainly excluded his capability of hanging out with any zealots remaining for any length of time. As a survivor, he also made the transition from one emporer to another, at a time when many Roman chieftains did not make the cut. The result, or end to his means are a legacy of historical work (in his eye) that vastly surpasses alternatives.

hillel,

If in that neighborhood and/or interested in those old times, how's about a visit to lounge someday when there is the time?

desperado,

I need some clarification here before I can get close to trying to pitch in for you. First are you still interested in something, and does it require C, or Visual C or what.

I thought I'd seen a couple of other threads on this issue, and that you may be handiling this problem one-on-one for another. So, what is your status?

It is also not clear to me what kind of program you want to do. Do you want to compute where to stand? Or would you like a display that just kills them off until only one is left? Or two? Do you just want to predict the positions of the ### survivors?

On my own, I'd be tempted to run linked list on original participants. Same length. But after clicking on some links on the topic and following them, it seems like an interesting simplification may be available by adding each person passed over to the end of the line.

But maybe you are aware and want to do something different. Adding at end of line obviously increases the length requirements, size of array if used, etc.

My assumption is also that you are only dealing with the fixed numbers of the Josephus problem, not a larger world of possibilities.

Have you tried any of the recommended solutions, any of the code available on the web, if so, with what effect? What went right or wrong, and where do you want to take this now?

I was very fond of the historical session that we had... It is very interesting indeed.

But - Let's switch back to our original

agenda...

I'm interested in the analytical aspect

of the problem.

The algorithmic aspect seems quite simple and not really chalanging....

Strictly speaking - Is there a "closed

function" or a "Generating function"

or something that yields "directly"

the value of Jos(N,M)?

A very well known equivalent is the analytical solution of difference equations (like the "immortal" Fibbonaci sequence...) where you get the N_th element by simple computation.

One does not need to generate the whole sequence in order to get the N_th element.

Does anybody have any clue...?

I'd like to think that once the multiline solution is presented for that method, that knowing the technique would enable a mathematical simplification to a function. Have you pursued the links?I am not that deep in math or use of summations or even fibonacci, so my ignorance has this method appear as a "generating function", being less familiar with names and terms.

First i want to precise that i'm not a native english speaker, and i'm new to this site, so i apologize for all my mistakes.

I think there could be an iterative solution, for your problem, and i will think on it when i will be less busy, and maybe there is a direct method to find the last one.

Here is a program in C implemanting a naive version of the solution, if something is not clear please ask, i hope it will be readable.

PS : Take care that the first person is the 0-th in this code

/*

* Josephus (naive)

*/

#include <stdio.h>

#include <stdlib.h>

int josephus(int,int);

void main(void)

{

fprintf(stdout,"The last one is the %d th \n",josephus(7,4));

}

int josephus(int m,int n)

{

int i,r,s=0;

int *str=(int *)calloc(m,sizeof(int)); /* Allocate memory and put 0 in it */

for(i=0;i<m-1;i++) /* Till it remain just one person */

{

r=n-1;

while(r) /* Till we don't reach the n-th person next to the last removed */

{

if(!str[s]) /* The one we consider still there ? */

{

r--; /* Yes, so if needed continue to find the next one */

s=(++s)%m;

}

while(str[s]) /* Jump to the next one till the one we consider have been removed */

{

s=(++s)%m;

}

}

str[s]++; /* Remove him */

fprintf(stderr,"%d\n",s+1)

}

/* Find the last one */

for(i=0;i<m;i++)

{

if(!str[i])

{

free(str);

return(++i);

}

}

}

int jos(int n, int m); /*where n is the number of people originally,

and m is the person removed each time.

Function returns the number of the person who

was left over. */

the_bikeman

All Courses

From novice to tech pro — start learning today.

/**************

The Josephus algorithm.

This function will return the last man standing. :)

n is the amount of people in the circle in the beginning,

while m is the mth person you delete each time.

**************/

int jos(int n, int m) {

int data[n], i, q, curr_pos = 0, curr_size = n;

for(i = 1; i <= n; i++) data[i-1] = i;

for(;;) {

if(curr_size == 1)

return data[0];

curr_pos = (curr_pos-1+m)%(curr_size)

for(q = curr_pos; q < curr_size; q++)

data[q] = data[q+1];

--curr_size;

}

}

Hope this works for you!

the_bikeman