php单向链表解决约瑟夫环问题

作者: 白云飞 分类: php 发布时间: 2017-06-22 10:43 阅读:

一个经典的面试题:41一个人排成一个圈,从1开始数数,数到4,那个人就要离开队伍,然后下一个人从1开始再数,依次类推。这种算法叫做约瑟夫环问题。也可以叫丢手绢问题。由于php没有指针可以用,我们可以用类来模拟这个过程。好了,废话不多说,直接上代码:

<?php
// 节点类
class Node
{
	public $data = null;
	public $next = null;
	
	public function __construct($data)
	{
		$this->data = $data;
	}
}
// 创建节点
function createNode($node, $data)
{
	$curr = findLastNode($node);
	$newNode = new Node($data);
	$curr->next = $newNode;
}

// 计算节点的数量
function countNode($node, $head)
{
	$num = 1;
	$curr = $node;
	while(!is_null($curr->next)){
		if($curr->next == $head){
			break;
		}
		$num++;
		$curr = $curr->next;
	}

	return $num;
}

// 获取最后一个节点
function findLastNode($node)
{
	$curr = $node;
	while(!is_null($curr->next)){
		$curr = $curr->next;
	}
	
	return $curr;
}

// 删除节点 $no -- 指定删除的节点位置
function delNode(&$node, $no)
{
	$curr = $node;
	$num = 1;
	while(($num + 1) < $no ){
		$curr = $curr->next;
		$num++;
	}
	
	$curr->next = $curr->next->next;
	return $curr->next;
}

// 展示节点数据
function showNode($node, $head)
{
	$curr = $node;
	while(!is_null($curr->next)){
		echo $curr->data . "号<br/>";
		if($curr->next == $head){
			break;
		}
		$curr = $curr->next;
	}
}

// 头结点
$head = new Node(1);

// 41 个人
for($i = 2; $i < 42; $i++){
	
	createNode($head, $i);
}

// 排成一圈
$last = findLastNode($head);
$last->next = $head;

// 每数到4 退出一个
$count = countNode($head, $head);
while($count > 3){
	
	$head = delNode($head, 4);
	$count = countNode($head, $head);
}

echo "41个人从 1-41编号,每数到4退出一个人,最后剩下的是:<br/>";
showNode($head, $head);

 

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。