![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
情報処理技術者試験見習い中です。
春の試験落としました。秋期は絶対に合格したいので、春の問題を復習中です。
午後の問8アルゴリズムで、擬似言語のソースがどうしてもわからない箇所があります。
行番号5 変数:vpos(64)、hpos(64)
の要素数が64も取られている理由がわかりません。
後半のループ処理を見る限り、vpos、hposの添え字に使われているmoreは多くても3つまでしか
増えません(処理待ちの画素数)。なので、せっかく64も領域が取られていても、実際に使われるのは
問題の範囲では、3が適当なのではと思いました。
もしくは、汎用性、拡張性を考えて、処理対象画素数の分だけ領域をとっているのでしょうか。
設問の本質から逸脱しておりますが、気になったので投稿させていただきました。
*基礎がまだ身についていません。プログラムや設問の解釈に誤りがあるかもしれません。
その際はご容赦ください。。
試験問題
http://app.cocolog-nifty.com/t/comments?__mode=r …
No.4ベストアンサー
- 回答日時:
>もしお気づきの点ありましたらご指摘願います。
「aに関する解答群」を1~5で止めずに最後まで描いていけばいいんじゃないでしょうか。
■■■242526■■
■■2223■■■■
■2021■■■■■
■42191817■■
■31■■1615■
■5■■■■14■
■67■■1213■
■■891011■■
上図の1では,上と左が同色なので,上の2をスタックに積んで,左の3へ進む。
上図の3では,上と下が同色なので,上の4をスタックに積んで,下の5へ進む。
後は上図の19まで,ずっと一方向に進むばかりですから,
スタックの1番目と2番目は「上図の2 と 上図の4」で変わらないまま,
スタックの3番目を入れたり(40行目)出したり(29行目)しながら,上図の19まで塗っていき,行き止まります。
そうしたら今度は,スタックの2番目の「上図の4」を取り出し,ずっと一方向に上図の20~26を塗っていきます。(ちなみに上図の26まで達した後,スタックの1番目の「上図の2」は上下左右すべて塗り終えられているので読み捨てられます)
補足のMORE2については,おっしゃっていることが分かりません。
「すべてを塗り終わった」状態とは,スタックの添字MoreがMAX値になったときではなく,スタックが空になった(Moreが0になった)状態ですから。
詳細な解説ありがとうございます。また、図解までしてくださり感謝です。ちゃんとトレースしたら、最後の画素に到着した時点では、moreの値が0か1になっていました。コツコツとトレースをする訓練の必要性を実感した次第です。
No.3
- 回答日時:
私も,スタックの最大長が64である必要はないだろうという印象を持っています。
とりあえず,私が途中で数え間違えていなければ,
全面 白,かつ,(1, 1)が開始点の場合は,スタックの深さは28まで,
全面 白,かつ,(2, 2)が開始点の場合は,スタックの深さは29まで,
全面 白,かつ,(4, 4)が開始点の場合は,スタックの深さは28まで,
伸びるようです。
全要素数の半分,8×8÷2=32くらいの最大長でいけそうな気がします。
あくまで上の3つ程度の例を試してみた結果ですが。
この回答への補足
もうひとつ個人的な疑問です。
すべてを塗り終わったあと(このときMOREの値はがMAX値だったとする仮に20回)、行番号26から34までのループが、MOREの値が0になるまで「処理なし」で繰り返されて終了するという意味にとれますが(計20回)、無駄のような気がします。
いっそMORE2という変数を定義し、行番号40の下に、
MORE2 ← MORE という文を追加
ループの「繰り返し条件」を追記(行番号26)
MORE2-MORE<5
つまり、MORE2がMOREよりも4多くなると、上下左右とも「塗り変え済み」という判断になるのでそれ以上進んでも意味がないので終了でよいのでは、、、という理屈です。
ご丁寧にありがとうございました。
この場合、将来の拡張性を考えて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 /さらに一つ前の開始位置にもどる*/
これは私の「処理の実行順序」か「要素番号のカウント」が誤っているのでしょうか。もしかしたら何回か読み返したり紙に書き出すと誤りが発見できるかもしれませんが、もしお気づきの点ありましたらご指摘願います。
※アルゴリズムは基礎-実践-基礎-実践の順番で学習中ですが、
道のりは長そうです。試験対策となると、ツボを見つけるスキルが求められます。
No.2
- 回答日時:
適当なデータ例として次を想定する。
8×8領域内は全面 白(CC=3)で塗られており,それを全面 黒(NC=1)で塗り替える。
領域内の開始点である,VSの初期値は4,HSの初期値も4とする。
最初に,25行目の副プログラム CheckAndStack(4, 4) を実行。
副プログラム CheckAndStack() 内の40行目で Moreが1つ増え,
41行目42行目で VPos[1] と HPos[1] を使用した。
(問題文より… (7)配列VPos,HPosの添字は,1から始まる。)
副プログラムから復帰して,26行目へと進む。
現時点のMoreの値は1なので,ループ内へ進入。
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)の上下左右4マスはすべて白なので,副プログラム CheckAndStack() 内ですべてスタック(VPosとHPos)に積まれる。
よって,この時点でのMoreの値は「4」。一次元配列VPos・HPosの中身は次のとおり。
VPos[1]~[4] の内容は,|3|4|5|4|
HPos[1]~[4] の内容は,|4|3|4|5|
30行目~33行目の実行を終え,34行目でループ開始行へと戻り,
More=4なので,26行目でループ内へ進入。
27行・28行目で V←VPos[4],H←HPos[5] と参照して(つまり右のマスを新たな開始点とする)
29行目でMoreを3にした。
これにより,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の値は+3されて「6」。一次元配列VPos・HPosの中身は次のとおり。
VPos[1]~[6] の内容は,|3|4|5|3|5|4|
HPos[1]~[6] の内容は,|4|3|4|5|5|6|
----------------------------------------
以上,26行目~34行目のループを2回終えただけの段階でも,
>vpos、hposの添え字に使われているmoreは
>多くても3つまでしか増えません(処理待ちの画素数)
という解釈が誤りであることを実例で示した。
ご丁寧な説明ありがとうございます。
moreはたしかに、問題文の例でなく、「全面白」と仮定したら
増えていきますね
一回のループごとに
塗りつぶし対象数-1が増分されます。
升目が16個あった場合を仮定すると、Moreが4つになったので誤りでした。
しかし、なぜ64も領域を取る必要があるのかがまだ理解できていません。いろんなパターンを想定してあえてそうしていると解釈してよいのでしょうか。それとも、塗り替え処理のmoreのMAXが64になるという意味でしょうか。
初心者の質問にお付き合いくださり感謝です。
No.1
- 回答日時:
基本情報、"難しい"問題、いつも平気で出しますね…。
■さて解説。
(なんとなくソースコード読んでるので、
まちがってたらごめんなさい。)
画像を
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 /さらに一つ前の開始位置にもどる*/
処理を終了、、あらっ?
トレースが誤っているでしょうか??
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 情報処理技術者・Microsoft認定資格 基本情報 午後問題落ちました 2 2022/10/26 22:54
- 情報処理技術者・Microsoft認定資格 基本情報技術者試験について知りたい! こんにちは! 今年基本情報技術者試験を受験するつもりです。 今 2 2023/07/17 21:23
- 情報処理技術者・Microsoft認定資格 基本情報技術者試験について 基本情報技術者試験の午後問題についてなのですが、 大門①の情報セキュリテ 1 2022/10/30 00:34
- 大学受験 お急ぎの質問です。 現在高3受験生です。次の金曜日に明治大学総合数理学部(現象数理科)の学部別試験が 3 2023/02/13 23:38
- 情報処理技術者・Microsoft認定資格 基本情報技術者試験の午前試験過去問について質問です。 今日受けたのですが科目Aだけ点数が足りませんで 2 2023/06/30 21:07
- IT・エンジニアリング IT業界ほぼ未経験で28歳からインフラエンジニアになれますでしょうか 7 2023/05/04 17:41
- Illustrator(イラストレーター) ワードに貼った画像のキャンバスと画像本体のサイズの調整 2 2022/05/19 18:31
- 大学・短大 (工学部)とある数学の講義(必修)を自主休講しようか悩んでいます 7 2022/11/19 21:21
- Java 問題作成のWebアプリの作り方を教えてください 1 2022/11/26 22:01
- 国家公務員・地方公務員 公務員試験の数的処理で苦戦しています。 1 2023/01/30 08:56
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
情報技術者試験の午後問題で落ちる
-
トレースで絵はうまくなります...
-
【2day】と【2days】の違いを教...
-
耐圧試験と気密試験
-
ACCESSで空白のデーターをクエ...
-
創価学会 任用試験
-
中3 期末テスト と 曾祖母...
-
生命保険 一般課程
-
空試験
-
基板のイニシャル費の処理方法
-
本試験と空試験
-
30歳未満とは30歳は含まれない...
-
テストピースとはどういったも...
-
3種下水道技術検定試験の勉強の...
-
なぜか過酸化物価が…
-
【専門的な公称耐圧試験電圧】6...
-
最悪のミスをしてしまいました。
-
税理士試験は難易度の高い試験...
-
シスコ認定試験CCNA の合否は何...
-
試験などで、リスクアセスメン...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
トレースの意味を教えてください
-
平成21年秋期 基本情報 問8 ...
-
あと数日で基本情報試験ですが...
-
流れ図がよくわかりません
-
主プログラム内で呼び出される...
-
平成18年 秋期 基本情報技術者 ...
-
情報技術者試験の午後問題で落ちる
-
CASL2の勉強方法について
-
トレースで絵はうまくなります...
-
応用情報技術者試験-午後筆記に...
-
流れ図がよくわかりません。
-
平成23年秋の午後アルゴリズ...
-
表計算の難易度が、毎年上がっ...
-
基本情報技術平成21年春午後問8...
-
基本情報者の午後問題擬似言語
-
トレサビリティー??
-
情報技術検定3級について質問...
-
基本情報技術者午後の勉強法
-
【2day】と【2days】の違いを教...
-
ACCESSで空白のデーターをクエ...
おすすめ情報