本ブログの更新について
本ブログの更新は2016年3月31日をもって終了しました.ありがとうございました.
posted by みっちぃ (管理人)
2011年05月12日
よくこういうアルゴリズムを考えるなぁ〜
22年度秋期基本情報技術者試験の午後試験問8.設問に答えるということだけでいえばそれほど難しい問題じゃないけど,プログラムの各行がどんな意図で定義されて,どういう役割をするのかを説明するのが意外と難しかった.たぶんアルゴリズムの中で値がどのように変化するのかはわかっても,意味まで理解できた学生は少なかったと思う.
理解を難しくしている理由は2つあると思う.1つは,設問2のdの問題にもなっているが,Nのビット取出しと計算結果のシフトを一度にやっていること.一度にやるために,Rという1つの変数で済ませている点が理解を難しくしている.計算とNのビット取出しをそれぞれ違う変数でやるアルゴリズムだったら説明しやすかった.
もう1点は,加算(減算)時のビット位置が,被加算数を右シフトすることによって行っていること.例えば図1の5×3の場合は5×20+5×21という計算を行っているわけだが,加算数5×21(つまり10)を足す際に,00101を左にシフトして01010を作りこれを被加算数に加えるのではなく,被加算数を右にシフトして1ビットずれたところに00101を加算することで,01010を加算したのと同じ効果を得ている.このような仕組みになっている理由は,1点目のNのビット取出しと計算結果のシフトを一度にやるため.おそらく,メモリがほとんど用意できないような,コンピュータの黎明期に考えられたアルゴリズムなのだろう.
あなただったら,どのように学生に解説します?
理解を難しくしている理由は2つあると思う.1つは,設問2のdの問題にもなっているが,Nのビット取出しと計算結果のシフトを一度にやっていること.一度にやるために,Rという1つの変数で済ませている点が理解を難しくしている.計算とNのビット取出しをそれぞれ違う変数でやるアルゴリズムだったら説明しやすかった.
もう1点は,加算(減算)時のビット位置が,被加算数を右シフトすることによって行っていること.例えば図1の5×3の場合は5×20+5×21という計算を行っているわけだが,加算数5×21(つまり10)を足す際に,00101を左にシフトして01010を作りこれを被加算数に加えるのではなく,被加算数を右にシフトして1ビットずれたところに00101を加算することで,01010を加算したのと同じ効果を得ている.このような仕組みになっている理由は,1点目のNのビット取出しと計算結果のシフトを一度にやるため.おそらく,メモリがほとんど用意できないような,コンピュータの黎明期に考えられたアルゴリズムなのだろう.
あなただったら,どのように学生に解説します?