很多书在一开始就开始学习josephus问题,为了让大家前面学起来较为容易我把前面涉及到此问题的地方都故意去掉了,现在我们已经学习过了结构体和类,所以放在这里学习可能更合适一些。
在正式开始学习之前我们先回顾一下如何利用数组和结构体的方式来解决,最后我们再看一下如何利用面向对象的抽象理念进行解决此问题的程序设计,相互对比,找出效率最高,最容易理解,最方便维护的程序来,说明利用面向对象的抽象理念进行程序设计的好处。
josephus问题其实就是一个游戏,一群小孩围成一个圈,设置一个数,这个数是个小于小孩总数大于0的一个整数,从第一个小孩开始报数,当其中一个小孩报到你设置的那个数的时候离开那个圈,这样一来反复报下去,直到只剩下最后一个小孩的时候那个小孩就是胜利者,写程序来找出这个小孩。
以下是数组方法:
由于数组的限制我们必须预先假设好有多少个小孩,离开的小孩他自身设置为0来标记离开状态。
代码如下: #include <iostream> using namespace std; void main() { const int num=10; int interval; int a[num]; for(int i=0; i<num; i++) { a[i]=i+1; } cout <<"please input the interval: "; cin >>interval; for(int i=0; i<num; i++) { cout <<a[i] <<","; } cout <<endl; int k=1; int p=-1; while(1) { for(int j=0;j<interval;) { p=(p+1)%num; if(a[p]!=0) { j++; } } if(k==num) { break; } cout<<a[p]<<","; a[p]=0; k++; } cout <<"\nNo." <<a[p] <<" boy've won.\n"; cin.get(); cin.get(); } 就数组解决来看,程序简短但效率不高可读性也不好,此代码没有什么特别之处主要依靠一个加1取模的方式来回到首位置,形成环链:p=(p+1)%num;。
|