分类目录归档:算法

算法题 – 洗牌

一副牌(54张,用1到54表示每张牌),要求随机打乱并且对应的位置的牌不能和原来的相同,举例:原来第6张牌是3,那么洗牌后的第6张不能是3。

洗牌这个东西肯定是跟随机相关的,但是这里的随机是有条件的。我试着使用随机取索引(数组下标)并保证这个索引和新牌索引不一样的办法来避免值比较来实现这个算法:

<?php
/*
 * 洗牌算法
 */

// 模拟一副随机打乱的牌
$list = range(1,54);
shuffle($list);

// 新牌
$newList = array();

// 可用下标
$canUseIndex = array_pad(array(),54,1);

for($i=0;$i<54;$i++){
	while(true){
		// 从可用下标中取一个随机下标
		$index = array_rand($canUseIndex);
		// 下标必须和原牌下标不同
		if($index !== $i){
			break;
		}
	}
	// 填写新牌
	$newList[] = $list[$index];
	// 删除已经使用过的下标
	unset($canUseIndex[$index]);
}

// 判断是否有重复
foreach($list as $id=>$vv){
	if($newList[$id] != $vv){
		
	}else{
		echo "Index -> $id - $vv \n";
	}
}

//结果输出
print_r($list);
print_r($newList);

永久链接:http://blog.ifeeline.com/1567.html

算法题 – 木板墙

考古学家在人迹罕至的一块平地上发现了由一堆木板拼成的墙。令人惊奇的是这些木板的宽度都相同!地下的部分都已腐烂,而地上的部分也有高有低,甚至有的地方根本没有木板,所以考古学家决定带走面积最大的长方形回去研究。

这个应该是原题描述,不过经过简单抽象就是有若干宽度一样而高度不一的木板排列在一起,木板不可移动,在这些木板中取一个长方形,使得其面积最大。

木板墙

最低木板决定了木板数,即固定了长与高。所以,我们可以把每块木板看成高度都不一样的,某一个高度的木板能结合多少木板就是固定的,所以我们可以按照这个规则循环一遍每块木板计算面积,然后取最大值。

/* 随机数组
$len = rand(10,50);

for($i=0;$i<$len;$i++){
	$num[] = rand(1,200);
}
*/

$num = array(7,3,5,8,7,3,10,11,8,6,8,13,6,9);

$len = count($num);

$result = array();
for($i=0;$i<$len;$i++){
	$height = $num[$i];
	$width = 1;
	
	for($x=($i-1);$x>=0;$x--){
		if($num[$x] >= $height){
			$width += 1;
		}else{
			break;
		}
	}
	for($y=($i+1);$y<$len;$y++){
		if($num[$y] >= $height){
			$width += 1;
		}else{
			break;
		}
	}	
	
	$result[] = $width * $height;
}

print_r($result);

输出:

Array
(
    [0] => 7
    [1] => 42
    [2] => 15
    [3] => 8
    [4] => 14
    [5] => 42
    [6] => 20
    [7] => 11
    [8] => 24
    [9] => 48
    [10] => 16
    [11] => 13
    [12] => 48
    [13] => 9
)