最新的新浪PHP面试题(2009.3)

function re($n,$m)
{
    $a = array(); 
    $b = array(); 
    for($i=0;$i<$n;$i++)
    {
        $a[$i]=$i+1;
    }
    $start=0;
    $k=0;
    for($i = $n;$i >= 2;$i--)      
            { 
                $start = ($start + $m - 1) % $i; 
                if ($start == 0) 
                    $start = i; 
                $b[$k] = $a[$start]; 
                $k++; 
                for ($j = $start + 1; $j <= $i; $j++) 
                    $a[$j - 1] = $a[$j]; 
            }  
        $b[$k]=$a[0]; 
    return $b[$k];
}
echo re(10,3); 

function re($n,$m)
{
    $a = array(); 
    $b = array(); 
    for($i=0;$i<$n;$i++)
    {
        $a[$i]=$i+1;
    }
    $start=0;
    $k=0;
    for($i = $n;$i >= 2;$i--)      
            { 
                $start = ($start + $m - 1) % $i; 
                $b[$k] = $a[$start]; 
                $k++; 
                for ($j = $start + 1; $j <= $i; $j++) 
                    $a[$j - 1] = $a[$j]; 
            }  
        $b[$k]=$a[0]; 
    return $b[$k];
}
echo re(10,3);

function kickMonkey($n,$m)
{
    /*monkeys array*/
    $monkeys = array();
    $before[1] = $n;
    for($i=1;$i<=$n;$i++)
    {
        $before[$i] = $i == 1 ? $n : $i-1;
        $next[$i]     = $i == $n ? 1 : $i+1;
    }
    $i = 1;
    $loop = 1;
    while($next[$next[$i]])
    {
        if($loop == $m)
        {    
            $x = $next[$before[$i]] = $next[$i];
            $before[$next[$i]] = $before[$i];
            unset($next[$i]);
            $loop = 1;
        }
        else 
        {
            $x = $next[$i];
            $loop++;
        }
        $i = $x;        
    }
    return $i;
}
echo "The king is monkey :".kickMonkey(10,4);

  /*
  13. 一群猴子排成一圈，按1，2，...，n依次编号。
  然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，
  再数到第m只，在把它踢出去...，如此不停的进行下去，
  直到最后只剩下一只猴子为止，那只猴子就叫做大王。
  要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
  */
  
  
  // 输入m,n. 本程序用6和4来举个例子
  $n = 6;
  $m = 4;
  
  $monkeys = array();
  
  for($i=1; $i<=$n; $i++){ //按1，2，...，n依次编号
      $monkeys[] = $i;
  }
  
  echo '<pre>';
  echo "start:";
  print_r($monkeys);  //输出初始状态
  
  $i = 0; //数组下标
  $z = 0; //数数的变量
  $c = $n; //用来记录还剩下的猴子个数
  while($c>1){ //只要剩下的猴子还多余一个，就继续循环
    
    if($i == $n){
      $i = 0;  //如果下标跑到头，就回0；用这个方法来模拟不停转圈。
    }
    if($monkeys[$i] != null){ //跳过之前已经踢出去的猴子
      $z++; // 往下数
    
      if($z == $m){ //如果数到了m
        $monkeys[$i] = null;  //数到第m只,把它踢出圈
    $c--; //猴子数量减1
    $z = 0;  //重新再数
    echo "temp:";
        print_r($monkeys); //这里去掉注释可以输出中间过程，看清踢出的顺序
      }  
    }
    
    $i++; //下标往下走
  }//while
  
  echo "final:";
  print_r($monkeys);//打印最后结果
  
  echo '</pre>';

function kickMonkey($n,$m)
{
        //构造前后指向的猴子环状链表
    for($i=1;$i<=$n;$i++)
    {
        $before[$i] = $i == 1 ? $n : $i-1;//当前猴子的前指向
        $next[$i]     = $i == $n ? 1 : $i+1;//当前猴子的后指向
    }
    $i = 1;
    $loop = 1;
        //如果还有下一只猴子
    while($next[$next[$i]])
    {
        if($loop == $m)
        {//踢除猴子    
            $x = $next[$before[$i]] = $next[$i];//把前一只猴子的后指向改为下一只猴子
            $before[$next[$i]] = $before[$i];//把后一只猴子的前指向改为前一只猴子
            unset($next[$i]);//踢掉数到的猴子,直接踢掉，那下一次循环不会读到这只猴子了,所以循环只会越来越快
            $loop = 1;//从下一只猴子开始数
        }
        else 
        {//继续数数
            $x = $next[$i];//当前猴子不踢除的话，就数到下一只猴子
            $loop++;
        }
        $i = $x;        
    }
    return $i;
}