PR
【第7問】
 「線形探索」のアルゴリズムでは,「番兵」と呼ばれるテクニックがよく使われます。番兵の説明として正しいものはどれですか。
【選択肢】正解
A  配列の末尾に置いて目印とするデータ
B  配列の要素数を表すデータ  
C  配列を分割する位置を示すデータ  
D  配列に対する不正な処理を防止するデータ  

正解は選択肢Aです。

 目印となるデータのことを「番兵(sentinel)」と呼びます。線形探索では,配列の末尾に要素を1つ追加し,そこに見つけたいものと同じ数値を格納して番兵とします。番兵を追加したことで,処理時間を短くすることができます。

 番兵を使わない場合は,1つの要素に対して「見つけたい数値と同じか」「配列の末尾を越えていないか」という2つのチェックが必要ですが,番兵を使った場合は「見つけたい数値と同じか」だけで済むからです。番兵があるので,配列の途中に見つけたい数値がなくても,最終的に(配列の末尾で)必ず見つかることになるからです。




【第8問】
 「ユークリッドの互除法」は何を求めるためのアルゴリズムですか。
【選択肢】正解
A  最大公約数
B  最小公倍数  
C  最大値  
D  最小値  

正解は選択肢Aです。

 ユークリッドの互除法は「プログラムを作るには,勘に頼らない,いわば機械的に問題が解けるアルゴリズムを使わなければならない」ということを教えるために,アルゴリズムの入門書でよく紹介されている手法です。いくつかのバリエーションがありますが,一例として「大きいほうから小さいほうの数値を引くことを,両者が同じ値になるまで繰り返す。その値が最大公約数である」という手順があります。