PHP经典算法（四）
2019-12-18 09:17:59 来源：admin 点击：705
17 你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？
每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。保证 n ≤ 100 , s ≤ L ≤ 10000
<?php
class TestKeenSting{
private $song_num;
private $song_size;
private $cd_size;
public function __construct($n,$s,$l)
{
if($n>100 || $s>$l)
exit('input error!');
$this->song_num = $n;
$this->song_size = $s;
$this->cd_size = $l;
}
public function run()
{
$cd_container = $this->calculate_single_cd();
return ceil($this->song_num/$cd_container);
}
private function calculate_single_cd()
{
//假设一张cd可以放n个 song_length+1
$n = floor($this->cd_size / ($this->song_size + 1));
//对剩余空间做判断
$gap = $this->cd_size - $n * ($this->song_size + 1);
if($gap == $this->song_size)//剩余空间是否刚好可以放一首歌
if($n!=12)//已经放了12首歌,不要这最后的一首
$n += 1;
else
if($n == 13) //如果之前就已经可以放13首,放弃一首
$n = 12;
return $n;
}
}
$a = new TestKeenSting(7,2,6);
$re = $a->run();
echo $re;
18 用PHP实现一个双向队列
<?php
class Deque{
private $queue=array();
public function addFirst($item){
return array_unshift($this->queue,$item);
}
public function addLast($item){
return array_push($this->queue,$item);
}
public function removeFirst(){
return array_shift($this->queue);
}
public function removeLast(){
return array_pop($this->queue);
}
}
?>
19 请使用冒泡排序法对以下一组数据进行排序10 2 36 14 10 25 23 85 99 45。
<?php
// 冒泡排序
function bubble_sort(&$arr){
for ($i=0,$len=count($arr); $i < $len; $i++) {
for ($j=1; $j < $len-$i; $j++) {
if ($arr[$j-1] > $arr[$j]) {
$temp = $arr[$j-1];
$arr[$j-1] = $arr[$j];
$arr[$j] = $temp;
}
}
}
}
// 测试
$arr = array(10,2,36,14,10,25,23,85,99,45);
bubble_sort($arr);
print_r($arr);
?>