ハノイの塔について課題が出たのですが、言ってる意味自体解りません(TへT)
課題内容は以下のものなんですがぁ;;助けてくださぁ~い↓↓
(1)ハノイの塔の時間計算量が 2n - 1 になるのはなぜか.
また,1 枚の円盤を移すのに 2 秒かかるとする.
ハノイの塔で,30 枚の円盤を移すのに約何年かかるか求めよ.
ただし,1 年を 365 日とする.
(2)8 Queen で,しらみつぶし法によってあらゆる置き方を確認するのに何回かかるか求めよ.
また,8 Queen で,一行には一つの Queen しか置けないことを考慮した場合のあらゆる置き方を確認するのに何回かかるか求めよ.
いずれも,Queen を一個ずつ確認するのではなく,8 個の Queen の置き方一通りについて一回の確認とみなす.
求めた過程も説明すること.
A 回答 (4件)
- 最新から表示
- 回答順に表示
No.4
- 回答日時:
質問者さんが、どこまで理解されているのか、そういう情報がないと回答できません。
Tower of Hanoi や Eight Queen Problem のルールは、よくご存知なのですよね。
簡単なパズルについてのアルゴリズム作成のご経験はあるのですよね。
ハノイの塔について「時間」を尋ねるのは、わざと問題を難しくしているだけであって、もともと時間は無関係で、「移動回数」を問うている問題です。
現位置Aからn-1個の盤を位置Bへ移すには、f(n-1)回かかりますよね。次に最後の盤を位置Cへ移すのに1回、Bから全部Cへ移すのにf(n-1)回、合計 f(n)=2f(n-1)+1だけかかります。証明には数学的帰納法を使ってください。
クイーン問題は、条件をしっかり定めないとできません。ひたすら愚直にあるがままをしらみつぶしにするなら8の8乗でしょう。考えようによっては「すでにある行が使われているのを見て吟味を省略する」なら8の階乗で済むと言えるかもしれません。しかし、ある行が使われているかどうかを吟味するのだって0秒ではできません。したがって「何をもって“1回しらべた”と数えるのか」出題者と回答者の間に了解がないと正確には答えられないことになります。
また「置き方1とおりについて1回の確認とみなす」というのであれば「アルゴリズムの問題」とはまったく無関係な話となり「解がいくつ存在するか」という単なる数学の問題になると思います。
No.3
- 回答日時:
言っている意味:
(1) n枚の板からなるハノイの塔の解は、板の移動が (2^n)-1 回であることを示せ。
また、2 秒の (2^30)-1 倍は、何年か。
(2) チェス盤の各行に一個づつの Queen を置く。置き方は、何通りあるか。
それぞれの置き方が 8 Queenn 問題の解であるかを調べようというのだが、
どう調べるかは、この問題とは別の話。
ハノイの塔は、
無駄な手を打たないために、同じ板を 2 手続けて動かさない…と決めるだけで、
第 2 手移後は、自動的に手が決まる。それを (2^n)-1 手行うと、n 枚の板が
初めとは別の一本の柱に集まる。
No.2
- 回答日時:
ハノイの塔の方だけ
(1)「何回の操作でできるか」
(2)「その回数でやるのにはどうすればいいか」
このゲームの難しさは(2)の方にあります。(1)は簡単です。
硬貨を使ってでもやってみられたらいいと思います。
500円、100円、50円、10円、5円、1円
と6種類あります。やってみるにはいい数です。
[n]をn個の塊とします。nをn番目の硬貨とします。
[n] [n]
--------------------- を --------------------
A B C A B C
に移すのに必要な操作の回数をN(n)とします。
N(n+1)=2N(n)+1
になります。
[n] [n]
n+1 n+1
--------------------- → --------------------
A B C A B C
[n] [n]
n+1 n+1
→ -------------------- → --------------------
A B C A B C
N(1)=1ですから
N(2)=3、N(3)=7、・・・、N(n)=2^n-1、・・・
がすぐに分かります。
N(6)=63ですからやってみてください。
N(5)=31でも難しいです。
どういう手順でやればこんがらがらずにこの回数でやることができるかは別のルールが必要です。
それがアルゴリズムです。
No.1
- 回答日時:
ハノイの塔、8Queen問題とも、アルゴリズムや計算量の分野で非常に有名な問題です。
従って、図書館、ネットにいくらでも資料は転がっています。調べることに困る課題では有りません。
問題の意味自体分からない、ということは講義を全く聴いていないか理解していないかですね。
そのような人は素直に落第してください。したくないなら相応の努力をしましょう。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- 高校 「高校生クイズ。 何問目」。「2問目」です。「回答(解答)」をお願い出来ますか? 理解出来ません。 1 2022/04/17 13:44
- AI・ロボット chat.openAIの限界。私は「何事にもやる気が起きない」と相談して、対策よりも原因に付いて 3 2023/04/13 11:34
- 工学 いつもありがとうございます、 円盤の上に何ccの液を液滴させながら円盤を回したら液が拡がって円盤の全 5 2023/03/18 14:17
- 物理学 波動方程式のようなもの 1 2023/05/13 07:23
- 政治 これは自民党が統一教会の「使い走り」をさせられていたということですか? 5 2022/10/21 10:51
- 数学 高校数学の質問です 文字を消去したり、置き換えたりしたら、残った文字に範囲がつくかどうか調べるという 4 2023/05/03 18:18
- 人類学・考古学 大学のレポートと課題の違いと書き方 3 2022/04/17 03:55
- 物理学 風車が回転する理由 5 2023/05/08 08:03
- エアコン・クーラー・冷暖房機 エアコン初期不良の対応について 4 2022/08/04 19:37
- 訴訟・裁判 国家賠償法と公務員個人の賠償責任 3 2022/11/26 23:10
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
数学についてです 「 aを定数と...
-
答えを教えて
-
Excelで合計値を基にデータを均...
-
tanX=Xの解
-
16の4乗根は±2ではない!?
-
高校数学の問題について 2次方...
-
微分の重解条件は公式として使...
-
4次関数と二重接線に囲まれる面...
-
cos x = 0の解の書き方について
-
a(x-α)(x-β)
-
定数係数以外の2階常微分方程...
-
数学II 三次方程式 x^3-5x^2+ax...
-
連立二次不等式についての問題
-
等差数列の和を利用・・?
-
偏微分方程式のラプラス変換に...
-
定数変化法って全ての解を出せる?
-
y''=-yの一般解について
-
確率の求め方を教えてください
-
2次方程式の2解がともに0と3の...
-
x^y=y^x (x>y)を満たす整数解は...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
Excelで合計値を基にデータを均...
-
tanX=Xの解
-
16の4乗根は±2ではない!?
-
数学についてです 「 aを定数と...
-
答えを教えて
-
一枚の板から何枚取れるか?
-
微分方程式の解を、微分方程式...
-
解なし≠解はない
-
解に3つ以上±や∓がある時複号...
-
微分の重解条件は公式として使...
-
数学I 二次方程式について次の...
-
微分方程式 定常解について・・・
-
x^y=y^x (x>y)を満たす整数解は...
-
3次関数と直線が接する場合、...
-
3次方程式の解の範囲について
-
3次関数と1次関数が接するとき
-
複数の品目での単価と全体の合...
-
次の関数が,与えられた微分方...
-
定数係数以外の2階常微分方程...
-
3次方程式
おすすめ情報