[算法题]约瑟夫(josephus)环的php玩法

[整理自喜悦国际村] 没有认真去看,只是觉得有意思,先收集整理一下,有空再消化一下..

原文地址:

 

约瑟夫(josephus)环是这样的：假设有n个小孩坐成一个环，假如从第一个小孩开始数，如果数到m个小孩，则该小该离开，问最后留下的小孩是第几个小孩？例如：总共有6个小孩，围成一圈，从第一个小孩开始，每次数2个小孩，则游戏情况如下：
小孩序号：1，2，3，4，5，6
离开小孩序号：2，4，6，3，1
最后获胜小孩序号：5

 

1）

 

// 数组长度
$n = 6;

// 数到这个数的时候，小孩离开
$m = 2;

// 定义数组
$a = array();

// 建立数组
for ($i=0; $i<$n; $i++)
{
    $a[$i]=$i+1;
}

// 循环前，从第一个小孩开始
$i=0;

// 开始循环
while(true)
{
    // 开始数小孩
    for ($s=1;$s<=$m;$s++)
    {
        // 当没有数到 $m 的时候，将数组的长度加一，加上的值为当前数到是第几个的小孩
        if ($s<$m)
        {
            $a[$n] = $a[$i];
            $n++;
            //print_r($a);exit;
        }

        // 如果数到的小孩为最后一个小孩的，输出
        if ($i>=$n-1)
        {
            echo $a[$i];
            break 2;
        }

        // 移动数组下标
        $i++;
    }
}
?>

2）

define (TOTAL_N, '6');
define (COUNT_M, '2');

$arr = array ();
$key = 1;
$max_key = COUNT_M - 1;
$curr_ct = 0;

// Init
for ($i = 1; $i <= TOTAL_N; $i++) {
    $arr[$i] = array ('prev' => $i - 1, 'next' => $i + 1);
}

$arr[TOTAL_N]['next'] = 1;
$arr[1]['prev'] = TOTAL_N;
$key = 1;
$ct = 1;

while (true) {
    echo ('Current Key:' . $key . ' Next Key:' . $arr[$key]['next']);
    if ($ct == COUNT_M) {
        echo (' ...Current node deleted!');
        $ct = 0;
        $arr[$arr[$key]['prev']]['next'] = $arr[$key]['next'];
        $arr[$arr[$key]['next']]['prev'] = $arr[$key]['prev'];
    }
    
    $key = $arr[$key]['next'];
    $ct++;
    echo ('
');
    
    if ($key == $arr[$key]['next']) {
        $last = $key;
        break;
    }
}

echo ('The last key is ' . $last);

?>

3）

$num=6; //总人数
    $step=2;//步长
    //初始化数组
    $array[0]=-1;
    for($i=1;$i<=$num;$i++)
        {
            $array[$i]=0;    
        }
        
    $s=0;
    $i=1;
    $con=$num;
    while($con<>1)
        {
                if($array[$i]==0) //当为0时表明该人没有出局
                    {
                        $s++;
                        if($s==$step)  //数的$step个人，让他出局
                            {
                                $array[$i]=$con;
                                $con--;
                                $s=0;
                                $exitChar.="$i-";
                                
                            }
                            
                    }
                
            if($i==$num)
                {
                    $i=1;    
                }
                else
                    {
                        $i++;
                    }
        
            
        }
echo "离开小孩序号：$exitChar n";
echo "留下小孩 ：".array_search('0', $array);
?>

4）

list($lastone, $queue) = josephus(6,2) ;
echo 'Last one is:', $lastone, 'Queue:', $queue ;
function josephus($n, $m)
{
    $arr = array() ;
    $queue = '' ;
    for ($i = 1; $i <= $n; $i++)
        $arr[] = $i ;
    $key = -1 ;
    $count = count($arr) ;
    while ($count > 1)
    {
        for ($i = 0; $i < $m; $i++)
        {
            $key ++ ;
            if ($key == $count)
                $key = 0 ;
        }
        $queue .= $arr[$key] ;
        unset($arr[$key]) ;
        --$key == --$count && $key = -1 ;
        sort($arr) ;
    }
    return array($arr[0], $queue) ;
}
?>

5）

$n=10000000;$m=9999;$k=1;
for($i=2;$i<=$n;$i++)
    $k=($k+$m%$i-1)%$i+1;
echo $k;
?>

6）

$n=20;$m=7;$k=1;
for($i=2;$i<=$n;$i++){
    $k=($k+$m)%$i;
    $k = $k ? $k : $i;
}
echo $k;
?>

7）

$ar = array(1,2,3,4,5,6);
$m = 2;
$i = 0;
while(count($ar) > 1) {
  $i++;
  $x = array_shift($ar);
  if($i < $m) array_push($ar, $x);
  else {
    echo "$x ";
    $i = 0;
  }
}
echo '
剩下:'.array_pop($ar);
?>