该问题的解决方法有很多种，关于Josephus问题，前面已经给出了4种解法(http://blog.itpub.net/29876893/viewspace-1853008/)，是笔者对该问题产生浓厚的兴趣下而写出的，这些算法（可以说是很简单的吧，嘿嘿）是笔者走路或者吃饭的时候想出的（原创哦~_~）,也许其中功能不是太完善或不当之处，请大家谅解。今天突然想起解决该问题是不是可以用递归呢？立马打开VS,简单的修改了之前的解决方法四，通过画图分析这种方法是可行的。下面给出代码：

点击(此处)折叠或打开

#include<iostream> //递归解决该问题
#define MAX_SIZE 10
using namespace std;
int j, flag, q, sizeA;
int i;
char lastone;
void searchnote(char *, int);
void searchnote(char *A, int n) {
if (i == sizeA) {
i%=sizeA;
}
if(A[i] == NULL){
i++; //跳过数据域为NULL的元素，i需要自增1
searchnote(A, n); //该步中，本想用“臭名昭著"的goto语句，直接跳过下面的语句，但是笔者弃用了。
}
q++;
if (q == n) {
cout << A[i]<< " ";
flag++;
if (flag == sizeA) {
lastone = A[i];
}
A[i] = NULL;
q = 0;
}
if (flag == sizeA) { //递归退出的条件
cout << endl;
cout << "获胜的同学是：" << endl;
cout << lastone;
cout << endl;
exit(-1);
}
i++; //i需要自增1
searchnote(A, n);
}
int main() {
cout << "请输入同学的编号：" << endl;
char note[MAX_SIZE];
for (char ch; cin >>ch, j++) {
note[j] = ch;
cout << note[j] << " ";
sizeA++;
}
cout << endl;
cout << "出列同学的顺序依次是：" << endl;
searchnote(note, 4);
cout << endl;
}

运行结果：

上面的代码，读者仔细对比解决方法四会发现，只是把方法四中的for语句去了，然后再简单的修改，这种递归看起来比较的臃肿，这是笔者最先想到的解决方法，弃用for语句。希望读者有更好的递归算法。

ITPub博客

Josephus问题解决方法五（递归）

最新文章