ハノイの塔について課題が出たのですが、言ってる意味自体解りません（Tへ

質問

ハノイの塔について課題が出たのですが、言ってる意味自体解りません（TへT）
課題内容は以下のものなんですがぁ;;助けてくださぁ～い↓↓

(1)ハノイの塔の時間計算量が 2n - 1 になるのはなぜか．
また，1 枚の円盤を移すのに 2 秒かかるとする．
ハノイの塔で，30 枚の円盤を移すのに約何年かかるか求めよ．
ただし，1 年を 365 日とする．

(2)8 Queen で，しらみつぶし法によってあらゆる置き方を確認するのに何回かかるか求めよ．
また，8 Queen で，一行には一つの Queen しか置けないことを考慮した場合のあらゆる置き方を確認するのに何回かかるか求めよ．
いずれも，Queen を一個ずつ確認するのではなく，8 個の Queen の置き方一通りについて一回の確認とみなす．
求めた過程も説明すること．

回答No.4

Ishiwara

質問者さんが、どこまで理解されているのか、そういう情報がないと回答できません。
Tower of Hanoi や Eight Queen Problem のルールは、よくご存知なのですよね。
簡単なパズルについてのアルゴリズム作成のご経験はあるのですよね。

ハノイの塔について「時間」を尋ねるのは、わざと問題を難しくしているだけであって、もともと時間は無関係で、「移動回数」を問うている問題です。
現位置Ａからn-1個の盤を位置Ｂへ移すには、f(n-1)回かかりますよね。次に最後の盤を位置Ｃへ移すのに１回、Ｂから全部Ｃへ移すのにf(n-1)回、合計 f(n)=2f(n-1)+1だけかかります。証明には数学的帰納法を使ってください。

クイーン問題は、条件をしっかり定めないとできません。ひたすら愚直にあるがままをしらみつぶしにするなら８の８乗でしょう。考えようによっては「すでにある行が使われているのを見て吟味を省略する」なら８の階乗で済むと言えるかもしれません。しかし、ある行が使われているかどうかを吟味するのだって０秒ではできません。したがって「何をもって“１回しらべた”と数えるのか」出題者と回答者の間に了解がないと正確には答えられないことになります。

また「置き方１とおりについて１回の確認とみなす」というのであれば「アルゴリズムの問題」とはまったく無関係な話となり「解がいくつ存在するか」という単なる数学の問題になると思います。

回答No.3

alice_44

言っている意味：

(1) ｎ枚の板からなるハノイの塔の解は、板の移動が (2^n)-1 回であることを示せ。
　　また、2 秒の (2^30)-1 倍は、何年か。

(2) チェス盤の各行に一個づつの Queen を置く。置き方は、何通りあるか。
　　それぞれの置き方が 8 Queenn 問題の解であるかを調べようというのだが、
　　どう調べるかは、この問題とは別の話。

ハノイの塔は、
無駄な手を打たないために、同じ板を 2 手続けて動かさない…と決めるだけで、
第 2 手移後は、自動的に手が決まる。それを (2^n)-1 手行うと、n 枚の板が
初めとは別の一本の柱に集まる。

回答No.2

htms42

ハノイの塔の方だけ

（１）「何回の操作でできるか」
（２）「その回数でやるのにはどうすればいいか」

このゲームの難しさは（２）の方にあります。（１）は簡単です。

硬貨を使ってでもやってみられたらいいと思います。
５００円、１００円、５０円、１０円、５円、１円
と６種類あります。やってみるにはいい数です。

［ｎ］をｎ個の塊とします。ｎをｎ番目の硬貨とします。

［ｎ］　　　　　　　　　　　　　　　　　　　　　　［ｎ］
---------------------　を　--------------------
Ａ　　　　　Ｂ　　　　　Ｃ　　　　　　　Ａ　　　　　Ｂ　　　　　Ｃ

に移すのに必要な操作の回数をＮ(ｎ)とします。
Ｎ(ｎ＋１)＝２Ｎ(ｎ)＋１
になります。

［ｎ］　　　　　　　　　　　　　　　　　　　　　　　［ｎ］
ｎ＋１　　　　　　　　　　　　　　　　　ｎ＋１　　　　　　　　　　　　　　
---------------------　→　　--------------------
Ａ　　　　　Ｂ　　　　　Ｃ　　　　　　　　Ａ　　　　　Ｂ　　　　　Ｃ

　　　　　　［ｎ］　　　　　　　　　　　　　　　　　　　　　　　　［ｎ］
　　　　　　　　　　　　ｎ＋１　　　　　　　　　　　　　　　　　ｎ＋１
→　--------------------　→　--------------------
　 Ａ　　　　　Ｂ　　　　　Ｃ　　　　　　　　Ａ　　　　　Ｂ　　　　　Ｃ

Ｎ(１)＝１ですから
Ｎ(２)＝３、Ｎ(３)＝７、・・・、Ｎ(ｎ)＝２^n－１、・・・
がすぐに分かります。

Ｎ(６)＝６３ですからやってみてください。
Ｎ(５)＝３１でも難しいです。
どういう手順でやればこんがらがらずにこの回数でやることができるかは別のルールが必要です。
それがアルゴリズムです。

回答No.1

goldenleaf

ハノイの塔、8Queen問題とも、アルゴリズムや計算量の分野で非常に有名な問題です。

従って、図書館、ネットにいくらでも資料は転がっています。調べることに困る課題では有りません。

問題の意味自体分からない、ということは講義を全く聴いていないか理解していないかですね。
そのような人は素直に落第してください。したくないなら相応の努力をしましょう。