1、一群猴子排成一圈，按1，2，…，n依次編号。然後從第1隻開始數，數到第m隻,把它踢出圈，從它後面再開始數，再數到第m隻，在把它踢出去…，如此不停的進行下去，直到最後隻剩下一隻猴子為止，那隻猴子就叫做大王。要求程式設計模拟此過程，輸入m、n, 輸出最後那個大王的編号。
function king($n, $m){
$monkeys = range(1, $n); //建立1到n數組
$i=0;
while (count($monkeys)>1) { //循環條件為猴子數量大于1
if(($i+1)%$m==0) { //$i為數組下标;$i+1為猴子标号
unset($monkeys[$i]); //餘數等于0表示正好第m個，删除，用unset删除保持下标關系
} else {
array_push($monkeys,$monkeys[$i]); //如果餘數不等于0，則把數組下标為$i的放最後，形成一個圓形結構
unset($monkeys[$i]);
}
$i++;//$i 循環+1，不斷把猴子删除，或 push到數組
}
return current($monkeys); //猴子數量等于1時輸出猴子标号，得出猴王
}
echo king(6,3);
2、有一母牛，到4歲可生育，每年一頭，所生均是一樣的母牛，到15歲絕育，不再能生，20歲死亡，問n年後有多少頭牛。
function niu($y){
static $num= 1; //定義靜态變量;初始化牛的數量為1
for ($i=1; $i <=$y ; $i++) {
if($i>=4 && $i<15){ //每年遞增來算，4歲開始+1，15歲不能生育
$num++;
niu($y-$i); //遞歸方法計算小牛$num，小牛生長年數為$y-$i
}else if($i==20){
$num--; //20歲死亡減一
}
return $num;
}
3、楊輝三角
<?php
/* 預設輸出十行，用T(值)的形式可改變輸出行數 */
class T{
private $num;
public function __construct($var=10) {
if ($var<3) die("值太小啦！");
$this->num=$var;
}
public function display(){
$n=$this->num;
$arr=array();
//$arr=array_fill(0,$n+1,array_fill(0,$n+1,0));
$arr[1]=array_fill(0,3,0);
$arr[1][1]=1;
echo str_pad(" ",$n*12," ");
printf("%3d",$arr[1][1]);
echo "<br/>";
for($i=2;$i<=$n;$i++){
$arr[$i]=array_fill(0,($i+2),0);
for($j=1;$j<=$i;$j++){
if($j==1)
echo str_pad(" ",($n+1-$i)*12," ");
printf("%3d",$arr[$i][$j]=$arr[$i-1][$j-1]+$arr[$i-1][$j]);
echo " ";
}
echo"<br/>";
}
}
}
$yh=new T('3'); //$yh=new T(數量);
$yh->display();
?>
4.冒泡排序
function maopao($arr){
$len = count($arr);
for($k=0;$k<=$len;$k++)
{
for($j=$len-1;$j>$k;$j--){
if($arr[$j]<$arr[$j-1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $temp;
}
}
}
return $arr;
}
5.快速排序
function quickSort($arr) {
//先判斷是否需要繼續進行
$length = count($arr);
if($length <= 1) {
return $arr;
}
//選擇第一個元素作為基準
$base_num = $arr[0];
//周遊除了标尺外的所有元素，按照大小關系放入兩個數組内
//初始化兩個數組
$left_array = array(); //小于基準的
$right_array = array(); //大于基準的
for($i=1; $i<$length; $i++) {
if($base_num > $arr[$i]) {
//放入左邊數組
$left_array[] = $arr[$i];
} else {
//放入右邊
$right_array[] = $arr[$i];
}
}
//再分别對左邊和右邊的數組進行相同的排序處理方式遞歸調用這個函數
$left_array = quickSort($left_array);
$right_array = quickSort($right_array);
//合并
return array_merge($left_array, array($base_num), $right_array);
}
6.二分查找算法（折半查找算法）
function binsearch($x,$a){
$c=count($a);
$lower=0;
$high=$c-1;
while($lower<=$high){
$middle=intval(($lower+$high)/2);
if($a[$middle]>$x){
$high=$middle-1;
} elseif($a[$middle]<$x){
$lower=$middle+1;
} else{
return $middle;
}
}
return false;
}
7.PHP奇異算法
<?php
function test(){
$a=1;
$b=&$a;
echo (++$a)+(++$a);
}
test();
PHP7以下的版本傳回的是 6，PHP7版本傳回5 ，還真的算奇異，個人底層算法差，認為是PHP7以下版本的BUG
8.字元集合：輸入一個字元串，求出該字元串包含的字元集合，并按順序排序（英文）
function set($str){
//轉化為數組
$arr = str_split($str);
//去除重複
$arr = array_flip(array_flip($arr));
//排序
sort($arr);
//傳回字元串
return implode('', $arr);
}
9.周遊一個檔案下的所有檔案和子檔案夾下的檔案
function AllFile($dir){
if($dh = opendir($dir)){
while (($file = readdir($dh)) !== false){
if($file !='..' && $file !='.'){
if(is_dir($dir.'/'.$file)){
AllFile($dir.'/'.$file); //如果判斷還是檔案，則遞歸
}else{
echo $file; //輸出檔案名
}
}
}
}
}
10.從一個标準的Url提取出檔案的擴充名
function getExt($url)
{
$arr = parse_url($url);
$file = basename($arr['path']);// basename函數傳回路徑中的檔案名部分
$ext = explode('.', $file);
return $ext[count($ext)-1];
}
11.有個人想上一個n級的台階，每次隻能邁1級或者邁2級台階，問：這個人有多少種方法可以把台階走完？例如：總共3級台階，可以先邁1級再邁2級，或者先邁2級再邁1級，或者邁3次1級總共3中方式
function jieti($num){ //實際上是斐波那契數列
return $num<2?1:jieti($num-1)+jieti($num-2);
}
12.請寫一段PHP代碼，確定多個程序同時寫入同一個檔案成功
<?php
$fp = fopen("lock.txt","w+");
if (flock($fp,LOCK_EX)) {
//獲得寫鎖，寫資料
fwrite($fp, "write something");
// 解除鎖定
flock($fp, LOCK_UN);
} else {
echo "file is locking...";
}
fclose($fp);
?>
13.無限級分類
function tree($arr,$pid=0,$level=0){
static $list = array();
foreach ($arr as $v) {
//如果是頂級分類，則将其存到$list中，并以此節點為根節點，周遊其子節點
if ($v['pid'] == $pid) {
$v['level'] = $level;
$list[] = $v;
tree($arr,$v['id'],$level+1);
}
}
return $list;
}
14.擷取上個月第一天 和 最後一天
//擷取上個月第一天
date('Y-m-01',strtotime('-1 month'));
//擷取上個月最後一天
date('Y-m-t',strtotime('-1 month'));
15.随機輸入一個數字能查詢到對應的資料區間
//把區間換成數組寫法，用二分法查找區間
function binsearch($x,$a){
$c=count($a);
$lower=0;
$high=$c-1;
while($lower<=$high){
$middle=intval(($lower+$high)/2);
if($a[$middle]>=$x){
$high=$middle-1;
}elseif($a[$middle]<=$x ){
$lower=$middle+1;
}
}
return '在區間'.$a[$high].'到'.$a[$lower];
}
$array = ['1','50','100','150','200','250','300'];
$a = '120';
echo binsearch($a,$array);
16，現在有一個字元串，你要對這個字元串進行 n 次操作，每次操作給出兩個數字：(p, l) 表示目前字元串中從下标為 p 的字元開始的長度為 l 的一個子串。你要将這個子串左右翻轉後插在這個子串原來位置的正後方，求最後得到的字元串是什麼。字元串的下标是從 0 開始的，你可以從樣例中得到更多資訊。
每組測試用例僅包含一組資料，每組資料第一行為原字元串，長度不超過 10 ，僅包含大小寫字元與數字。接下來會有一個數字 n 表示有 n 個操作，再接下來有 n 行，每行兩個整數，表示每次操作的(p , l)。
保證輸入的操作一定合法，最後得到的字元串長度不超過 1000。
<?php
class TestKeenSting{
private $str;
public function __construct($str)
{
$this->str = $str;
}
public function run($orders)
{
foreach($orders as $item)
{
$this->execute($item[0],$item[1]);
}
return $this->str;
}
private function execute($pos,$length)
{
$len = strlen($this->str);
if(($length-$pos) > $len)
exit(1);
else
$tmp_str = substr($this->str,$pos,$length);
$s1 = substr($this->str,0,$pos+$length);
$s2 = substr($this->str,$pos+$length);
$dest_str = $this->str_reverse($tmp_str);
$this->str = $s1.$dest_str.$s2;
}
private function str_reverse($str)
{
$len = strlen($str);
if($len%2 == 0)
$times = $len/2;
else
$times = ($len-1)/2;
for($i=0;$i<$times;$i++)
{
$t = $str[$len-1-$i];
$str[$len-1-$i] = $str[$i];
$str[$i] = $t;
}
return $str;
}
}
$a = new TestKeenSting('ab');
$re = $a->run([[0,2],[1,3]]);
echo $re;
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);
?>
20 寫出一種排序算法（要寫出代碼），并說出優化它的方法。
<?php
//快速排序
function partition(&$arr,$low,$high){
$pivotkey = $arr[$low];
while($low<$high){
while($low < $high && $arr[$high] >= $pivotkey){
$high--;
}
$temp = $arr[$low];
$arr[$low] = $arr[$high];
$arr[$high] = $temp;
while($low < $high && $arr[$low] <= $pivotkey){
$low++;
}
$temp=$arr[$low];
$arr[$low]=$arr[$high];
$arr[$high]=$temp;
}
return$low;
}
function quick_sort(&$arr,$low,$high){
if($low < $high){
$pivot = partition($arr,$low,$high);
quick_sort($arr,$low,$pivot-1);
quick_sort($arr,$pivot+1,$high);
}
}
?>
21 洗牌算法
<?php
$card_num = 54;//牌數
function wash_card($card_num){
$cards = $tmp = array();
for($i = 0;$i < $card_num;$i++){
$tmp[$i] = $i;
}
for($i = 0;$i < $card_num;$i++){
$index = rand(0,$card_num-$i-1);
$cards[$i] = $tmp[$index];
unset($tmp[$index]);
$tmp = array_values($tmp);
}
return $cards;
}
// 測試：
print_r(wash_card($card_num));
?>
【程式1】 題目：古典問題：有一對兔子，從出生後第3個月起每個月都生一對兔子，小兔子長到第四個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？
1.程式分析： 兔子的規律為數列1,1,2,3,5,8,13,21....
2 就是第三個數是前兩個數字的和,既是經典的菲波那切數列
function actionFblist($n)
{
// 1,1,2,3,5,8,13
// $n 為第n個月
$arr = [1,1];
if($n < 2)
return false;
for ($i=2;$i<=$n+1;$i++)
{
$arr[$i] = $arr[$i-1] + $arr[$i-2];
}
var_dump($arr);
echo $arr[$n+1];
}
【程式2】 題目：判斷101-200之間有多少個素數，并輸出所有素數。
1.程式分析：判斷素數的方法：用一個數分别去除2到sqrt(這個數)，如果能被整除，
則表明此數不是素數，反之是素數。
public function actionIsPrimeNumber()
{
$arr = [];
for ($i=101;$i<=200;$i++)
{
$flag = true;
for ($j = 2;$j<=sqrt($i);$j++)
{
if($i % $j == 0)
{
$flag = false;
}
}
if($flag == true)
$arr[] = $i;
}
var_dump($arr);
}
【程式3】 題目：列印出所有的 "水仙花數 "，所謂 "水仙花數 "是指一個三位數，其各位數字立方和等于該數本身。例如：153是一個 "水仙花數 "，因為153=1的三次方＋5的三次方＋3的三次方。
1.程式分析：利用for循環控制100-999個數，每個數分解出個位，十位，百位。
public function actionWaterFlower()
{
$re = [];
for($i = 100;$i<= 999;$i++)
{
$hundred = floor($i / 100 ); // 擷取百位數字
$ten = floor(($i %100 ) / 10 ); // 擷取十位數字
$one = floor($i % 100 % 10); // 擷取各位數字
if((pow($hundred,3) + pow($ten,3) + pow($one,3) ) == $i )
{
$re[] = $i;
}
}
var_dump($re);
}
【程式4】 題目：利用條件運算符的嵌套來完成此題：學習成績> =90分的同學用A表示，60-89分之間的用B表示，60分以下的用C表示。
1.程式分析：(a> b)?a:b這是條件運算符的基本例子。
public function actionGetScore()
{
$score = 90;
if($score <0 || $score > 100)
return false;
$re = $score >= 90 ? 'A' : ($score >= 60 ? 'B' :'C');
var_dump($re);
}
【程式5】 題目：求s=a+aa+aaa+aaaa+aa...a的值，其中a是一個數字。例如2+22+222+2222+22222(此時共有5個數相加)，幾個數相加有鍵盤控制。
1.程式分析：關鍵是循環獲得計算出每一項的值。
2. 可以使用php的str_repeat函數
public function actionRepeatN()
{
$a = 8;
$n = 8;
$sum = 0;
for ($i = 0;$i<$n;$i++)
{
$num = 0;
for ($j = 0;$j<=$i;$j++)
{
$num += $a* pow(10,$j);
}
$sum += $num;
}
var_dump($sum);
}
【程式6】題目：一個整數，它加上100後是一個完全平方數，加上168又是一個完全平方數，請問該數是多少？
1.程式分析：在10萬以内判斷，先将該數加上100後再開方，再将該數加上268後再開方，如果開方後的結果滿足如下條件，即是結果。請看具體分析：
剛開始不知道怎麼判斷一個數字是否為完全平方數,但是根據php的基本函數sqrt和pow可以間接進行判斷
若開方後進行取整再平方等于原數字,那麼這個數字則為一個完全平方數,根據這個方法進行判斷
public function actionWhitchNum()
{
for ($i=1;$i<=100000;$i++)
{
if(pow((int)sqrt($i+100),2) == ($i+100) &&pow((int)sqrt($i+168),2) == ($i+168) )
{
echo $i;
}
}
echo 'ok';
}
【程式7】 題目：輸入某年某月某日，判斷這一天是這一年的第幾天？
1.程式分析：以3月5日為例，應該先把前兩個月的加起來，然後再加上5天即本年的第幾天，特殊情況，閏年且輸入月份大于3時需考慮多加一天。 剛開始看這題以為有什麼簡單的方法,但是我沒有想到,沒有辦法,隻能用這種方法了
public function actionToday()
{
$today = '2018-03-05'; // 格式固定
$days = explode('-',$today);
$year = $days[0];
$month = (int)$days[1];
$day = (int)$days[2];
// 判斷是否為閏年
$flag = false;
if($year%400==0||($year%4==0&&$year%100!=0))
{
$flag = true;
}
// 對月份進行判斷 1,3,5,7,8,10,12 為31天
// 4,6,9,11 為30天
// 2月份閏年為29天,否則為28天
switch ($month)
{
case 1:
$sum = 0;break;
case 2:
$sum = 31;break;
case 3:
$sum = 59;break;
case 4:
$sum=90;break;
case 5:
$sum=120;break;
case 6:
$sum=151;break;
case 7:
$sum=181;break;
case 8:
$sum=212;break;
case 9:
$sum=243;break;
case 10:
$sum=273;break;
case 11:
$sum=304;break;
case 12:
$sum=334;break;
default:
break;
}
$sum = $sum + $day;
if($flag && $month>2)
$sum = $sum + 1;
var_dump($sum);
}
【程式8】 題目：輸入三個整數x,y,z，請把這三個數由小到大輸出。
1.程式分析：我們想辦法把最小的數放到x上，先将x與y進行比較，如果x> y則将x與y的值進行交換，然後再用x與z進行比較，如果x> z則将x與z的值進行交換，這樣能使x最小。
這裡不把排序當做考察點,排序的話可以使用冒泡,快速,插入等排序算法,這裡使用了三種交換變量的方式,我感覺這才是重要的
public function actionSortX()
{
$x = 6;
$y = 53;
$z = 6;
if($x>$y) // $y<$x
{
$x = $x+$y;
$y = $x-$y;
$x = $x-$y;
}
if($x>$z)
{
$tmp = $x;
$x = $z;
$z = $tmp;
}
if($y>$z)
{
$tmp = $y . '-' .$z;
$tmp = explode('-',$tmp);
$y = $tmp[1];
$z = $tmp[0];
}
echo $x,',',$y,',',$z;
}
【程式9】 題目：輸出9*9口訣。
1.程式分析：分行與列考慮，共9行9列，i控制行，j控制列。
public function actionMultiplicationTable()
{
for ($i=1;$i<=9;$i++)
{
for ($j=1;$j<=$i;$j++)
{
echo $j . '*' .$i .'=' . $i*$j;
echo ' ';
}
echo "<br>";
}
}
【程式10】 題目：有一分數序列：2/1，3/2，5/3，8/5，13/8，21/13...求出這個數列的前20項之和。
1.程式分析：請抓住分子與分母的變化規律。
public function actionAddFraction()
{
$sum = 0;
$numerator = [2,3];
$denominator = [1,2];
// 根據規律獲得所有的分子和分母
for ($i=2;$i<20;$i++)
{
$numerator[$i] = $numerator[$i-2] + $numerator[$i-1];
$denominator[$i] = $denominator[$i-2] + $denominator[$i-1];
}
// 獲得分數的前n項和
for ($i=0;$i<20;$i++)
{
$sum += $numerator[$i] / $denominator[$i];
}
var_dump($sum);
}
【程式11】 題目：求1+2!+3!+...+20!的和
1.程式分析：此程式隻是把累加變成了累乘。
public function actionAddFactorial()
{
$n = 20;
$sum = 0;
for ($i=1;$i<=$n;$i++)
{
$num = 1;
for ($j=1;$j<=$i;$j++)
{
$num = $j*$num;
}
$sum += $num;
}
var_dump($sum);
}
【程式12】 題目：利用遞歸方法求5!。
1.程式分析：遞歸公式：fn=fn_1*4!
public function numFactorial($n)
{
if($n>1)
return $sum = $n * $this->numFactorial($n-1); // 需要注意這點,若是寫成函數要替換成函數形式
else
return $n;
}
public function actionNumFactorial()
{
$n =4;
$sum = $this->numFactorial($n); // 調用上面的階乘方法(函數)
}
【程式13】 題目：有5個人坐在一起，問第五個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第三個人，又說比第2人大兩歲。問第2個人，說比第一個人大兩歲。最後問第一個人，他說是10歲。請問第五個人多大？
1.程式分析：利用遞歸的方法，遞歸分為回推和遞推兩個階段。要想知道第五個人歲數，需知道第四人的歲數，依次類推，推到第一人（10歲），再往回推。
public function myAge($n)
{
if($n == 1)
return $age = 10;
else
return 2 + $this->myAge($n-1);
}
public function actionMyAge1()
{
$n = 5;
echo $this->myAge($n);
}
【程式14】 題目：給一個不多于5位的正整數，要求：一、求它是幾位數，二、逆序列印出各位數字。
public function actionIntLength()
{
$num = 1232345;
$num = (string) $num;
$length = strlen($num);
$numstring = '';
for ($i=$length-1;$i>=0;$i--)
{
$numstring .= $num[$i];
}
echo $numstring;
}
【程式15】 題目：一個5位數，判斷它是不是回文數。即12321是回文數，個位與萬位相同，十位與千位相同。
public function actionIsPalindromeNumber()
{
$num = 12321;
$num = (string) $num;
if($num[0] == $num[4] && $num[1] == $num[3])
var_dump('Is Palindrome Number');
else
echo 'false';
}
/*
* 找到所有的5位的回文數
* */
public function actionAllPalindromeNumber()
{
$result = [];
for ($i=10000;$i<99999;$i++)
{
$i = (string) $i;
if($i[0] == $i[4] && $i[1] == $i[3])
$result[] = $i;
}
var_dump($result);
}