平成24年秋期午後問8  どうか笑わずに聞いてくださ

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
落ち込み中さん  
(No.1)
https://www.fe-siken.com/kakomon/24_aki/pm08.html

笑わずに聞いてください。


私はこの問題の【設問】a,bを解くのに2時間ほどかかりました。
結果は正解でしたが、解法が解らずに、すべてトレースました。


Via=1  From=1  To=1  ←開始
Via=1  From=1  To=2
Via=1  From=1  To=3
Via=1  From=1  To=4
Via=1  From=1  To=5
Via=1  From=2  To=1
Via=1  From=2  To=2
Via=1  From=2  To=3
Via=1  From=2  To=4
Via=1  From=2  To=5
Via=1  From=3  To=1
Via=1  From=3  To=2
Via=1  From=3  To=3
Via=1  From=3  To=4
Via=1  From=3  To=5
Via=1  From=4  To=1
Via=1  From=4  To=2
Via=1  From=4  To=3
Via=1  From=4  To=4
Via=1  From=4  To=5
Via=1  From=5  To=1
Via=1  From=5  To=2
Via=1  From=5  To=3
Via=1  From=5  To=4
Via=1  From=5  To=5
Via=2  From=1  To=1
Via=2  From=1  To=2
Via=2  From=1  To=3
Via=2  From=1  To=4
Via=2  From=1  To=5
Via=2  From=2  To=1
Via=2  From=2  To=2
Via=2  From=2  To=3
Via=2  From=2  To=4
Via=2  From=2  To=5
Via=2  From=3  To=1  ←aを解く
Via=2  From=3  To=2
Via=2  From=3  To=3
Via=2  From=3  To=4
Via=2  From=3  To=5  ←bを解く


です。
途中、間違えたりで何度もやって、ある時点で法則性に気付いて…それで2時間です。
以降の設問は着手できていません。


アドバイス頂きたいのは、この問題は、そもそも論として「どうやって解くべきもの」
なのか…です。

うまく言えないのですが、一体「何に気付けば良かったのか」というか…。
あるいは、上記のようなトレースを高速で行うべきものなのか…。


この問題(とりあえず設問a,bだけについてで構いません)を解ける、解法が解る!という方のご意見を聞きたいのです。
どうぞよろしくお願い致します。

2021.02.12 18:24
チンプンさん 
(No.2)
問題文をよく読んでプログラムではなく図2の表と図1の動きを追えば5分も掛からないですね。
プログラムのイメージを掴ませるための導入問題だと思います。
2021.02.12 21:09
room710さん 
(No.3)
>>>うまく言えないのですが、一体「何に気付けば良かったのか」というか…。

→「そのプログラムが再現しようとしているのはどんな"動き"か?」
をいかに早くイメージできるかがアルゴリズムの解法力かと思います。
本問の場合には、
「隣り合っていない駅同士の距離を、他の駅を経由して計った場合に最も短い距離はどれか、
片っ端から調べていく」
といった"動き"を再現しようとしていることに気づければ良かったのではと思います。
  
私は下記のような思考回路で気づきました。
================================================

【1】まず「初期値」表と「Via=1」表を見比べてみると、
  Dist[2][4]が999から32に更新されている、なぜだろう?
  ↓

【2】駅②と駅④は隣り合っていないから「初期値」表では999とされていたが、
  ①を経由すると
  ・②→①=18
  ・①→④=14
  なので18+14=32に更新されたのではないか?
  ↓

【3】この仮説を「Via=2」表のaに当てはめてみると、
  駅①と駅③は隣り合っていないから「初期値」表では999とされていたが、
  ②を経由すると
  ・①→②=18
  ・②→③=17
  なので18+17=35に更新されたのではないか?    
  ↓

【4】実際にプログラムにあてはめてトレースしてみると、
  Via=2  From=1  To=1
  Via=2  From=1  To=2
  Via=2  From=1  To=3  ←確かにa=35になるのを確認
  ↓

【5】bについても【3】の考え方で計算(トレースはしない)

================================================

※ちなみに【2】については、
  英語「Via」の日本語訳が「~を通って」といった意味であるのを知っている人は
  より気づきやすかったのではと思います。

>>>あるいは、上記のようなトレースを高速で行うべきものなのか…。
→上記のような"動き"であることをイメージできていれば、
  【4】のようにトレースが必要な最小限の箇所を絞り込むことができたかと思います。


落ち込む必要など全くないですし、ましてや笑う人などいません。
こういったアルゴリズム力を養う唯一の方法は、
何時間かかっても自力でトレースし考えることだからです。
ぜひそのまま続けてみてください。

合格を心からお祈りしております。

2021.02.12 21:18
チンプンさん 
(No.4)
ちょっと言葉足りませんでした。
トレースの必要な箇所に気づけばいいんです。
via=1のトレース結果が与えられているのでそのデータを使って
via=2の時のトレースを
aなら
from=1
to =3
で行うだけです。
2021.02.12 21:23
落ち込み中さん  
(No.5)
チンプンさん(No.2)
room710さん(No.3)


スレ主です。
レスありがとうございます!
大変理解が深まりました。

先日トレースの重要性を痛感して、取り組んでおりましたが、
ヤミクモにやるだけではなくて、「プログラムの動きをイメージする」
という言わばイメトレも大切ですね・・・。

色々と気付きが多いです。
感謝いたします!!

引き続きがんばります・・・
2021.02.12 21:55
ぱるむさん 
(No.6)
viaは簡単にいえばtoにいくまでの経由地点です。
例えば2から4までは、(via=)1を経由したほうが早いのか、3を経由したほうが早いのか、5経由したほうが早いのかを調べています。経由地点が存在しなかったら、toまでの距離がそのまま入ります。

問題文やソースコードをよく読んで、そのプログラム何をしたいのかを頭の中で思い浮かべることができればいいんですが、これはトレースしまくって練習しないとなかなかできないんですよね。
自分はH29の最短経路の問題を一番最初に取り組んだんですが、本当に何時間もかかりました。なので最初はそれでいいと思います。同じ問題でもいいので何回もトレースするのがいいと思います。(自分は日を開けて何回もやっています)
2021.02.12 22:04
チンプンさん 
(No.7)
私もぱるむさんと同意見です。

がむしゃらにトレースをすることによってでしか養われない感覚が確実に存在していると思います。
いまだにアルゴの短期修得法が編み出されていないのもそう言うことなんだと思います。

落ち込み中さんのおっしゃる「ヤミクモ」は必要な過程だと思いますし、その「ヤミクモ」を実行できる人は、しばらく耐えれば攻略できる人です。
2021.02.13 01:45
落ち込み中さん  
(No.8)
ぱるむさん(No.6)
チンプンさん(No.7)

スレ主です。
ありがとうございます。

毎回のようにアルゴリズム問題に対しての不安というか、自身の至らなさを吐露してしまっており、申し訳なく思います・・・。

とにかくあれこれ考えずに、トレース、トレース、トレース・・・その先にある世界を見てみたい・・・。
午後試験まで1ヶ月、出来ることを出来るだけやってみます。
ダメでも再トライするのみです!

2021.02.14 11:19
チンプンさん 
(No.9)
おそらくプログラム未経験の人のほとんどはそうだと思いますよ。
私は20問ぐらい何周かやりましたけど、満点取れるようになった問題ですら、毎回読み始めるのが苦痛でしたよ。

アルゴはたぶん、やり続けさえすれば誰でもできるようになると思います。
ただ、この「やり続ける」という部分が最大の難所なんだと思います。
多くの人が、目先に光が見えてこない不安と、間違えては最初からやり直しになりがちなトレースのめんどくささに心が折れてしまう結果、難問扱いになっているのでしょう。
しかしやり続ければ「お?アルゴいけるんちゃう?」な瞬間が必ず訪れますので、それまで少し我慢して頑張ってください。

私の主観では、落ち込み中さんはホントにあと一歩で、ダムの決壊のようにドバーっと色んなことが見えるようになるところまで来ていると思いますよ。
2021.02.14 14:08

返信投稿用フォーム

スパム防止のためにスレッド作成から30日以上経過したスレッドへの書き込みは禁止しています。

その他のスレッド


Pagetop