PHP使用栈解决约瑟夫环问题算法示例
本文实例讲述了PHP使用栈解决约瑟夫环问题算法。分享给大家供大家参考，具体如下：
约瑟夫环问题：39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
size=$num;
$index=0;
while($index++<$this->size)
{
$this->stack[]=$index;
}
}
publicfunctionpop(){
$item=array_shift($this->stack);
$this->size=count($this->stack);
return$item;
}
publicfunctionpush($item)
{
$this->stack[]=$item;
$this->size=count($this->stack);
}
publicfunctionsize()
{
return$this->size;
}
publicfunctionstack()
{
return$this->stack;
}
}
interfaceJoseph
{
publicfunctionhandle($num=0,$step=0,$survivors=0);
}
classStackJosephimplementsJoseph
{
protected$stack;
protected$num;
protected$step;
publicfunction__construct(ArrayStack$stack)
{
$this->stack=$stack;
}
publicfunctionhandle($num=0,$step=0,$survivors=0)
{
//TODO:Implementhandle()method.
$this->stack->buildStack($num);
$i=0;
while($this->stack->size()>$survivors)
{
$pop=$this->stack->pop();
if(($i+1)%$step!==0)
{
$this->stack->push($pop);
$i++;
}
else
{
$i=0;
}
}
return$this->stack->stack();
}
}
functionjoseph($num,$step,$survivorsNum)
{
$arrayStack=newArrayStack();
$joseph=newStackJoseph($arrayStack);
return$joseph->handle($num,$step,$survivorsNum);
}
print_r(joseph(41,3,2));
执行结果：
Array ( [0]=>16 [1]=>31 )
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。