LoginSignup
0
0

More than 3 years have passed since last update.

アルゴリズムパズルを解く【その1】

Posted at

目次

はじめに

こんにちは、前回の【その0】ぶりです。お久しぶりです。今回はキリよく? 5問目まで解いていきたいと思います。後、個人的に長くて読みづらいと思ったので目次をつけました。

4. 兵士の輸送

【問題内容】

  • 25人の兵士が川を渡る
  • 2人の少年が船で遊んでいるので借りる
  • 船には少年2人か兵士1人が乗れる
  • 兵士全員渡って、最後は少年2人が乗っている状態にしたい
  • 何回往復する?

【考察】

  • 最初は動きが決まっている
  • 1手目で向こう岸に少年2人で行って2手目で片方が帰ってくる
  • ここで両岸に少年が1人ずついる状態が重要
  • この状態でないと兵士は渡ることができない(兵士が往復するだけになるので)
  • 3手目で満を辞して兵士が渡る
  • 4手目で少年が帰ってくる
  • この4手で兵士1人が渡り状態は元に戻った(1セット)

【解答】

  1. 少年が2人で向こう岸へ
  2. 片方の少年が帰ってくる
  3. 兵士が向こう岸に渡る
  4. 向こう岸に残ってる少年が帰ってくる 以上の4手で1人の兵士が向こう岸に渡ることができた よって4n(n:運ぶ兵士の数)で渡れる 今回は25人なので25*4=100手、50往復で完了する

【感想】

小さなアルゴリズムを複数回繰り返すことで結果が得られるわかりやすい例。for文を使ったメソッド作るときにこういう考えになる。4問目にしてプログラミングちっくな問題だと思います。

5. 行と列の入れ替え

【問題内容】

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
12 10 11 9
16 14 5 13
8 6 7 15
4 2 3 1
  • 行と列を入れ替えて上の図を下の図にできる?

【考察】

  • まず思ったのは全体の数字の合計は変わらないということ
  • ただこのことは今回の問題にはあまり関係ない気がする
  • 行と列の入れ替えというところに着目してみる
  • とりあえず何回か行と列を動かしてみる
  • 気づいたのは行と列の間で数字の組み合わせは変わらないということ
  • 1行目に注目してみると行を動かしてももちろん組み合わせは変わらない、列を動かしても行の中で位置が移動するだけだ
  • 他の行、列にも同じことが言える

【解答】

できない
変わるはずのない行間列間の組み合わせが変わってしまっているため

【感想】

ここまでの問題とは違って手の付けどころが難しかったです。意外とわからない人もいるのではないでしょうか。私はちょっと時間かかりました。

おわりに

今日は2問解きました。ちょっと難しくなって来たかな?
こんな考え方もあるよっていう方がいましたらコメントくださると私が喜びます。
猛暑日のところも出て来ましたので体調には気をつけてお過ごしください。
今夜は勉強会参加して来ます。それでは。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0