欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

PHP丢手帕问题实例详解

程序员文章站 2022-03-26 16:21:28
...
问题描述:有n个人围成一圈,然后从任意指定的一个 人那里为起点,以m个人为单位,每转m个人第m个人被杀死。求最后不会被杀死的人。

遗留问题:

在此用php做简单的实现,php中对递归有100次的深度限制,所以在此不用递归,用循环;php中处理数组的函数比较多,所以采用顺序表(数组),顺序表删除元素比较复杂,所以效率比较低,只能处理10000一下的数据。链表中的遍历比较复杂,同样会导致效率低下,以后再做顺序表与链表的结合。

模拟实现:

  1. class Dhc  
    {  
        private function dropHandkerchief($start=0,$distance,$menArray)  
        {  
            $count = count($menArray);    
            $pos = $distance - 1;    
            $start = $start > ($count-1) ? 0 : $start;//开始位置大于总人数则默认从第一个开始    
            $pos = $start + $pos;//第一个要被出列的人的位置,pos为下标,所以要 -1;    
            while($count > 1)    
            {    
                if($pos < $count)//判断要出列的人的位置是否超出数组大小,超出则减去(或取模)数组大小,从头开始    
                {    
                    echo "第". $menArray[$pos] ."人出列<br />";    
                    array_splice($menArray,$pos,1);//删除要出列的人    
                    $count  = count($menArray);//重新计算大小    
                    $pos += $distance - 1;//下一个要出列的人的位置,pos 为要数的第一个人,所以第 n 个人的下标为 pos + n -1    
                }else    
                {    
                    //$pos -= $count;    
                    $pos = $pos % $count;    
                }  
            }    
            echo '<br />';    
            echo "第" .$menArray[0]. "人被留下";    
        }    
      
        public function drop()  
        {  
            $menArray = array();//    
            $total = 100;//总人数    
            $distance = 50;//间隔人数    
            $start = 3;//从第几个人开始    
            $i = 0;    
            while($i < $total)//初始化    
            {    
                $menArray[$i] = $i + 1;    
                $i++;    
            }    
            $this->dropHandkerchief($start, $distance, $menArray);    
        }  
    }

数学推导实现:(20170914)

简单改变一下问题的描述:有 n 个人,编号是 0 - n-1,从 0 开始数,数到 m 则 m 死,下一个人继续从 0 开始数,直到只剩最后一个人,求这个人最开始的编号。

每死一个人就重新开始,相当于减小了问题的规模,就是要解 n 个规模的解:n, n-1, n-2, n-3 …… 3, 2, 1。

假如在第二轮(n-1个人的规模)中死的那个人编号是 x(这个编号是第一个人死后,重新从 0 开始编排的),则可以推导出这个人在第一轮(人数为 n 时)中的编号是:(x + m)%n。

(n-2)中死的人在(n-1)中的编号是:(x + m)%(n-1)

(n-3)中死的人在(n-1)中的编号是:(x + m)%(n-2)

( 1 )中死的人在( 2 )中的编号是:(x + m)%2, 此时 x = 0;

把上面的过程倒过来,已知规模为 1 时,x = 0;

求规模为 2 时,x2 的值:(x + m) % 2 = x2

求规模为 3 时,x3 的值:(x2 + m) % 3 = x3

求规模为 n 时 x 的值。

  1. $n = 100;  
    $m = 3;  
    $s = 0;  
      
    $x = 0;  
    for ($i=2; $i<=$n; $i++) {  
        $x = ($x + $m) % $i;  
    }  
    echo ($x + $s) % $n;  
    // $s=0,表示从第 0 个开始数,如果不是从 0 开始,则只需要向后推 $s 个即可

以上就是PHP丢手帕问题实例详解的详细内容,更多请关注其它相关文章!

相关标签: php 详解 实例