基本情報技術平成21年春午後問8のアルゴリズム問題での疑問です

質問

情報処理技術者試験見習い中です。
春の試験落としました。秋期は絶対に合格したいので、春の問題を復習中です。

午後の問8アルゴリズムで、擬似言語のソースがどうしてもわからない箇所があります。
行番号5　変数：vpos(64）、hpos(64)
の要素数が64も取られている理由がわかりません。

後半のループ処理を見る限り、vpos、hposの添え字に使われているmoreは多くても3つまでしか
増えません（処理待ちの画素数）。なので、せっかく64も領域が取られていても、実際に使われるのは
問題の範囲では、3が適当なのではと思いました。
もしくは、汎用性、拡張性を考えて、処理対象画素数の分だけ領域をとっているのでしょうか。

設問の本質から逸脱しておりますが、気になったので投稿させていただきました。
＊基礎がまだ身についていません。プログラムや設問の解釈に誤りがあるかもしれません。
　その際はご容赦ください。。

試験問題
http://app.cocolog-nifty.com/t/comments?__mode=red&user_id=58606&id=37468099

回答No.4

jjon-com · ベストアンサー

>もしお気づきの点ありましたらご指摘願います。

「ａに関する解答群」を１～５で止めずに最後まで描いていけばいいんじゃないでしょうか。

■■■242526■■
■■2223■■■■
■2021■■■■■
■４２191817■■
■３１■■1615■
■５■■■■14■
■６７■■1213■
■■８９1011■■

上図の１では，上と左が同色なので，上の２をスタックに積んで，左の３へ進む。
上図の３では，上と下が同色なので，上の４をスタックに積んで，下の５へ進む。

後は上図の19まで，ずっと一方向に進むばかりですから，
スタックの１番目と２番目は「上図の２ と 上図の４」で変わらないまま，
スタックの３番目を入れたり（40行目）出したり（29行目）しながら，上図の19まで塗っていき，行き止まります。

そうしたら今度は，スタックの２番目の「上図の４」を取り出し，ずっと一方向に上図の20～26を塗っていきます。（ちなみに上図の26まで達した後，スタックの１番目の「上図の２」は上下左右すべて塗り終えられているので読み捨てられます）

補足のMORE2については，おっしゃっていることが分かりません。
「すべてを塗り終わった」状態とは，スタックの添字MoreがMAX値になったときではなく，スタックが空になった（Moreが０になった）状態ですから。

お礼

詳細な解説ありがとうございます。また、図解までしてくださり感謝です。ちゃんとトレースしたら、最後の画素に到着した時点では、moreの値が0か1になっていました。コツコツとトレースをする訓練の必要性を実感した次第です。

回答No.3

jjon-com

私も，スタックの最大長が64である必要はないだろうという印象を持っています。

とりあえず，私が途中で数え間違えていなければ，
全面 白，かつ，(1, 1)が開始点の場合は，スタックの深さは28まで，
全面 白，かつ，(2, 2)が開始点の場合は，スタックの深さは29まで，
全面 白，かつ，(4, 4)が開始点の場合は，スタックの深さは28まで，
伸びるようです。

全要素数の半分，８×８÷２＝32くらいの最大長でいけそうな気がします。
あくまで上の３つ程度の例を試してみた結果ですが。

お礼

ご丁寧にありがとうございました。
この場合、将来の拡張性を考えて64個領域を確保した、と解釈してよさそうですね。（かなり自信ありませんが。。）

また、もうひとつ気になることがあります。
トレースの途中で、隣り合う同じ色の画素がなくなってしまうのです。
処理順：対象画素数：Moreの値：V,H、でトレース
1回目：3つ：2：5,2
2回目：1つ：2：6,2
3回目：2つ：3：7,2
4回目：1つ：3：7,3
..
17回目：なし：2：4,4　/*4方向とも塗りつぶしずみ*/
18回目：なし：1：4,5　/*ひとつ前のループの開始位置に戻る*/
19回目：なし：0：4,6　/さらに一つ前の開始位置にもどる*/
これは私の「処理の実行順序」か「要素番号のカウント」が誤っているのでしょうか。もしかしたら何回か読み返したり紙に書き出すと誤りが発見できるかもしれませんが、もしお気づきの点ありましたらご指摘願います。
※アルゴリズムは基礎-実践-基礎-実践の順番で学習中ですが、
　道のりは長そうです。試験対策となると、ツボを見つけるスキルが求められます。

補足

もうひとつ個人的な疑問です。
すべてを塗り終わったあと（このときMOREの値はがMAX値だったとする仮に20回）、行番号26から34までのループが、MOREの値が0になるまで「処理なし」で繰り返されて終了するという意味にとれますが（計20回）、無駄のような気がします。
　いっそMORE2という変数を定義し、行番号40の下に、
MORE2　←　MORE　という文を追加
　ループの「繰り返し条件」を追記（行番号26）
MORE2-MORE＜5
つまり、MORE2がMOREよりも4多くなると、上下左右とも「塗り変え済み」という判断になるのでそれ以上進んでも意味がないので終了でよいのでは、、、という理屈です。

回答No.2

jjon-com

適当なデータ例として次を想定する。
８×８領域内は全面 白(CC=3)で塗られており，それを全面 黒(NC=1)で塗り替える。
領域内の開始点である，VSの初期値は4，HSの初期値も4とする。

最初に，25行目の副プログラム CheckAndStack(4, 4) を実行。
副プログラム CheckAndStack() 内の40行目で Moreが１つ増え，
41行目42行目で VPos[1] と HPos[1] を使用した。
（問題文より… (7)配列VPos，HPosの添字は，１から始まる。）

副プログラムから復帰して，26行目へと進む。
現時点のMoreの値は１なので，ループ内へ進入。
27行・28行目で V←VPos[1]，H←HPos[1] と参照して，V＝4，H＝4。
29行目でMoreをゼロに戻した。

続いて30行目～33行目を実行。
　　30行目 CheckAndStack(3, 4) …上↑のマス
　　31行目 CheckAndStack(4, 3) …左←のマス
　　32行目 CheckAndStack(5, 4) …下↓のマス
　　33行目 CheckAndStack(4, 5) …右→のマス
座標(4, 4)の上下左右４マスはすべて白なので，副プログラム CheckAndStack() 内ですべてスタック（VPosとHPos）に積まれる。
よって，この時点でのMoreの値は「４」。一次元配列VPos・HPosの中身は次のとおり。
　　VPos[1]～[4] の内容は，|3|4|5|4|
　　HPos[1]～[4] の内容は，|4|3|4|5|

30行目～33行目の実行を終え，34行目でループ開始行へと戻り，
More＝４なので，26行目でループ内へ進入。
27行・28行目で V←VPos[4]，H←HPos[5] と参照して（つまり右のマスを新たな開始点とする）
29行目でMoreを３にした。
これにより，VPosとHPosは，配列の末尾でpush/popするスタックであることが分かる。

続いて30行目～33行目を実行。
　　30行目 CheckAndStack(3, 5) …→↑と進んだ新たなマス
　　31行目 CheckAndStack(4, 4) …→←と進んだ元のマス
　　32行目 CheckAndStack(5, 5) …→↓と進んだ新たなマス
　　33行目 CheckAndStack(4, 6) …→→と進んだ新たなマス
座標(4, 4)だけは元のマスなので黒に置き換え済だが，残りはすべて白なのですべてスタックに積まれる。
よって，Moreの値は＋３されて「６」。一次元配列VPos・HPosの中身は次のとおり。
　　VPos[1]～[6] の内容は，|3|4|5|3|5|4|
　　HPos[1]～[6] の内容は，|4|3|4|5|5|6|

----------------------------------------
以上，26行目～34行目のループを２回終えただけの段階でも，

>vpos、hposの添え字に使われているmoreは
>多くても3つまでしか増えません（処理待ちの画素数）

という解釈が誤りであることを実例で示した。

お礼

ご丁寧な説明ありがとうございます。
moreはたしかに、問題文の例でなく、「全面白」と仮定したら
増えていきますね
一回のループごとに
塗りつぶし対象数-1が増分されます。
升目が16個あった場合を仮定すると、Moreが4つになったので誤りでした。
しかし、なぜ64も領域を取る必要があるのかがまだ理解できていません。いろんなパターンを想定してあえてそうしていると解釈してよいのでしょうか。それとも、塗り替え処理のmoreのMAXが64になるという意味でしょうか。
初心者の質問にお付き合いくださり感謝です。

回答No.1

kacchann

基本情報、"難しい"問題、いつも平気で出しますね…。

■さて解説。
(なんとなくソースコード読んでるので、
まちがってたらごめんなさい。)

画像を
4×3の領域

□□□□
□□□□
□□□□

とし、
それぞれのマス目を

あいうえ
おかきく
けこさし

というふうに名づける。
で、この領域は、今、全部「黒」になっている。
これを、全部「白」に変えたい。

調査開始点は「か」とする。
---

(1)ループ突入前
まず、開始点たる「か」を、
ぬりかえ、「『処理待ち点』貯蔵庫」にぶちこむ(※行番号25)
[現在の処理待ち点貯蔵庫の中身:か]

(2)ループ1回目
処理待ち点貯蔵庫から、とりあえず「最後尾」をとりだし(※行番号27～29)、
これを「現在の調査基準点」とする。
[現在の調査基準点:か]
[現在の処理待ち点貯蔵庫の中身:なし]

この「基準点」の四方のマス4つ全てをしらべ(※行番号30～33)、
"領域内"であれば(※行番号38)
ぬりかえ(※行番号39)、
処理待ち点貯蔵庫にぶち込む。(※行番号40～42)
(注：「塗り替え済み」の点は領域外とみなす)

[現在の基準点:か]
[現在の処理待ち点貯蔵庫の中身:いおこき]

(3)ループ2回目
処理待ち点貯蔵庫から、とりあえず「最後尾」をとりだし、
これを「現在の基準点」とする。
[現在の基準点:き]
[現在の処理待ち点貯蔵庫の中身:いおこ]

この「基準点」の四方のマス4つ全てをしらべ、
"領域内"であれば
ぬりかえ、
処理待ち点貯蔵庫にぶち込む。
[現在の基準点:き]
[現在の処理待ち点貯蔵庫の中:いおこうさく]

…おおっと、「貯蔵庫」、どんどん増えていきそう？？

お礼

ありがとうございます。MOREの値が、問題文の例をあてはめると、
26-34のループのたびに29行目で無条件に1つ差し引かれる
29　More　←　More　-　1
　副プログラム：checkandstackが一回実行されるごとにMOREが1足される
40　More　←　More　+　1
　すると、Image[VS、HS]の上（V-1,H）、左（V,H-1）
　　　　　　　　　　　　 下（V+1,H）、右（V,H+1)
　が「塗りつぶしの対象」であればMoreが1ずつ増えることがわかる
処理順：対象画素数：Moreの値：V,H、でトレース
1回目：3つ：2：5,2
2回目：1つ：2：6,2
3回目：2つ：3：7,2
4回目：1つ：3：7,3
..
17回目：なし：2：4,4　/*4方向とも塗りつぶしずみ*/
18回目：なし：1：4,5　/*ひとつ前のループの開始位置に戻る*/
19回目：なし：0：4,6　/さらに一つ前の開始位置にもどる*/
処理を終了、、あらっ？
トレースが誤っているでしょうか？？