Solved

# nietod..Josephus algorithm with circular list

Posted on 2000-02-28

I have made so fa this circular list and I'm trying to implement the Josephus algorithm which you solved using arrys with it. I'm stuck. it doesn't do what I want and i can't find my error.

here is the Cicular List class:

// Circular Linked List Class

#ifndef CIRCLIST_H

#define CIRCLIST_H

#include <iostream.h>

template <class T>

class CircularList {

public:

CircularList();

~CircularList();

int Add(T item); // return -1 if out of memory

int Remove(int index);

int Get(int index, T&item) const; // return -1 if not gotten

int Find(T item) const; // return -1 if not found

int Empty() const { return size==0; }

int Size() const { return size; }

struct Node {

T data;

Node *left, *right;

};

private:

Node *head;

int size;

};

//----------------------------//

template <class T>

CircularList<T>::CircularList() {

head=new Node;

head->right=head;

head->left=head;

size=0;

}

//----------------------------//

template <class T>

CircularList<T>::~CircularList() {

while (Size()>0) Remove(0);

delete head;

}

//----------------------------//

template <class T>

int CircularList<T>::Add(T item) {

Node *temp, *cur;

temp = new Node; // get a new node and fill with data

if (temp==NULL) { cout << "Out of memory for linked list node allocation: Add() failed." << endl; return -1; }

temp->data = item;

cur = head->right;

while(cur != head && cur->data < temp->data) {

cur=cur->right;

}

temp->right = cur;

temp->left = cur->left;

cur->left->right = temp;

cur->left = temp;

size++; // adjust size

return 1;

}

//----------------------------//

template <class T>

int CircularList<T>::Remove(int index) {

if (Empty() || index<0 || index>=Size() ) return -1;

Node *cur;

cur = head->right;

for (int i=0; i<index; i++) {

cur=cur->right;

} // at end of loop, cur is pointing

// to the node to delete

cur->left->right = cur->right;

cur->right->left = cur->left;

delete cur; // free up space

size--; // adjust size

return size;

}

//----------------------------//

template <class T>

int CircularList<T>::Get(int index, T &item) const { // similar to Remove

if (Empty() || index<0 || index>=Size() ) return -1;

Node *cur;

cur = head->right;

for (int i=0; i<index; i++) {

cur=cur->right;

} // at end of loop, cur is pointing

// to the node to get

item=cur->data; // transfer data

return 1;

}

//----------------------------//

template <class T>

int CircularList<T>::Find(T item) const {

if (Empty()) return -1;

int index=0;

Node *cur=head->right;

while (cur!=head && item!=cur->data) {

cur=cur->right;

index++;

}

return (cur==head ? -1 : index);

}

#endif

Here is the main I have done so far:

/*Josephus*/

#include <iostream.h>

#include "Circlist.h"

main()

{

CircularList <int> P;

int n;

int m;

cout<<"Enter the amount of people in the circle:\n";

cin>>n;

cout<<"Enter what m-th person you want to take out:\n";

cin>>m;

int z=n;

for(int i=1; i<=n; i++)

{

P.Add(i);

}

int x=1;

for(i=1; i<=z; i++)

{

while(n!=1)

{

if(x==m)

{

P.Remove(i);

x=0;

n--;

}

x++;

}

cout<<i;

}

cout<<P.Find(n);

return(0);

}

Need Help!!!!