アルゴリズムの勉強法は慣れしかないのでしょうか？

質問

学校の先生から、アルゴリズムは慣れだ慣れだと言われて、ひたすら問題を解くのですが、なにかしっくりきません。

時々、ここはなんでこういう事をしているのか分からないという所が出てきます。

例えば、基本情報技術者試験平成１６年度春期午後のこの問題
http://www.rs.kagu.tus.ac.jp/infoserv/j-siken/H16a2/pm04.html

において、擬似言語中の上から１３行目の

i: a_idx － span_idx , i < b_idx － a_idx , 1

では、教科書どおり？トレースしていくと

a_idx － span_idx

なんかは始めは０なんで、なぜ０としないでこんな事をやっているのかなあ・・・と頭を抱えてしまいます。

こうしている理由は、次々とループしていくとiの初期値は０でないときも出てくるからかな？とは想像できるのですが、
a_idx も　span_idxもそれに伴って変化していくので
、なんでこんな式を使うの？？？
と頭がごちゃごちゃになってしまいます。

何か法則的なことがある程度はあるような気がするのですが・・・。
ごく初歩的な例で行くと、iは何の変数かといった時にプログラム中にT（i）などとあると、配列の添え字なんだなと分かる、みたいな事です。

どのようにして考えていけばいいのでしょうか？
何か法則みたいなものをご存知の方も、教えていただけないでしょうか？

よろしくお願いします。

回答No.1

pipipi523

この問題で重要なのはマージソートの考え方とその実現方法です。たぶん。
まずソートの考え方を理解する必要がありますが、
図を見ても解りにくいので実際に値の変化を見ながら追っていくのが理解し易いでしょう
しかし人の作ったプログラムを解析しているだけでは理解し難いので、
実際に入力して動かして見るのが良いと思います(動かしたり改造してたりすると理解度が違います)

例えばPerlで入力・・
実際にやってみました
(確認に使ったツール)
http://www.forest.impress.co.jp/article/2001/09/03/perlwohajimeyou.html

@input=(47,33,68,55,74,89,25,10);#入力
$size=@input;
#問題
$span_size=2;
@output=@input;
while($span_size<=$size){
$span_idx=0;
$write_idx=0;
$ordered = 'true';#α
while($span_idx<$size){
$a_idx=$span_idx;
$b_idx=$span_idx + $span_size/2;
#for($i = $a_idx-$span_idx ; $i < $b_idx ; $i+=1){
for($i = 0 ; $i < $b_idx ; $i+=1){
$temp[$i]=$output[$i + $span_idx];
}
$a_yet='true';
$b_yet='true';
while($a_yet eq 'true' || $b_yet eq 'true'){
if($b_yet eq 'false' || ($a_yet eq 'true'
&& $b_yet eq 'true' &&
$temp[$a_idx - $span_idx] <= $output[$b_idx])){
$output[$write_idx] = $temp[$a_idx - $span_idx];
$a_idx = $a_idx + 1;
if($a_idx >= $span_idx + $span_size/2){
$a_yet = 'false';
}
}else{
$output[$write_idx] = $output[$b_idx];
$b_idx = $b_idx + 1;
if($b_idx >= $span_idx + $span_size){
$b_yet = 'false';
}
}
if($write_idx>0){#β
if($temp[$write_idx]>$output[$wtite_idx]){
$ordered='false';
}
}
$write_idx = $write_idx + 1;
}
$span_idx = $span_idx + $span_size;
}
#γ
if($ordered eq 'true'){
$span_size=$size;
}
$span_size = $span_size * 2;
}
#問題ここまで
print "END = ".join(',',@output)."\n";#結果確認

i: a_idx － span_idx , i < b_idx － a_idx , 1
は、直前で、
a_idx ← span_idx
と、なっているので0にしかならないですね
i: 0 , i < b_idx － a_idx , 1
と同等です
どっちでも正しく動くので間違いではないですが・・・ミスでしょう。