（PHP面试）数猴子（原型：约瑟夫环）

2019-11-06 08:23:10

字体：大中小

来源：转载

供稿：网友

约瑟夫环：递归算法假设下标从0开始，0，1，2 .. m-1共m个人，从1开始报数，报到k则此人出环自杀，问最后剩下的一个自杀的人编号是多少？

百度了好久好久，大家写的不是特别全面，导致我眼花缭乱，折腾了几天几夜，郁闷+++，终于把结果死和过程死的递归过程弄明白了。。。这里写图片描述

#include<iostream>using namespace std;int Joseph1(int n,int k){ if(n<=0||k<=0) { cout<<"error!"<<endl; return -1; }else { if(n==1) { return 0; }else { return ((Joseph1(n-1,k)+k)%n); } }}int Joseph2(int n,int k,int i){ if(n<=0||k<=0||n<i) { cout<<"error"<<endl; return -1; }else { if(i==1) { return (k-1)%n; }else { return ((Joseph2(n-1,k,i-1)+k)%n); } }}int main(){ int n,k;cin>>n>>k; cout<<"只看最后死"<<endl; for(int i=1;i<=n;i++){ cout << Joseph1(i,k) << endl; } cout<<"看过程死"<<endl; for(int j=1;j<=n;j++) { cout<<Joseph2(n,k,j)<<endl; } return 0;}

http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/ (只看结果死) http://www.cnblogs.com/yangyh/archive/2011/10/30/2229517.html (只看结果死) http://www.cnblogs.com/daimingming/p/3242406.html （只看代码，代码一和代码二分别对应结果死和过程死）

数猴子一群猴子排成一圈，按1，2，…，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号

// 只需要在输出结果死时，将编号加1，再输出。 cout<<"只看最后死"<<endl; cout << Joseph1(n,k)+1 << endl;

http://www.cnblogs.com/Flashcjy/p/4583802.html(看不懂。。。)

上一篇：php boolean类型转换

下一篇：PHP结合memcacheq消息队列解决并发问题