トランプその2

トランプを使って基本アルゴリズムを学びましょう。
探索プログラムの最も基本的なアルゴリズムである線形探索を実装します。

準備

HTMLとCSSを準備します。
トランプで作成したプログラムからForkするのが簡単です。

HTMLとCSSを準備します。
これまで作ってきたプログラムをForkしても良いですし、一から作成しても良いでしょう。
このページで作成するプログラムで共通で使用します。

HTML
<html>
   <body>
       <form name="form1">         
           <br>
            <INPUT TYPE="button" NAME="cmdCalc" value="開始" onclick="start()">           
       </form>
       
       <div id="disp">
        </div>
	<form name="form2">
       どのマーク?(0:♠,1:♣, 2:♥, 3:♦)<INPUT TYPE="text" NAME="txtA"><br>
       どの数字?(1~13)<INPUT TYPE="text" NAME="txtB"><br>
            <INPUT TYPE="button" NAME="cmdSrc" value="検索" onclick="search()">                    
             <INPUT TYPE="button" NAME="cmdSrc2" value="検索2" onclick="search2()">           
      </form>
       <div id="disp2">
        </div>
  </body>
</html>
いくつかボタンが用意されていて、onclickで
start()
search()
search2()
それぞれが起動できるようになっています。
divタグを書いて出力用の領域を置いてます。
dispという名前の領域とdisp2という名前の領域2つ作ります。


CSS
body { background-color: #DDDDDD; font: 30px sans-serif; }
前回と同じです。Forkしたなら変更不要です。


線形探索

線形探索とは、前から順番に総当たりで探す単純なアルゴリズムです。
ランダムに並んでいるものから探すにはこの方法しかありません。


検索ボタンを押した時に動作する search() 関数を作ります。
function search()
{
   この中にプログラムを書く
}

他のプログラムと同様に、テキストボックスから値を取り出します。今回は数値として扱うのでparceIntで整数値に変換しています。
var a=parseInt(document.form2.txtA.value);
var b=parseInt(document.form2.txtB.value);

この変数は、出力領域の一時保存場所として使います。最初は空文字列を入れておきます。
var tmpHtml="";

while命令は繰り返しの命令です。forでも書けますが、この形も良く使うので覚えておきましょう。
条件はカードのi番目の数字b(後ろのテキストボックスの値)と等しく無い間です。
意味付けすると、「カードがまだ見つかっていない間」を表しています。
var i=0;
while(cards[i].num!=b) {
  i++;
}

tmpHtml += を使って、変数の内容を追加しています。=だけを使うと内容を書き換えるので、前の行で設定した物が残らなくなります。ここでは見つかった時のiを表示して何番目に見つかったかを表示しています。配列の添字は0から始まっているので、先頭は0番目として表示します。さらに、その時のマークの値を表示しています。
最後にその結果をdisp2の領域に出力しています。

tmpHtml += "探しているカードは"+i+"番目に見つかりました<br>";
tmpHtml += "マークは"+cards[i].mark+"です";
document.getElementById("disp2").innerHTML = tmpHtml;

ここまでの完成板は以下のプログラムです。


このままでは一つ不具合があるはずです。
入力した値がトランプに無い値の場合は、検索できません。実際動作させてみると何も表示されませんが、存在しない配列の場所を探すので不具合で異常終了しています。

見つからない場合には、その情報を表示するように改良します。
基本的な考え方は以下の図です。
線形探索では最後のカードを探した後にさらに次のカードを探そうとします。
そこにはカードが無いため、探さずに終了します。
結局、カードが見つかった場合はその場所を示していますが、見つからなかった場合はカードが無い場所を示す事になります。
これを判定することで、見つからなかった事を知る事ができます。

実際のコードを書いてみます。
while(i<13*4 && cards[i].num!=b) {
  i++;
}

カードがまだ見つかっていない事まだカードがある事の2つを判定します。
どちらかでも満たさない場合は終了しなければいけません。繰り返す条件は両方満たしている場合ですから&&という記号を使います。どちらかだけ満たしたいという条件を書く場合は||を使います。

実は順番も重要です。
もうカードが無い場合はカードを見てはいけませんから、まだカードがある事の条件を先に書かなければなりません。


見つかった場合と見つからなかった場合で処理を分けます。
if(i<13*4) {
  tmpHtml += "探しているカードは"+i+"番目に見つかりました<br>";
  tmpHtml += "マークは"+cards[i].mark+"です";
} else {
  tmpHtml += "そんなカードはありません。";
}
i<13*4 は最終的なiの値がカードの範囲内かどうかを判定しています。13*4枚より少ないという判定ですから、これは見つかった場合を表しています。それ以外は見つからなかった場合ですから処理を分岐しています。



練習

  • 検索する様子を随時表示するようにプログラムを追加してみよう。
    • whileループ内でtmpHtmlに情報を追記してください。
  • 数値とマークが両方合うカードを検索するように追加してみよう。search2()関数を作って、検索2ボタンから動かしてください。
    • 条件が少し複雑です。数値とマーク両方一致している場合は終了しますが、繰り返し条件はその逆です。逆を表す記号は!です。!(条件式)のようにすると()の中の条件の逆で成り立つ式を記述することができます。


途中結果を表示する実行例
最終更新:2012年12月19日 10:43