HOME»応用情報技術者試験掲示板» 平成26年秋期午後問3プログラミング  問1(3)
投稿する

[2925]  平成26年秋期午後問3プログラミング  問1(3)

 太郎さん(No.1) 
https://www.ap-siken.com/kakomon/26_aki/pm03.html

図5のプログラムの2〜6行目について
2 a←list
3 b←a->next
4 if(bがNULLと等しくない)
5  b←b->next
6 end if

この部分の動きについて、図3の6→4→3→8→7→2→1→5の例だと
2行目で「aポインタが6の要素を指す」
3行目で「bポインタが4の要素を指す」
5行目で「bポインタが3の要素を指す」
となり6行目終了時点で、「aポインタは6,bポインタは3の要素を指している」という解釈になると思うのですが、間違えているでしょうか?

そうなると7行目以降でaが1つ、bが2つずつ進むと、
while文1回目終了時点  aポインタは4,bポインタは7の要素を指している。
while文3回目終了時点  aポインタは3,bポインタは1の要素を指している。
while文4回目の途中で  aポインタは8,bポインタは5の要素(NULL)を指す。
となるのかと思いますが、

これを要素数が7個の場合に適応すると
マージソートの前半:N個、後半N+1となり解答と相違します。

どこの考え方が間違えているかご教授ください。
2021.09.28 21:26
関数従属さん(No.2) 
AP シルバーマイスター
>6行目終了時点で、「aポインタは6,bポインタは3の要素を指している」という
>解釈になると思うのですが、間違えているでしょうか?

上記で合っております。

>そうなると7行目以降でaが1つ、bが2つずつ進むと、
>while文1回目終了時点  aポインタは4,bポインタは7の要素を指している。
>while文3回目終了時点  aポインタは3,bポインタは1の要素を指している。
>while文4回目の途中で  aポインタは8,bポインタは5の要素(NULL)を指す。

aが1つ、bが2つずつ進む部分は合っております。以下となります。
while文1回目終了時点  aポインタは4,bポインタは7の要素を指している。
while文2回目終了時点  aポインタは3,bポインタは1の要素を指している。
while文3回目終了時点  aポインタは8,bポインタは5の次要素(NULL)を指す。

>これを要素数が7個の場合に適応すると
>マージソートの前半:N個、後半N+1となり解答と相違します。

要素数7個の以下の例の場合だと
6→4→3→8→7→2→1

6行目終了時点で、aポインタは6,bポインタは3の要素を指しており

7行目以降でaが1つ、bが2つずつ進み
while文1回目終了時点  aポインタは4,bポインタは7の要素を指している。
while文2回目終了時点  aポインタは3,bポインタは1の要素を指している。
while文3回目の途中で  aポインタは8,bポインタは1の次要素(NULL)を指す。
ようになります。

13行目が p←a->next となっているので、pポインタは7の要素を指します。
このpポインタがdivide関数の戻り値となり後半のリストの先頭になるので
6→4→3→8
7→2→1
となり、前半:N+1個、後半N個となります。
2021.09.29 01:23
 太郎さん(No.3) 
ありがとうございます、理解できました!
ポインタが最後の要素を指している状態と最後の要素のnextを指している状態を混同していたようです。
2021.09.29 08:25

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop