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

質問

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

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

例えば、基本情報技術者試験平成１６年度春期午後のこの問題
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.3

tonton5656

>アルゴリズムは慣れだ慣れだと言われて、ひたすら問題を解くのですが、なにかしっくりきません
慣れはものすごく必要ですが
問題をひたすら解くだけのそんな知識役に立ちません。
実際にプログラミングをしてみないと無意味です。
それにその勉強方法でとった資格なんて資格の肩書きだけで
なんの役にも立ちません。
科学の授業も黒板で説明されるよりは実験して
試した先生に言われることでなくて
自分考えてでりいろいろ試行錯誤したほうが覚えやすいでしょ?

お礼

おっしゃるとおりで、私もそう思っています。
授業としても４月から一回もプログラム実習がなく、黒板ばっかりで、かなり無味乾燥です。

ただ、学校では、「来月１０月の国家試験で通らないと、来年の就職活動に間に合わない可能性がある。
取っているのと取っていないのとでは就職率が全く異なってくる」、と発破をかけられます。

私としては、基本情報の試験のための勉強よりもJAVAの方が好きだし資格SJCシリーズの方をどんどん取っていきたいのですが(組むことを楽しみながら)、
資格じゃないと言っておきながら結局資格(この場合は基本情報)を持っている人を企業としては採用しているという現実を学校側に突きつけられると、従わざるを得ません。
現実とは、あくまでうちの学校から就職した時の現実としてはという意味です。

大学を出ればいいってもんじゃないと言っておきながら、ほとんど一流大学しか採用しない一流企業と一緒です。

もう少しPCに触れ、色々と試しながら楽しみながら学んでいく事を私としても望んでいるのですが、
時間的に厳しいものがあるのでやむを得ない感じです・・・。

また、自分でプログラムをスイスイ組んでいけるレベルまで達していませんし、コンピュータの勉強も今年４月に始めたばかりですので・・・＾＾；

補足

すいません、就職率というより、就職の決まりやすさみたいな感じです。

回答No.2

pipipi523

No1でちょっと引っかかっていたのですがβのところは間違いで、
$output[$write_idx-1]>$output[$write_idx]が正解でした。
マージソートは名前しか知らなかったので・・勉強になりました A^-^;

あとは、sizeが2^2n(2,4,8,16・・)以外のときはうまく動かないのですが、
その辺りどう改造すればいいかなど考えるのが面白いと思います

お礼

わざわざプログラムまで組んでいただいてありがとうございます！！！
やっぱり実際に入力してみると良く分かるんですね。
私はJAVAを少しかじったぐらいしかプログラムをやったことがないのですが、なんとなく似通っていたので、perlも少し分かりました。

＞あとは、sizeが2^2n(2,4,8,16・・)以外のときはうまく動かないのですが、
その辺りどう改造すればいいかなど考えるのが面白いと思います

ほぉ～！こんな条件が裏に隠れていたとは思いもしませんでした。実際動かしてみると色々と出てくるのですね。

試験まであと一ヶ月もないぐらいなので、ちょっとプログラムを入力して理解・・・というのはきついので・・・、やはり問題の入力データの例を実際に当てはめて流れを追っていくしかないのですかね？

なんとなくやっていることはわかるのですが、
データの例を当てはめてトレースしていっても
それぞれの変数がどういう役割をしているのかというのが、どうもしっくりこないんです。

マージソートを知っている→試験に出る
であればいいのですが、問題は色々と組み合わさったものが出て試験場で考えなくてはならないので、
なにか解く手順のようなものがあればいいのですが。
どこを見るといい、とか。

pipipi523さんなら、
http://www.rs.kagu.tus.ac.jp/infoserv/j-siken/H16a2/pm04.html
の問題を出されたとしたらどう解いていかれますか？

回答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
と同等です
どっちでも正しく動くので間違いではないですが・・・ミスでしょう。