HOME»基本情報技術者試験掲示板»h31年午後試験春のデータとアルゴリズムについて
投稿する

[4005] h31年午後試験春のデータとアルゴリズムについて

 こうこうさん(No.1) 
問三番なのですが、一度葉から根まで辿り、その後根から葉まで辿るのはなぜなのでしょうか。
最初から根から葉に辿れば良いのではないでしょうか。
また、kの値をk←parent[k]の式などが無くても、ひとつづつ辿ることはできるのでしょうか。
どなたか回答お願いします。
2022.03.01 03:13
nsさん(No.2) 
FE シルバーマイスター
>問三番なのですが、一度葉から根まで辿り、その後根から葉まで辿るのはなぜなのでしょうか。
>最初から根から葉に辿れば良いのではないでしょうか。
このプログラムは図2にあるように B => 010 の変換を目的としたものです。
根から辿ろうとすると、最初の分岐で左右どちらに辿ればいいか分かりません。
そのため、初めに葉から根に向かい、ルートを確定させたうえで、根から葉に向かい、ビット列を構築するという手順になっています。

>また、kの値をk←parent[k]の式などが無くても、ひとつづつ辿ることはできるのでしょうか。
プログラムの3行目で Encode(parent[k], parent, left) と再度Encodeを呼び出しています。(説明(3)にも「再帰的に」呼び出すと書かれています。)
再帰呼び出しのトレースは頭が混乱しやすいですが、頑張ってトレースしてみてください。
2022.03.01 08:53

返信投稿用フォーム

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

Pagetop