برنامه Josephus

سلام
این برنامه به صورته یک داستانه که براتون توضیح میدم
در یک زندان تعدادی زندانی هستند که حکم اعدام دارند.قاضی ای که این حکم رو اعلام کرده گفته که یکی از این زندانی ها میتونه زنده بمونه و برای این کار روشی رو گفته و اون روش اینه:
تمام زندانی ها رو دور یک میز جمع میکنیم و از میان آنها یک نفر را برای شروع کار انتخاب میکنیم
سپس از آن نفر به بعد به صورت یک در میان اونها رو اعدام میکنیم آخرین نفری که زنده موند آزاد میشه
حالا من به دو روش این برنامه رو نوشتم:
1. با آرایه ی چرخشی
2. با لیست دو پیوندیه چرخشی
کد ها رو هم میتونین در پایین مشاهده کنین.

لیست پیوندی:

کد:

---

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
//*****************************************
//*****************************************
class node{
      private:
              friend class list;
              friend void kill(int &);
              char pname[31];
              int pnum;
              node *next;
              node *prior;
      };
//*****************************************
//*****************************************
class list{
      public:
            list();
            ~list();
            void addnode();
            void delnode(int&);
            void display();
            void kill(int&);
      private:
              int number;
              node *first;
              node *last;
      };
//*****************************************
//*****************************************
list ::list()
{
        first=last=NULL;
        number=0;
}
//*****************************************
list ::~list()
{
        node *a=first;
        delete a;
       
}
//*****************************************
void list::addnode()
{
    node *a=new node();
    if(!a)
    {
                cout<<"\nAllocation failure.";
                getch();
                exit(0);
    }
    cout<<"\nEnter name of prisoner:";
    cin>>a->pname;
    a->pnum=++number;
    if(first==NULL)
    {
                    first=last=a;
                    a->next=a;
                    a->prior=a;
    }
    else
        {
              last->next=a;
              a->prior=last;
              a->next=first;
              first->prior=a;
              last=a;
        }
}
//*****************************************
void list::delnode(int &num)
{
    node *a=first;
    while (1)
    {
          if(num== a->pnum)
          {
                  if(a ==first)
                  {
                              last->next=a->next;
                              a->next->prior=last;
                              first=first->next;
                              a->next=NULL;
                              a->prior=NULL;
                              delete a;
                              break;
                  }
                  else
                  {
                  if(a ==last)
                              last=last->prior;
                  a->prior->next=a->next;
                  a->next->prior=a->prior;
                  a->next=NULL;
                  a->prior=NULL;
                  delete a;
                  break;
                  }
          }else
                a=a->next;
    }
    number--;
}
//*****************************************
void list::display()
{
    node *a=first;
    do{
    cout<<"\n"<<a->pnum<<") "<<a->pname<<"\n\n";
    a=a->next;
    }
    while(a!=first);             
}
//*****************************************
void list::kill(int &num)
{
    node *a=first,*temp;
    int i=number;
    cout<<"\nBEGIN...";
    while(1)
            if( a->pnum==num)
                break;
            else{
                  i--;
                  if(!i)
                        while (num>number||num<0)
                        {
                              cout<<"There is no prisoner with this number.\nPlease enter new number for start:";
                              cin>>num;
                        }
                a=a->next;
                }
    while(a!=a->next)
    {
                      temp=a;
                      a->prior->next=a->next;
                      a->next->prior=a->prior;
                      a=a->next->next;
                      delete temp;
    }
    first=a;
    cout<<"\n*****************  "<<a->pname<<"  WILL ALIVE  ******************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
    cout<<"\n****************************************************";
}
//*****************************************
void menu();
//*****************************************
int main()
{
    int no,pnum,number;
    bool ch=true;
    list plist;
    menu();
    cin>>number;
    while(1)
    {
            if(number==1)
                        plist.addnode();
            else if(number==2)
            {
                       
                              cout<<"\nEnter prisoner number to delete:";
                              cin>>no;
                              plist.delnode(no);
            }
            else if(number==3)
                              plist.display();
            else if(number==4)
                              break;
            menu();
            cin>>number;
    }
    cout<<"\n\n\nNow you can enter number of prisoner that you want to begin from he or she:\n";
    cin>>pnum;
    plist.kill(pnum);
    getch();
    exit(0);
    return 0;
}
//*****************************************
void menu()
{
    cout<<"\n1.Enter a prisoner to game."
        <<"\n2.Delete a prisoner from game."
        <<"\n3.Display prisoner list."
        <<"\n4.End of prisoner.";
    cout<<"\nEnter your select.";
}
//*****************************************

---

با آرایه:

کد:

---

#include<iostream>
#include<conio.h>
using namespace std;
int main()
{
    int *a,mahal,temp,m,i,j,n,x,num;
    m=1;
    temp=-1;
    cout<<"Enter number of your prisoners:";
    cin>>x;
    a=new int[x];
    for(i=0;i<x;i++)
    *(a+i)=1;
    cout<<"\n\nEnter start number:";
    cin>>n;
    i=n-1;
    while(m)
    {
            if(a[i%x]==1)
            {
                        temp*=-1;
                        if(temp==1)
                        a[i%x]=0;
            }
            i++;
            num=0;
            for(j=0;j<x;j++)
            if(a[j]==1)
            {
                      num++;
                      mahal=j;
            }
            if(num==1)
            m=0;
    } 
    cout<<"\n\nNumber "<<mahal+1<<" is winner.";
    getch();
    return 0;
}

---

دیگه اگه تو این دوتا مشکلی دیدید به بزرگواریه خودتون ببخشید

می تونی با کلاس vector بنویسیش؟