Katsuoのサイト
このページでは過去問の苦手な部分や覚えておきたいことについて書いていく。
マージソートのプログラムについての問題が3回同じ問題をしたにもかかわらず全然分からずというレベルでわからないので、
苦手すぎる。そのため、理解を補完するためにこのノートを作成した。
苦手ということは、問題を解くために必要な何かしらの前提とする知識が不足していると考えられるので、そこをまずは抽出。
応用情報2021年版の問題集の73ページに掲載されている問題。
データ構造がリストである数値データをマージソートのプログラムで昇り順に並び変えるという問題。
リストは、個々の要素とポインタが１つのセットになっていて、ひとつひとつの要素が繋がったもの。 数値データはvalueと呼び、次の要素のアドレスを示すポインタをnextと呼ぶ。
マージソートを実現するための方法として、2つのプログラムを実行する。
リストを約半分になるように分割し、分割した2つのリストの先頭から順に2つずつ要素の大きさを比較し、小さい順に並べていく。
リストを分割する関数をdivideと呼ぶ。divideの引数にはlistというリストの先頭を指すポインタを渡す。
すると、divideは実行結果として、リストを2つに分割し、2つ目のリストの先頭のポインタを戻り値として返す。
問題文にも載っているように、リストを分割するために、変数a、bを用意し、それぞれポインタを格納し、変数aのポインタを1つ進めるごとに
変数bのポインタを2つずつ進める。変数bのポインタがリストの一番最後の要素に達するまで移動を繰り返すと、変数aのポインタは
リストのほぼ中央の要素を指すという性質を利用してリストを分割する。
ポインタを格納する変数2つ準備する。この変数をa、bとする。 最初の設問は、下記のdivide関数のア、イ、ウに入る字句を答える問題。
function divide(list)
a <- list
b <- a->next
if (bがnullと等しくない)
b <- b->next
endif
while( ア )
a <- a->next
b <- b->next
if(bがnullと等しくない)
イ
endif
endwhile
p <- a->next
ウ <- NULL
retuen p
endfunction
プログラムの流れ：
変数aにlistポインタを格納し、変数bに変数aよりも1つ後ろのポインタを格納。
この初期化によって、変数aにはリストの先頭を指すポインタが格納され、変数bにはリストの2番目の要素を指すポインタが格納される。
さらに、もしbがnullでないならば、リストの要素はまだ最後の要素ではないので、変数bに2番目+1の要素を指すポインタを格納する。
上記のように、bにリストの3番目の要素のポインタを格納するときに、bがnullでないかを確認することで、
リストの要素が全部で2個で少ない場合にもリストの分割に対応できるようにしている。
上記までが変数a、bの初期化の処理。
次はwhileの中身が穴埋めになっているブロック。
条件アの間に、whileブロックの中身を実行する。
ここで考えられるのが、whileのループを利用して、変数aと変数bのポインタをそれぞれ移動して、
変数bに格納しているポインタがリストの最後の要素になるまで繰り返すことである。
変数bに格納しているポインタがリストの最後の要素かどうかの判断は、変数bに格納したポインタがnullであるかどうかである。
もしポインタが指すアドレスがnullの場合は、そのポインタが指す要素が最後の要素となるので、アの解答は”bがnullと等しくない”となる。
変数aにaの次の要素を指すポインタを格納する。
変数bにbの次の要素を指すポインタを格納する。
条件アがtrueの間、上記の2つが実行される。
条件アがtrueで最初に実行されるとき、変数aはリストの最初の要素を指すポインタが格納されている。
そこから変数aのポインタの位置を1つ進める。
また、変数bは初期化のときにリストの2番目または3番目を指すポインタが格納されている。
そこから変数bのポインタの位置を1つ進める。
そしてもしbがnullではない場合は、要素の最後ではないので、イを実行する。
ここで考えられるのが、リストの分割のために変数aのポインタを１つ進めるごとに変数bのポインタを2つ進めるので、
イは変数bのポインタをもう1つ進めるという処理。そのため、イの解答は、”b <- b->next”となる。
上記までの処理で、変数bに格納したポインタが最後尾の要素を指している。
次に、変数pを新たに宣言し、pに、変数aに格納したポインタの次の要素を指すポインタを格納している。
変数bに格納したポインタが最後尾を指している時点では、変数aに格納したポインタは2つに分割したリストのうち、
1つ目のリストの最後尾を指している。ここで、関数divideについての冒頭の説明のように、関数divideの戻り値は
分割したリストの2つ目のリストの先頭を指すポインタを戻り値とすることになっているので、変数pを新たに宣言し、
pに、変数aに格納したポインタの次の要素を指すポインタを格納している。
次に、ウにnullを格納している。もともとのリストの最後尾はnullが入っていて分割後の2つ目のリストの最後尾も同じもの
なので特に何もする必要はないが、変数aに格納されているポインタは1つ目のリストの最後尾を指している。
ここで、変数aに格納しているポインタの次が2つ目のリストの先頭を指すポインタであり、このポインタをnullにすることで
1つ目のリストの最終要素となり、実質、リストの分割になる。このため、解答は、nullにするのは、”a->next”となる。
要素数が2N+1個の奇数個のとき、関数divideで分割した要素数は前半と後半でそれぞれいくつになるかを式で答える問題。
具体的にリストの要素数が3個や5個の奇数個の時に、関数divideを実行したらどうなるかを図に書いて試す。
例えば、要素数3個のときは、2N+1=3によりN=1となる。図に書いて試すと、リスト前半の要素数は2個、リスト後半の要素数は1個となる。
これを2N+1=3によりN=1となることに当てはめると、リスト前半の要素数はN+1個、リスト後半の要素数はN個に対応させることができる。
また、要素数5個のときも同様に関数divideの動作を図に書いて試すと、リスト前半の要素数が3個で、リスト後半の要素数が2個で、
2N+1=5からのN=2となることに当てはめると、リスト前半の要素数はN+1個、リスト後半の要素数はN個に対応させることができる。
よって、”リスト前半の要素数はN+1個、リスト後半の要素数はN個” が解答となる。
また、上記は、divide関数の中身を実行してポインタが移動する要素数によっても導くことができる。
関数divideを実行することで、変数aは要素の位置が1～N+1の間を位置するので、リストを分割してできる前半のリスト
の要素数は(N+1)-1+1=N+1個となる。また、変数bは後半のリストの最初の要素の位置は、リスト前半の要素の最後尾の位置+1個なので、
(N+1)+1=N+2となる。また、変数bが最後尾に位置する位置は、そのまま要素数の個数となるので、2N+1となる。
よって、リスト後半の要素数は、(2N+1)-(N+2)+1=2N+1-N-2+1=N個となる。
ここまでが、関数divideに関する問題となる。次は、分割したリストのマージについての問題となる。
関数divideで分割したリストを併合していく。関数mergeは、2つの連結リストの先頭へのポインタ変数aとbを引数とし、
併合後の連結リストの先頭へのポインタを戻り値とする。併合処理をする際には、ダミーのセルを用意し、この後ろに併合後の連結リストを
構成する。ダミーのセルへのポインタをheadとする。aとbが指すセルの値を比較しながら、値が小さい順に並ぶように処理を進める。
下記エ、オ、カに入る字句を答える問題。
function merge(a, b) //a,bは併合対象の連結リストの先頭へのポインタ
ダミーのセルを準備する
head <- ダミーのセルへのポインタ
p <- head
while(エ, かつ,bがnullと等しくない)
if(a->valueがb->value以下である)
p->next <- a
p <- a
a <- a->next
else
p->next <- b
p <- b
b <- b->next
endif
endwhile
if(オ) //要素が残っている連結リストを連結する
p->next <- b
else
p->next <- a
endif
return カ
endfunction
ダミーセルへのポインタheadを変数pに代入する。ここで、pは併合後のために作ったダミーセルの位置を表すポインタを格納するための変数。
whileループで併合していくことが読み取れるので、whileループの条件は、変数a、bが最後の要素までするので、ポインタがnullでない間実行される。
よって、エは、”aがnullと等しくない”が解答となる。
whileループの中身：
aとbのポインタが指す要素の大きさを比較し、要素を並べていく。変数pは最初、ダミーセルの先頭にある。
ダミーセルのaがb以下の場合はダミーセルの1つ右のセルのポインタaの値を格納する。
さらに変数pにaを代入することで、headポインタがポインタaを指すようになる。aのアドレスを指す。
セルは、セルの値と、次のセルへのポインタがセットなので、上記の処理が必要となる。
そして、ポインタ変数aにaの次のポインタを代入することで、ポインタaが2つ目の要素を指すようにする。
whileループでどちらかの要素が末尾になりポインタがnullであることが検出されると、
whileループを抜ける。そのため、ループを抜けた後は、aかbかどちらか一方の要素が残っている。
whileループの中で、要素の値によって、aだけがどんどん並べられて末尾にいったり、あるいはbだけがどんどん末尾にいったりする
ことがあり得る。これは、リストの構成に依存する。
whileループを抜けると、aまたはbどちらかの要素が残っているので、要素が残っている連結リストを連結する。
穴埋めの条件オは、ifの中でbを並べているので、”bがnullと等しくない”が解答となる。
上記により連結が完了すると、return文でカを返す。
冒頭で、関数mergeは”併合後の連結リストの先頭へのポインタを戻り値とする”と記載されているので、このポインタがカとなる。
ここで、連結リストの先頭はダミーで、それを指すポインタはheadポインタである。ダミーの次に要素が入っていて、
これが連結リストの先頭なので、これを指すポインタはheadのnextとなる。よって、カは”head->next”である。
32個の要素をdivide関数で1つずつに分割する。そこからmerge関数が16回呼ばれて、2個ずつの要素に連結される。
そこから、merge関数が8回呼ばれて、4個ずつの要素に連結される。そこからmerge関数が4回呼ばれて、8個ずつの要素に連結される。
そこから、merge関数が2回呼ばれて、16個ずつの要素に連結される。そこからmerge関数が1回呼ばれて、16個ｘ2個のリストが32個のリスト
に連結されて、連結が完了となる。そのため、16+8+4+2+1=31回merge関数が実行されることになる。