本文目录
约瑟夫问题,n个人从第k个人开始由1报数,数到m的人退出,用数组实现,以下是我根据老师讲课写的
开始的人k 蜀道m出列k-1+m-1是首个出列的人下一个人编号是k=(k+m-1)%ii是当前的剩余的位处列人数if((k+m-2)%i!=i-1) 这句是说如果下一个人编号k开始数到m的人不是最后一个人 就从这个人要删除的人后面的到末尾的人均前移一个位置 实现删除下一个人编号k开始数到m的人因为剩下的刚好i个人 下个编号为k的人的再数m后编号为k+m-1 下标为k+m-2如果是他的下标是最后一个人 而当前有i个人最大下标为i-1 所以判断k+m-2对i求余不是最后一个人 即i-1就吧k+m-2到i-1的人均前移1个位置 删除掉k+m-2否则的话 就不用移动了 已经是最后一个人了 因为i是在变的 i继续减少1所以前面的i-1个人继续参与淘汰 不受影响给你整理下:其实总的思路就是步骤1:从数组后往前逼近 如果数到m的编号是末尾 将人数i=i-1然后重复这个步骤1和步骤2否则步骤2:从删除处的人到末尾均前移1个位置 剩下的人数i=i-1然后重复以上步骤1和步骤2这个是顺序表的操作 如果用循环链表操作可能更直观一点
用C++数组实现约瑟夫环的问题
#include《iostream.h》int main(){ const int n=8; int m=4; int a; for(int j=0;j《n;j++) a=j+1; int k=1; int i=-1; while(1) { for(int j=0;j《m;) { i=(i+1)%n; if(a!=0) j++; } if(k==n) break; cout《《a《《","; a=0; k++; } cout《《a《《endl; return 0;}