平成25年秋 問8 「文字列圧縮」

平成25年秋問8 「文字列圧縮」 [1107]

orchardさん(No.1)

いつもお世話になっております。
基本情報技術者試験平成25年度秋問8 必須アルゴリズム「文字列圧縮」問題についてです。

URL転載禁止なので具体的にだせませんが、トレース図込みで解説されたサイトを一つだけ見つけることができました。※サンプル文字列として、説明部の16文字列ではなくて、設問2の24文字列を使用していることだけご注意ください。
トレース図をフォローすることでやっと概略だけつかめたのですが、一つぶつかったのは

メインループ部となる
■Pindex＜Plength （仮にLoop2と呼称）
以下のループ周回スタート直後で

・Max～ ← -1
・Max～ ← -1
とあわせて

・Distance ← 4

とリセットされる箇所です。

問Cの答えであり、Loop2の下位Loop3の末尾で

・Distance ← Distance +1

とインクリメント（マイナス方向なのでデクリメント？）しており、あわせて、If分岐3つ目でPindex、Cindexも圧縮不可だった場合は+1インクリメントされているのに、
そこからLoop2の先頭にに戻った際に、リセットされて4からスタートすることが理解できません。

＞メインループの４回目
＞ここでようやく文字が一致します。
＞内側のループにはいり、ループしながら Distance を 1 づつ増やしていき Distance が 7 になったところで文字が一致します。

の間の2回目、3回目部分が、distanceが5，6となる解説をいただければ幸いです。

2018.02.10 01:35

通りすがりの者さん(No.2)

そのサイトを見ました。確かにDistanceが5、6のときの説明は省略されています。以下、簡単ですが。

【内側のループ1回目】
8文字目のAが4(＝8－4)文字目のDと一致しない
空欄cにより、Distance ← 5

【内側のループ2回目】
8文字目のAが3(＝8－5)文字目のCと一致しない
空欄cにより、Distance ← 6

【内側のループ3回目】
8文字目のAが2(＝8－6)文字目のBと一致しない
空欄cにより、Distance ← 7

【内側のループ4回目】
8文字目のAが1(＝8－7)文字目のAと一致する
・・・
12文字目のEが5文字目のEと一致する
次は一致しないので、MaxFitnum ← 5

メインループに戻り、Distance ← 4
(今度は、13文字目のAと9文字目のBを比較するため)

2018.02.10 10:01

orchardさん(No.3)

通りすがりの者様はじめまして、ご丁寧な回答ありがとうございます。

解説とブログ記事を照らしあわせて、やっと自分の錯誤に気付きました。
Distanceを固定ポインタ的に考えてしまい、どうしてもループ毎に4からスタートする揮発性カウン
タと理解できませんでした。
問題文内でも配列を P3←P2←P1 とデクリメントして走査している図示があるのですが、どうしてもイメージできず添字[0]の先頭からインクリメント走査するための Distance の+1拡張指定と勘違いしていたわけです。

今回のアルゴリズムは、
1．まずdistanceをまさに+1づつ「拡張」することで、デクリメントし、つまり『一度「離れる」』ことで、1stヒットの文字を走査し、
2．そこからFitnumでヒット文字数を+1づつ「拡張」インクリメントして、ヒット範囲を確値するという

『行って＆帰る』2段階の手順になんとか気づけました。
理解すると他のアルゴリズムと同様、うまくできているなと感心するばかりです。

改めてブログでトレースを図示していただいた方も含めて、丁寧な解説ありがとうございました。

2018.02.10 19:18

スレッドの先頭へ»

その他のスレッド

»[1106] 午後の部戦略投稿数:7
»[1105] 基本情報の平成21年春期午後問8の設問ｆがわか投稿数:5
»[1104] 平成23年秋期午前問61 投稿数:4

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。