夏休みの課題として出ました。だれか助けてください・・・
(２)が全く分かりません。理由も含めお願いします。
![]() |
No.38292 - 2016/07/29(Fri) 15:51:44
| ☆ Re: 経路の最大得点の問題です。 / angel | | | 答えは多分、
上右上右下下右上上上
と辿った時の 22 になると思うのですが、とても「理由」は分かりません。
この答えは、スタートからゴールまでの考えられる184通りを全て試した結果なのですが、全部虱潰しに試す以外の方法はなかなか難しい気がします。
|
No.38296 - 2016/07/29(Fri) 19:32:50 |
| ☆ Re: 経路の最大得点の問題です。 / 中１ | | | 184通りも全て試してもらい、ありがとうございます！
感謝しかありません！
やはり最大の数字は２２なのですね。それが分かっただけでも安心しました。
しかし・・・理由は分からないですよね・・・
難しい！誰か理由が分かる方いらっしゃったらお願いします！
|
No.38300 - 2016/07/29(Fri) 20:45:54 |
| ☆ Re: 経路の最大得点の問題です。 / angel | | | ああ、いえ、184通り試してくれたのは、うちのパソコンなのですが…。
( 簡単なプログラムを組んで )
逆に言えば、こういう問題って、プログラムを書いて計算するようなものだと思うんですが…。何か明確に最大値が分かるポイントがあるのか…。
一応、Ruby という言語で書いたプログラムを載せておきます。( 特にプログラミングに心得が無ければ無視してください )
W=[[[2,2,-2],[3,2,1],[1,2,-4],[-2,-1,-2]],[[6,-2,4],[5,-1,3],[-1,-3,1],[8,-2,4]]]
maxc=0
f=->x,y,m,b,r{
#puts "#{?\s*r}call: #{x},#{y}"
if x==3&&y==3
if b>maxc
#puts "** update **"
maxc=b
end
return
end
(0..3).each{|d|
xn,yn=*[[x+1,y],[x,y+1],[x-1,y],[x,y-1]][d]
xn>=0&&xn<4&&yn>=0&&yn<4 or next
mn=m|1<<(yn*4+xn)
m==mn and next
w=(d<2?1:-1)*(d%2==0? W[0][y][d<2?x:xn]:W[1][x][d<2?y:yn])
f[xn,yn,mn,b+w,r+1]
}
}
f[0,0,1,0,0]
puts maxc
|
No.38303 - 2016/07/29(Fri) 22:36:48 |
| ☆ Re: 経路の最大得点の問題です。 / IT | | | 同一点を２度以上通らないことから下記のABCが言えると思います。
A：長方形の対辺同士になる経路についてみたとき、通過する方向は互い違い。
・横方向は、下から順に見ると（→）か（→、←、→）
・縦方向は、左から順に見ると（↑）か（↑、↓、↑）
B：外周は、逆行できない。(A より）
C：右下隅、左上隅は、それぞれ通るなら、(→↑)、(↑→)セットで通る。
３つの部分に分けて、考えると簡単になると思います。
(1)下部のウ、カ、ケの周りの経路での最大得点は１８点
(2)上下を結ぶ中間の経路４本での最大得点は０点
(3)上部のア、エ、キの周りの経路での最大得点は４点。
と言えそうです。
そして、angel さんが見つけられた例は３つが同時に最大になるので 最大値は２２点。
(1)下部のウ、カ、ケの周りの経路：
Cよりケの下の→-２点は６点に変え、右の↑８点は０点に変えて考えると
横移動による得点≦3+2+6=11
縦移動による得点≦6-(-1)+0=7
(2)中間の経路４本：
上１本の場合の得点≦-1
上２本下１本の場合の得点≦+(-2)+(-1)-(-3)＝0
(3)上部のア、エ、キの周りの経路：
説明が少し面倒なので書きませんが,得点は4以下だと思います。
適当に場合分けすれば説明できると思いますので、ご自分で考えてみてください。
> だれか助けてください・・・
思考訓練（試行錯誤を含む）が目的であり、完璧に出来なくても大丈夫なのでは？
|
No.38306 - 2016/07/30(Sat) 00:52:55 |
| ☆ Re: 経路の最大得点の問題です。 / 中１ | | | 皆さまありがとうございます！
考えて頂いてとっても嬉しいです！
夏休み課題なので、先生の趣旨としては「じっくり考えろ」
という意志表示なのかもしれませんね。
場合分けなど行い、頑張ってみます！
|
No.38309 - 2016/07/30(Sat) 16:16:05 |
|
