search
HomeWeb Front-endCSS TutorialHow to solve php Joseph problem

How to solve php Joseph problem

Mar 28, 2018 am 11:26 AM
phpsolve

"Joseph Ring" is a mathematical application problem: a group of monkeys line up in a circle and are numbered sequentially according to 1, 2,...,n. Then start counting from the 1st one, count to the mth one, kick it out of the circle, start counting from behind it, count to the mth one, kick it out..., and continue in this way until the end. Until there is only one monkey left, that monkey is called the king. Programming is required to simulate this process, input m, n, and output the number of the last king.

Listed below are three ways to solve this problem with PHP:

  1. Remove the recursion in logical order

  2. Algorithm

  3. Linear table application

Method 1, remove

logically
function getKingMokey($n, $m)  
{  
    $monkey[0] = 0;  
    //将1-n只猴子顺序编号 入数组中
    for($i= 1; $i<= $n; $i++)   
    {   
        $monkey[$i] = $i;  
    }  
    $len = count($monkey);  
    //循环遍历数组元素(猴子编号)
    for($i= 0; $i< $len; $i= $i)  
    {  
        $num = 0;  
        /* 
         * 遍历$monkey数组,计算数组中值不为0的元素个数(剩余猴子的个数) 
         * 赋值为$num,并获取值不为0的元素的元素值 
        */
        foreach($monkeyas$key => $value)   
        {   
           if($value == 0) continue;   
           $num++;   
           $values = $value;   
        }  
        //若只剩一只猴子 则输出该猴子编号(数组元素值) 并退出循环 
        if($num == 1)   
        {   
            return$values;  
            exit;   
        }  
        /*  
         * 若剩余猴子数大于1($num > 1)  
         * 继续程序  
        */
        //将第$i只猴子踢出队伍(相应数组位置元素值设为0) 
        $monkey[$i] = 0;  
        /* 
         * 获取下一只需要踢出队伍的猴子编号 
         * 在$m值范围内遍历猴子 并设置$m的计数器 
         * 依次取下一猴子编号 
         * 若元素值为0,则该位置的猴子已被踢出队伍 
         * 若不为0,继续获取下一猴子编号,且计数器加1 
         * 若取得的猴子编号大于数组个数 
         * 则从第0只猴子开始遍历(数组指针归零) 步骤同上 
         * 直到计数器到达$m值 * 最后获取的$i值即为下一只需要踢出队伍的猴子编号 
         */
        //设置计数器 
        for($j= 1; $j<= $m; $j++)   
        {   
            //猴子编号加一,遍历下一只猴子 
            $i++;  
            //若该猴子未被踢出队伍,获取下一只猴子编号 
            if($monkey[$i] > 0) continue;  
            //若元素值为0,则猴子已被踢出队伍,进而循环取下一只猴子编号 
            if($monkey[$i] == 0)   
            {   
                //取下一只猴子编号 
                for($k= $i; $k< $len; $k++)  
                {   
                    //值为0,编号加1 
                    if($monkey[$k] == 0) $i++;  
                    //否则,编号已取得,退出 
                    if($monkey[$k] > 0) break;  
                }   
             }  
            //若编号大于猴子个数,则从第0只猴子开始遍历(数组指针归零) 步骤同上 
            if($i == $len) $i = 0;  
            //同上步骤,获取下一只猴子编号
            if($monkey[$i] == 0)   
            {   
                for($k= $i; $k< $len; $k++)   
                {  
                    if($monkey[$k] == 0) $i++;  
                    if($monkey[$k] > 0) break;  
                }   
            }   
        }  
    }  
}  
//猴子个数 
$n = 10;  
//踢出队伍的编号间隔值 
$m = 3;  
//调用猴王获取函数
echo getKingMokey($n, $m)."是猴王";  
方法二,递归算法
[php] view
 plain copy
function killMonkey($monkeys , $m , $current = 0){  
    $number = count($monkeys);  
    $num = 1;  
    if(count($monkeys) == 1){  
        echo$monkeys[0]."成为猴王了";  
        return;  
    }  
    else{  
        while($num++ < $m){  
            $current++ ;  
            $current = $current%$number;  
        }  
        echo$monkeys[$current]."的猴子被踢掉了<br/>";  
        array_splice($monkeys , $current , 1);  
        killMonkey($monkeys , $m , $current);  
    }  
}  
$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10); //monkeys的编号
$m = 3; //数到第几只猴子被踢出
killMonkey($monkeys , $m);
    Method 3, linear table application
  1. function yuesefu($n,$m) {    
        $r=0;    
        for($i=2; $i<=$n; $i++) {  
            $r=($r+$m)%$i;    
        }  
        return$r+1;    
    }    
    echo yuesefu(10,3)."是猴王";

The above is the detailed content of How to solve php Joseph problem. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Moving Rainbow UnderlinesMoving Rainbow UnderlinesApr 13, 2025 am 11:27 AM

I absolutely love the design of the Sandwich site. Among many beautiful features are these headlines with rainbow underlines that move as you scroll. It's not

New Year, New Job? Let's Make a Grid-Powered Resume!New Year, New Job? Let's Make a Grid-Powered Resume!Apr 13, 2025 am 11:26 AM

Many popular resume designs are making the most of the available page space by laying sections out in a grid shape. Let’s use CSS Grid to create a layout that

One Way to Break Users Out of the Habit of Reloading Too MuchOne Way to Break Users Out of the Habit of Reloading Too MuchApr 13, 2025 am 11:25 AM

Page reloads are a thing. Sometimes we refresh a page when we think it’s unresponsive, or believe that new content is available. Sometimes we’re just mad at

Domain-Driven Design With ReactDomain-Driven Design With ReactApr 13, 2025 am 11:22 AM

There is very little guidance on how to organize front-end applications in the world of React. (Just move files around until it “feels right,” lol). The truth

Detecting Inactive UsersDetecting Inactive UsersApr 13, 2025 am 11:08 AM

Most of the time you don’t really care about whether a user is actively engaged or temporarily inactive on your application. Inactive, meaning, perhaps they

Wufoo   ZapierWufoo ZapierApr 13, 2025 am 11:02 AM

Wufoo has always been great with integrations. They have integrations with specific apps, like Campaign Monitor, Mailchimp, and Typekit, but they also

The JAMstack LandscapeThe JAMstack LandscapeApr 13, 2025 am 11:00 AM

It's no big secret that Netlify invented the term JAMstack. While it's possible to embrace the JAMstack without using Netlify, it's notable that Netlify is at

Why do we use .html instead of .htm?Why do we use .html instead of .htm?Apr 13, 2025 am 10:59 AM

Interesting question from Andy:

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: How To Unlock Everything In MyRise
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools