php関連アルゴリズムテーマ(回転)

19146 ワード
php
1、サルの群れがぐるぐる並んで、1、2、…、nの順に番号をつけます.そして1匹目から数えて、m匹目まで数えて、それを輪から蹴り出して、その後ろから数えて、m匹目まで数えて、それを蹴り出して...、このようにひっきりなしに進んで、最後にサルが1匹しか残っていないまで、そのサルは大王と呼ばれていました.このプロセスをプログラミングしてシミュレーションし、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、1匹の雌牛があって、4歳まで出産することができて、毎年1頭、生んだのはすべて同じ雌牛で、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、楊輝三角
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 "
";
    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"
";
    }
  }
}
$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]

 
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 $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]

 
7.PHP奇異アルゴリズム

PHP 7以下のバージョンは6を返し、PHP 7バージョンは5を返し、本当に奇異で、個人の下位アルゴリズムは悪く、PHP 7以下のバージョンのBUGだと思っています.
 
8.文字セット:文字列を入力し、その文字列に含まれる文字セットを求め、順番に並べ替えます(英語)
function set($str){
    //     
    $arr = str_split($str);
    //    
    $arr = array_flip(array_flip($arr));
    //  
    sort($arr);
    //     
    return implode('', $arr);
}

 
9.1つのファイルの下にあるすべてのファイルとサブフォルダの下にあるファイルを巡回する
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コードを書いてください.

 
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回操作します.操作ごとに2つの数字が与えられます.(p,l)は、現在の文字列の下にpと表記されている文字から始まる長さlのサブ列を表します.このサブストリングを左右に反転してこのサブストリングの元の位置の真後ろに挿入し、最後に得られた文字列を求めます.文字列の下付き文字列は0から始まり、サンプルからより多くの情報を得ることができます.
 
各テスト・インスタンスには、データのセットのみが含まれ、各データの最初の動作は元の文字列で、長さは10を超えず、大文字と小文字と数字のみが含まれます.次に、n個の操作を表す数字nがあり、n個の操作を表すn行があり、各行の2つの整数があり、各操作を表す(p,l).
 
入力の操作が合法的であることを保証し、最後に得られた文字列の長さは1000を超えない.
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;$irun([[0,2],[1,3]]);
echo $re;

 
17,あなたは1名のデビューする歌手としてついに自分の第1部のアルバムを出して、あなたはn首の歌を収录することを计画して、その上すべての歌の长さはすべてs秒で、すべての歌は完全に1枚のCDの中で収录しなければなりません.各CDの容量の長さはL秒で、少なくとも同じCD内の隣接する2つの歌の間に少なくとも1秒間隔があることを保証しなければなりません.魔除けのために、任意のCD内の歌数を13という数字で削除できないことにしました.では、このアルバムを出すには少なくとも何枚のCDが必要ですか?
 
各試験例は、1組のデータのみを含み、各データの第1の動作は、3つの正の整数n,s,Lである.n≦100,s≦L≦10000を保証する
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で双方向キューを実現
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 85,9945.
 $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ソートアルゴリズム(コードを書く)を書き出し、最適化する方法を説明します.
= $pivotkey){
                $high--;
            }
            $temp = $arr[$low];
            $arr[$low] = $arr[$high];
            $arr[$high] = $temp;
            while($low 

 
21シャッフルアルゴリズム

 
【プログラム1】テーマ:古典的な質問:ウサギのペアは、生まれてから3ヶ月目から毎月1対のウサギを産み、ウサギは4ヶ月目に成長してから毎月1対のウサギを産み、もしウサギが死ななければ、毎月のウサギの総数はいくらですか?   
1.プログラム分析:ウサギの法則は数列1,1,2,3,5,8,13,21...である.   
2は3番目の数が最初の2つの数字の和であり、古典的なフィボナカット数列である.
    function actionFblist($n)
    {
        // 1,1,2,3,5,8,13
    // $n   n  
        $arr = [1,1];
        if($n 

 
【手順2】題:101-200の間に何個の素数があるかを判断し、全ての素数を出力する.    1.プログラム分析:素数を判断する方法: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】題目:全ての「水仙の数」をプリントアウトし、「水仙の数」とは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+aaa+aaa+aaa...aの値で、aは数値です.例えば2+22+222+222+222+2222(このとき合計5個の数が加算される)で、数がキーボード制御に加算される.   
1.プログラム分析:各項目を計算する値を循環して取得することが重要です.
2.phpのstr_を使用可能repeat関数
  public function actionRepeatN()
    {
        $a = 8;
        $n = 8;
        $sum = 0;

        for ($i = 0;$i

 
【プログラム6】テーマ:1つの整数、それは100をプラスした後に1つの完全な平方数で、168をプラスしてまた1つの完全な平方数で、この数はいくらですか?   
1.プログラム分析:10万以内で判断し、まずその数に100を加えてから開方し、その数に268を加えてから開方する.具体的な分析を見てください.
 
最初は1つの数字が完全な平方数であるかどうかをどのように判断するか分からなかったが,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日を例にして、先に前の2ヶ月のをプラスして、それから5日をプラスして本年の何日目で、特殊な情況、うるう年しかも入力月が3より大きい時多く1日プラスすることを考慮しなければなりません.最初はこの問題を見て何か簡単な方法があると思っていたが、私は思わなかった.仕方がない.この方法しか使えない.
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】タイトル:3つの整数x,y,zを入力して、この3つの数を小さいから大きいまで出力してください.   
1.プログラム分析:最小の数をxの上に置く方法を考え、まずxとyを比較し、x>yならxとyの値を交換し、それからxとzで比較し、x>zならxとzの値を交換し、xを最小にすることができる.   
 
ここではソートを考察点としないで、ソートすると泡立ち、高速、挿入などのソートアルゴリズムを使うことができますが、ここでは3つの交換変数を使う方法が重要だと思います.
public function actionSortX()
{
    $x = 6;
    $y = 53;
    $z = 6;
    if($x>$y) // $y$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 "
";
    }
}

 
【プログラム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人が一緒に座って、5人目は何歳ですか?彼は4人目より2歳年上だと言った.4人目の年齢を聞くと、3人目より2歳年上だという.3人目に聞くと、2人目より2歳年上だという.2人目に聞くと、1人目より2歳年上だという.最後に最初の人に聞いて、彼は10歳だと言った.すみません、5人目はいくつですか?   
1.プログラム分析:再帰的な方法を利用して、再帰は再帰と再帰の2つの段階に分けられる.5人目の年齢を知るには、4人目の年齢を知って、順番に類推して、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は回文数であり,個位は万位と同じ,10位は千位と同じである.    
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);
}
SMProxy分析(SwooleベースのMySQLデータベース接続プール)
【資格試験】 スケジュールと記録等まとめ