???? 很經(jīng)典的"轉(zhuǎn)圈數(shù)數(shù)踢人"問題,老早以前做的東西
???? 這里是我的解法,利用STL里的List構(gòu)建Ring List
???? 頭文件:
? //:This part is partly from Bruce Eckel's source code .
// thought he don't hear of me at all ^_^
// Making a "ring" data structure from the STL
#ifndef RING_H
#define RING_H

#include<iterator>
#include<list>
using namespace std;

template <class Type> class Ring{
?list<Type> lst;
public:

?class iterator;
?friend class iterator;
?class iterator :public std::iterator<std::bidirectional_iterator_tag,Type,ptrdiff_t>{
??typename list<Type>::iterator it;
??list<Type>* r;

?public:
??iterator(list<Type>&lst,const typename list<Type>::iterator& i):it(i),r(&lst){}

??bool operator==(const iterator& x)const{
???return it==x.it;
??}

??bool operator!=(const iterator& x)const{
???return!(*this==x);
??}

??typename list<Type>::reference operator*()const{
???return *it;
??}

??iterator& operator++(){
???++it;
???if(it==r->end())
????it=r->begin();
???return *this;
??}

??iterator operator++(int){
???iterator tmp=*this;
???++*this;
???return tmp;
??}

??iterator &operator--(){
???if(it==r->begin())
????it=r->end();
???--it;
???return *this;
??}
??iterator operator--(int){
???iterator tmp=*this;
???--*this;
???return tmp;
??}

??iterator insert(const Type& x){
???return iterator(*r,r->insert(it,x));
??}
??
??//I have to recognize that the iterator is not so smart as
??//we expected .If the element in the list is erased ,the
??//iterator will be lost and point to a null.The shortage of
??//the stupid iterator will been seen the the Josephus.cpp
??//we have to use a template variable to storage the next iterator
??//of the deleting iterator.If not ,the programe will be nightmare
??iterator erase(){
???return iterator(*r,r->erase(it));
??}

?};

?void push_back(const Type& x){lst.push_back(x);}

?iterator begin(){return iterator(lst,lst.begin());}

?int size(){return lst.size();}

};
#endif

實(shí)現(xiàn)文件:
//:Using circle list to solve Josephus problem
//:version 1.01
//:author Murainwood 12/3/2006
#include<iostream>
#include"Ring.h"

void? main(){

?//enter the number of people and the index

?int n,m;
?cout<<"Enter the Number of Contestants?";
?cin>>n>>m;
???
?
??? Ring<int> ring;
?for(int i=1;i<=n;i++) ring.push_back(i);

?//determine the iterator
?//it is reasonable? to declare two iterator

??? Ring<int>::iterator tmp=ring.begin();
?Ring<int>::iterator it=tmp;
?
?//without the iterator tmp ,if we erase the it
?//the it will lost ,so the loop can not? work

?for(int index=0;index<n-1;index++){
???it=tmp;
??for(int j=0;j<m-1;j++){it++;tmp++;}
???tmp++;
????? cout<<"Delete person"<<*it<<endl;
???it.erase();
???
?}
?it=ring.begin();
?cout<<"The result is person"<<*it<<endl;
}

//:finished

???? 這個Ring List有很高的效率和安全性,并且通用性也比較好
???? 這里也發(fā)現(xiàn)個問題,就是STL里的Iterator 還不夠"聰明",這也是為什么我會在程序里多加個迭代器:tmp,
因?yàn)槿绻艺{(diào)用了it.erase();那么這個迭代器就丟失了,程序也就無非運(yùn)行下去.
???? 這樣我們很容易地想,如果調(diào)用了it.erase()后,指針不是丟失,而是指向下一個元素該多好啊!
???? 很遺憾,現(xiàn)階段標(biāo)準(zhǔn)STL庫里的List沒有這個功能.猜想是因?yàn)長ist的物理存儲結(jié)構(gòu)的緣故,如果讓他的迭代器變得如我們想像得那么"聰明",那么花費(fèi)可能會有些大.
??? 還沒有驗(yàn)證過boost庫,不知道那里的迭代器是否會更人性化些
???? 有時間研究一下相關(guān)的STL源碼,寫一個"聰明些"的迭代器.