ここから本文です

公務員試験の判断推理に関する質問です。

economics_statistics_xxxさん

2017/11/1513:22:10

公務員試験の判断推理に関する質問です。

以下の問題について、過程も含め、解き方がわからないので教えてください!

回答は5です。


次の図のようにA〜Cの3本の容器がある。Aの容器には、Ⅰ〜Ⅳの数字が書かれた4個のボールが下から数字の大きい順に入っており、BとCの容器は空である。Aの容器の4個のボールをCの容器に図のように移すには、最低何回の移動が必要か。ただし、ボールは1回の移動につき1個ずつ他の容器に動かし、小さい数字のボールの上に大きい数字のボールをのせないものとする。

1.7回、2.9回、3.11回、4.13回、5.15回

ご回答よろしくお願いいたします!

ボール,容器,解き方,公務員試験,判断推理,ハノイ,回数

閲覧数:
29
回答数:
2
お礼:
50枚

違反報告

ベストアンサーに選ばれた回答

kzk_4465さん

2017/11/1513:31:25

以下のように考えます.

仮にn個のボールをAからCに移すのに必要な回数をP(n)とします.

次に(n+1)個のボールを移すのに必要な回数P(n+1)を考えますが,これは
①まずn個のボールをAからBに移す → P(n)回
②n+1個目のボールをAからCに移す → 1回
③再びn個のボールをBからCに移す → P(n)回
という手順で移動が完了します.
よって,
P(n+1)=2P(n)+1 …☆
となります.

ボールが1個しかない場合は当然1回で移せるので,
P(1)=1
です.
よって以下,☆の式に順次代入して行けば,
P(2)=2・1+1=3
P(3)=2・3+1=7
P(4)=2・7+1=15
したがって答えは15回となります.

  • 質問者

    economics_statistics_xxxさん

    2017/11/2113:40:52

    返信が遅くなり、大変申し訳ございません。

    丁寧な解説、誠にありがとうございます。

    ①n個のボールをAからBに移す回数と③再びn個のボールをBからCに移す回数、n個のボールをAからCに移す回数がともにP(n)回であるのは、単にA,B,C間を移動させているだけなので、同じ回数ということですか。

    重ね重ねお手数おかけして誠に申し訳ございませんがよろしくお願いいたします!

返信を取り消しますが
よろしいですか?

  • 取り消す
  • キャンセル

質問した人からのコメント

2017/11/21 21:06:24

丁寧なご回答誠にありがとうございました!

ベストアンサー以外の回答

1〜1件/1件中

2017/11/1513:34:43

結論だけ言うと、
このルールでn個のボールを移すときの最小回数は、
2のn乗-1 回
になります。
4個なので、
2の4乗-1=16-1=15回
です。

詳しくは、
ハノイの塔
で検索してみてください。

あわせて知りたい

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問や知恵ノートは選択されたID/ニックネームのMy知恵袋で確認できます。