/* * Copyright TES@NPU * School of Automation InfoSec * All rights reserved. * * FileName: Josephus Problem.cpp * * Version: 1.0 * * Updated @ Oct. 12 2011 * Finished @ Oct. 12 2011 */
#include <iostream> using namespace std;
class List { // circular list of chars public: List (int = 0); friend ostream& operator<<(ostream&, const List&); int size() const { return _size; } bool empty() const { return _size == 0; } char last() const { return _last->_ch; } char kill(int);
protected: struct Node { Node (const char& ch=0) : _ch(ch) { } char _ch; Node* _next; }; Node* _last; // points to last node int _size; };
int main() { int n; int skip; cout << "Enter number of soldiers: "; cin >> n; List list(n); cout << "\t\t" << list; cout << "Enter skip number: "; cin >> skip; while (list.size() > 1) { cout << '\t' << list.kill(skip) << " killed" << list; } cout << list.last() << " survived.\n"; }
List::List(int n) : _size(n) { _last = new Node('A'+n-1); Node *p = _last; for (int i=0; i<n-1; i++) p = p->_next = new Node('A'+i); p->_next = _last; }
ostream& operator<<(ostream& ostr, const List& list) { ostr << "\tsize=" << list._size; if (list.empty()) cout << ":\t()\n"; else { List::Node* p = list._last->_next; // first node ostr << ": (" << p->_ch; for (p = p->_next; p != list._last->_next; p = p->_next) ostr << "," << p->_ch; ostr << ")\n"; } return ostr; }
char List::kill(int k) { static Node* p = _last; for (int i=0; i<k; i++) // advance k nodes p = p->_next; Node* temp = p->_next; char killed = temp->_ch; p->_next = temp->_next;
if (temp == _last) // reset _last, if deleted _last = p; delete temp; --_size; return killed; }
/* ---------- Output in VC++2008: ---------- Enter number of soldiers: 10 size=10: (A,B,C,D,E,F,G,H,I,J) Enter skip number: 3 D killed size=9: (A,B,C,E,F,G,H,I,J) H killed size=8: (A,B,C,E,F,G,I,J) B killed size=7: (A,C,E,F,G,I,J) G killed size=6: (A,C,E,F,I,J) C killed size=5: (A,E,F,I,J) J killed size=4: (A,E,F,I) I killed size=3: (A,E,F) A killed size=2: (E,F) F killed size=1: (E) E survived. */
/* C++的编译器还是比较弱的。因此，能够进行完善的自我检查，就好好检查。 不要过分的相信或者依赖编译器。 否则，你懂得。----By TES@NPU */
| 