Wednesday, 2018-11-14, 11:26 AM
Logged in as Guest | Group "Guests"Welcome Guest | RSS

Love Makes The World Go Round

Site Menu
Tag Board
Site Working Days

File Catalog

Main » Files » Codes » Data Structure

约瑟夫问题(Josephus Problem)
[ Download from this server (2.4 Kb) ] 2011-10-12, 6:30 PM
/* 
* 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
 */
Category: Data Structure | Added by: tes1991
Views: 603 | Downloads: 187 | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Tags...
Tencent
Statistics

Total online: 1
Guests: 1
Users: 0

Copyright MyCorp © 2018