首页 > Web开发 > 详细

约瑟夫环问题(猴子选大王)PHP版

时间:2019-05-06 17:37:50      阅读:175      评论:0      收藏:0      [点我收藏+]

约瑟夫斯问题问题有时候也被描述成猴子选大王问题,题目如下。(最后会贴上约瑟夫问题的来历)

一群猴子排成一圈,按1,2,…,n依次编号。

然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。

要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。

用程序模拟该过程,代码如下:

<?php
function monkeyKing($n, $m)
{
    $arr = range(1, $n);       //构造一个数组
    $i = 1;                         //从第一个开始循环

    while (count($arr) > 1) {       //如果总数大于1
        if ($i % $m != 0) {
            $arr[] = $arr[$i - 1];  //不被踢出则压入数组尾部
        }
        unset($arr[$i - 1]);        //压入数组然后删除
        $i++;                       //继续循环
    }

    return $arr[$i - 1];            //直至最后剩下一个为大王
}



print_r(monkeyKing(5, 3));         //第4只为大王



$n = 5
 $m = 3
 $arr = [1, 2, 3, 4, 5]

 $i   $arr
 ---+------------------------
 1    x 2 3 4 5 1
 2    x x 3 4 5 1 2
>3    x x x 4 5 1 2
 4    x x x x 5 1 2 4
 5    x x x x x 1 2 4 5
>6    x x x x x x 2 4 5
 7    x x x x x x x 4 5 2
 8    x x x x x x x x 5 2 4
>9    x x x x x x x x x 2 4
 10   x x x x x x x x x x 4 2
 11   x x x x x x x x x x x 2 4
>12   x x x x x x x x x x x x 4

约瑟夫环问题(猴子选大王)PHP版

原文:https://www.cnblogs.com/datang6777/p/10820665.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!