glxhyt

著名的Josephus問題

　　據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。

　　然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

  1#ifndef _RING_H_
  2#define _RING_G_
  3#include <iostream>
  4
  5using namespace std;
  6
  7typedef struct tag_Student
  8{
  9    int iNumber;
 10    tag_Student *pNext;
 11    tag_Student():pNext(NULL){}
 12    
 13
 14}st_Student;
 15class CRing
 16{
 17private:
 18    int m_NumCount;
 19    int m_Interval;
 20
 21public:
 22    CRing(int NumCount, int Interval);
 23    ~CRing();
 24
 25    void FindOutOfChidren(st_Student * p);
 26
 27    void DeleteChidren();
 28    void ShowLoseChidren();
 29    void ShowWinChidern();
 30
 31    void PrintChidren(st_Student *Head);
 32
 33public:
 34    st_Student *pCurrent;
 35    st_Student *pDelete;
 36
 37    st_Student *pHead;
 38
 39};
 40
 41#endif
 42
 43
 44#ifndef _JOSEPHUS_H_
 45#define _JOSEPHUS_H_
 46
 47
 48class Josephus
 49{
 50private:
 51    int m_iInterval;
 52    int m_iNumCount;
 53
 54public:
 55    Josephus(int Interval, int NumCount);
 56    
 57    void Inital();
 58
 59};
 60
 61#endif
 62
 63
 64#include "stdafx.h"
 65
 66#include "ring.h"
 67
 68CRing::CRing(int NumCount , int Interval)
 69{
 70    /**//*
 71    st_Student *Temp;
 72    m_NumCount = NumCount;
 73    m_Interval = Interval;
 74    pHead = new st_Student[NumCount];
 75
 76    Temp = pHead;
 77   
 78    for(int i = 1; i <= NumCount; ++i)
 79    {
 80      Temp->iNumber = i;
 81      Temp->pNext = pHead +( i % NumCount);
 82      Temp = Temp->pNext;
 83    }
 84
 85    Temp = pHead;
 86    pCurrent = Temp;
 87    */
 88
 89    m_NumCount = NumCount;
 90    m_Interval = Interval;
 91    st_Student *t, *q;
 92    pHead = new st_Student;
 93    t = pHead;
 94    for(int j = 1; j <= NumCount; ++j)
 95    {
 96
 97        //pHead = new st_Student;
 98        t->iNumber = j;
 99        t->pNext = new st_Student;
100        
101        q = t;//關鍵的一部是為了記錄最后一個節點，連成一個串
102
103        t =t->pNext;
104    }
105
106    q->pNext = pHead;
107
108    pCurrent = pHead;
109
110
111}
112void CRing::FindOutOfChidren(st_Student * p)
113{
114
115    for(int i=0 ; i < m_Interval; ++i)
116    {
117            pCurrent = p;
118            p = p->pNext;
119
120    }
121
122}
123
124void CRing::DeleteChidren()
125{
126    pDelete = pCurrent->pNext;
127
128    pCurrent->pNext = pCurrent->pNext->pNext;
129    pCurrent = pCurrent->pNext;
130
131}
132
133void CRing::PrintChidren(st_Student *Head)
134{
135    for(int i = 0; i < m_NumCount; ++i)
136    {
137        cout<<"chideren Number"<<Head->iNumber<<" ";
138        Head = Head->pNext;
139    }
140
141}
142
143void CRing::ShowLoseChidren()
144{
145    cout<<"Lose chidren"<<pDelete->iNumber<<endl;
146}
147
148CRing::~CRing()
149{
150    delete [] pHead;
151}
152
153
154#include "stdafx.h"
155#include "ring.h"
156#include "Josephus.h"
157
158Josephus::Josephus(int Interval, int NumCount)
159{
160    m_iInterval = Interval;
161    m_iNumCount = NumCount;
162
163}
164
165void Josephus::Inital()
166{
167
168
169    CRing cr(m_iNumCount, m_iInterval);
170
171    //cr.PrintChidren(cr.pHead);
172    for(int j = 0; j < m_iNumCount; ++j)
173    {
174
175        cr.FindOutOfChidren(cr.pCurrent);
176
177        cr.DeleteChidren();
178        cr.ShowLoseChidren();
179
180
181    }
182}
183
184
185
186// JosephusQuestion.cpp : 定義控制臺應用程序的入口點。
187//
188
189#include "stdafx.h"
190#include "Josephus.h"
191
192int _tmain(int argc, _TCHAR* argv[])
193{
194
195    Josephus J(2, 41);
196    J.Inital();
197    return 0;
198}
199