很经典的"转圈数数踢人"问题,老早以前做的东西
这里是我的解法,利用STL里的List构建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
实现文件:
//: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有很高的效率和安全性,并且通用性也比较好
这里也发现个问题,就是STL里的Iterator 还不够"聪明",这也是为什么我会在程序里多加个迭代器:tmp,
因为如果我调用了it.erase();那么这个迭代器就丢失了,程序也就无非运行下去.
这样我们很容易地想,如果调用了it.erase()后,指针不是丢失,而是指向下一个元素该多好啊!
很遗憾,现阶段标准STL库里的List没有这个功能.猜想是因为List的物理存储结构的缘故,如果让他的迭代器变得如我们想像得那么"聪明",那么花费可能会有些大.
还没有验证过boost库,不知道那里的迭代器是否会更人性化些
有时间研究一下相关的STL源码,写一个"聪明些"的迭代器.
posted on 2006-04-18 00:10
murainwood 阅读(640)
评论(0) 编辑 收藏 所属分类:
C++&C