php实现约瑟夫的环点名问题

浏览数：21 / 时间：2015年06月09日

function rand_number($num)
    {
        return rand(0,$num);
    }
     
    function outnumber($n,&$arr,$max)
    {
        $number=rand_number($max);
        if($number>$n) $number=$number%$n+1;
         
        while(!empty($arr)){
         
            if(!isset($i)) {unset($arr[$number]);var_dump($arr);}//删除元素
             
            $i=$number;//需要索引才能找到下一个间距为新$number的元素
             
            $number=rand_number($max);//生成下一个随机数
            if($number>$n) $number=$number%$n+1;
             
            echo ‘下一个间距‘.$number.‘元素‘.‘<br>‘;
             
            $count=0;
            $n=end($arr);
            while($count<$number){
                 
                if($i>=$n) $i=1;//最后一个元素则返回到第一个元素
                else $i++;
                 
                if(!isset($arr[$i])) {continue;}
                    else {$count++;}//找到一个元素才++
            }
            unset($arr[$i]);
            var_dump($arr);
        }
    }
     
    $max=100;
    $n=6;
    for($i=1;$i<=$n;$i++) $arr[$i]=$i;
    outnumber($n,$arr,$max);
 
 
 
 
/** 
* 线性表应用（选首领问题） 
* 
* @param  $n  总数 
* @param  $m  当报数到 m 时，m出列 
* @return 最后剩下的数字 
*/ 
function yuesefu($n,$m) {   
    $r=0;   
    for($i=2; $i<=$n; $i++) { 
            $r=($r+$m)%$i;   
    } 
    return $r+1;   
}   
print_r(yuesefu(3,3));
 
 
 
/** 
*双向链表实现约瑟夫环 
* @author :于燚：qq：496510819 
*/ 
$num=5; 
$size=3; 
class p{ 
public $num;//号码 
public $next=null;//下一个对象 
public function __construct($num){ 
    $this->num=$num; 
} 
} 
//创建第一个对象 
$one=new p(1); 
$cur=$one; 
for($i=2;$i<=$num;$i++){ 
    $p=new p($i); 
    $cur->next=$p; 
    $cur=$p; 
} 
$cur->next=$one; 
//开始报数 
$i=0; 
while($cur->next!=null){ 
    if($i%$size==($size-1)){ 
        $cur->next=$cur->next->next; 
        if($cur->next==$cur) 
            break; 
    } 
    $cur=$cur->next; 
    $i++; 
} 
echo $cur->num;
 
以上内容来自http://www.oschina.net/code/snippet_932809_18605