HOME»基本情報技術者試験掲示板»平成30年春期午後問8

基本情報技術者試験掲示板

掲示板検索:

[2909]平成30年春期午後問8

CEさん(No.1)
https://www.fe-siken.com/kakomon/30_haru/pm08.html
30年春ヒープソートに関する問題のプログラム1のswap入れ替え部分の質問になります。
tmp←heap[i]でheapi番目の配列要素の値を入れるまではわかります。
ただ、次のheap[i]←heap[j]ときますがこのjの要素番号は何番になって、
heap[i]に対して入れる配列要素の値をどうして返されるのかが分かりません。
意味合いとしては、子の値が親より大きいから一度tmpにいれて、
親と子の値を入れ替えているのは分かりますがしっくりきません。
どなたかご教授願いませんでしょうか?
2021.02.21 14:06
ミカンボウさん(No.2)
アルゴリズムを最初から丁寧に読んでください。
解説にあるデータ例を参考にします。
データが今回は「30,60,15,5,10,20」とします。
副プログラムmakeheapをトレースすると、1回目の繰り返しはk=0なので何も起きません。
2回目の繰り返しで、k=1となり、配列の0番目と1番めが比較され、もう一つの繰り返しに入ります。そして、60>30なので、true分岐に入ります。
そこで、副プログラムswapが出てきます。
swapにここで与えられる引数は(型名は省略します)
「heap[],k,b]
です。
では、中身の数字を詳しく言うと、
「heapという配列の中の、k番目と(この場合は1)、その親(この場合は0)」
となります。
ここまで分かると、swapの中で何が行われているのかが分かるはずです。
swapに与えられた引数は、プログラムの中で
「heap[k],i,j]
となります。つまり、繋げればi=k,J=その親ということになります。
tmp←heap[i](tmpという一時的な変数に配列1番目の要素60を逃がす)
heap[i]←heap[j](配列1番目に30を代入)
heap[j]←tmp(配列0番目にtmpに逃した60を代入)
これでプログラム2つの処理は全て見たことになります。
もしまだわからなければ、質問してください。
2021.02.22 09:34

【返信投稿用フォーム】

お名前(10文字以内)

顔アイコン


本文(2,000文字以内)

本投稿を削除するためのパスワード(20文字以内)

プレビュー
※CBT方式においては出題内容の公開は禁止されているため、出題内容を尋ねたり、出題内容を特定できる類の投稿を禁止します。
※宣伝や迷惑行為を防止するため、当サイトとIPAサイト以外のURLを含む文章の投稿は禁止されています。

投稿記事削除用フォーム

投稿No. パスワード 
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop