アルゴリズム+データ構造勉強会(10)~(15)

takekoshiです。いまさらですが春に行っていたA+D勉強会の資料のこりをUPしました。

最後は8クイーン問題を力技で解きますが、第15回最終ページにデータ構造を工夫して楽に解く方法が示されています。人に教わった方法ですが、かなり鮮やかな解き方になっています。

アルゴリズム+データ構造勉強会(2)の解答例とレビュー

第2回、バブルソートの解答例と修正です。
今回、広島県なみに「おしい」解答がありました。

    for ($i = 0; $i < count($array)-1; $i++) {
      for ($j = $i+1; $j < count($array); $j++) {
        if ($array[$i] > $array[$j]) {
          $cache     = $array[$i];
          $array[$i] = $array[$j];
          $array[$j] = $cache;
        }
      }
    }

ソートはされるのですが、「隣同士の比較」になっていないのです。動作確認ではなかなか検知不能ですが、不安定なソートになっています。「隣同士」を表現するために「$j」と「$j+1」を使ってみましょう。

    for ($i = 0; $i < count($array)-1; $i++) {
      for ($j = 0; $j < count($array)-1-$i; $j++) {
        if ($array[$j] > $array[$j+1]) {
          $cache       = $array[$j];
          $array[$j]   = $array[$j+1];
          $array[$j+1] = $cache;
        }
      }
    }

「$j+1」を使うために内側のループ初期値と条件を変更しています。

アルゴリズム+データ構造勉強会(1)の解答例とレビュー

今週の勉強会の解答例および、その修正です。

解答例

<?php
   $abc=array(46,2,5,39,38,6,24,1,283,3,7,8,-4,4,0,99,100,9,29,9);
   $arr_cnt = count($abc) - 1;
//   print("$arr_cnt\n");
   print("ソート前:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }
   sort($abc);
   print("ソート後:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }
?>

新人なので「コーディング規約はどうした」というのは置いておくとしまして。動作はするにしても、いくつか直したほうがよさそうです。

PHPの閉じタグは省略する

PHPの閉じタグ「?>」は省略したほうが不具合混入の可能性がなく、安全です。詳しくはググるなど

join()の利用

配列を出力するときに「スペース区切り、ただし末尾で改行」を実現しようと、頑張っています。

   $arr_cnt = count($abc) - 1;
//   print("$arr_cnt\n");
   print("ソート前:");
   for($i=0;$i<20;$i++){
      if($i == $arr_cnt){
         print("$abc[$i]\n");
      }else{
         print("$abc[$i] ");
      }
   }

これで悪いことはないのですが、せっかくPHPを使っているので関数を使って楽をしてみましょう。

   print("ソート前:");
  echo join(' ', $abc);
  echo "\n";

join()は「配列要素を文字列により連結する」関数です。「連結する」というと難しい感じがしますが、言い換えると「区切り文字を使ってくっつける」ということです。これで「スペース区切り」を実現します。
要素が1つの時はどうなる? という疑問がありそうですが、その場合はその要素1つが文字列として返ります。区切り文字は使われません。
区切り文字なので末尾には何もつきませんので、「行末で改行」は単に改行出力になります。

join()を使っての区切り文字実現はよくある定型句なので、覚えておくと便利です。

試行錯誤のコメントは消す

他の人にはむしろ読むときの邪魔になるので、試行錯誤の過程は消しておきましょう。

修正後

結果、こうなります。

<?php
   $abc=array(46,2,5,39,38,6,24,1,283,3,7,8,-4,4,0,99,100,9,29,9);

   print("ソート前:");
   echo join(' ', $abc);
   echo "\n";

   sort($abc); 

   print("ソート後:");
   echo join(' ', $abc);
   echo "\n";

だいぶすっきりしました。

アルゴリズム+データ構造勉強会(1)

社内勉強会として、初級者向けにアルゴリズム+データ構造の勉強会を始めました。全15回、毎週月曜開催なので大学の半期授業ぐらいの長丁場です。

せっかくなので資料を公開します。

PHPで書かれたアルゴリズム本って見つからないんですよね。需要ないんでしょうか。