- 締切済み
ハノイの塔について課題が出たのですが、言ってる意味自体解りません（Tへ
ハノイの塔について課題が出たのですが、言ってる意味自体解りません（TへT） 課題内容は以下のものなんですがぁ;;助けてくださぁ～い↓↓ (1)ハノイの塔の時間計算量が 2n - 1 になるのはなぜか． また，1 枚の円盤を移すのに 2 秒かかるとする． ハノイの塔で，30 枚の円盤を移すのに約何年かかるか求めよ． ただし，1 年を 365 日とする． (2)8 Queen で，しらみつぶし法によってあらゆる置き方を確認するのに何回かかるか求めよ． また，8 Queen で，一行には一つの Queen しか置けないことを考慮した場合のあらゆる置き方を確認するのに何回かかるか求めよ． いずれも，Queen を一個ずつ確認するのではなく，8 個の Queen の置き方一通りについて一回の確認とみなす． 求めた過程も説明すること．
- くまった くまｓ（@raf24232）
- お礼率0% (0/7)
- 数学・算数
- 回答数4
- ありがとう数7
- みんなの回答 （4）
- 専門家の回答
みんなの回答
- Ishiwara
- ベストアンサー率24% (462/1914)
質問者さんが、どこまで理解されているのか、そういう情報がないと回答できません。 Tower of Hanoi や Eight Queen Problem のルールは、よくご存知なのですよね。 簡単なパズルについてのアルゴリズム作成のご経験はあるのですよね。 ハノイの塔について「時間」を尋ねるのは、わざと問題を難しくしているだけであって、もともと時間は無関係で、「移動回数」を問うている問題です。 現位置Ａからn-1個の盤を位置Ｂへ移すには、f(n-1)回かかりますよね。次に最後の盤を位置Ｃへ移すのに１回、Ｂから全部Ｃへ移すのにf(n-1)回、合計 f(n)=2f(n-1)+1だけかかります。証明には数学的帰納法を使ってください。 クイーン問題は、条件をしっかり定めないとできません。ひたすら愚直にあるがままをしらみつぶしにするなら８の８乗でしょう。考えようによっては「すでにある行が使われているのを見て吟味を省略する」なら８の階乗で済むと言えるかもしれません。しかし、ある行が使われているかどうかを吟味するのだって０秒ではできません。したがって「何をもって“１回しらべた”と数えるのか」出題者と回答者の間に了解がないと正確には答えられないことになります。 また「置き方１とおりについて１回の確認とみなす」というのであれば「アルゴリズムの問題」とはまったく無関係な話となり「解がいくつ存在するか」という単なる数学の問題になると思います。
- alice_44
- ベストアンサー率44% (2109/4759)
言っている意味： (1) ｎ枚の板からなるハノイの塔の解は、板の移動が (2^n)-1 回であることを示せ。 また、2 秒の (2^30)-1 倍は、何年か。 (2) チェス盤の各行に一個づつの Queen を置く。置き方は、何通りあるか。 それぞれの置き方が 8 Queenn 問題の解であるかを調べようというのだが、 どう調べるかは、この問題とは別の話。 ハノイの塔は、 無駄な手を打たないために、同じ板を 2 手続けて動かさない…と決めるだけで、 第 2 手移後は、自動的に手が決まる。それを (2^n)-1 手行うと、n 枚の板が 初めとは別の一本の柱に集まる。
- htms42
- ベストアンサー率47% (1120/2361)
ハノイの塔の方だけ （１）「何回の操作でできるか」 （２）「その回数でやるのにはどうすればいいか」 このゲームの難しさは（２）の方にあります。（１）は簡単です。 硬貨を使ってでもやってみられたらいいと思います。 ５００円、１００円、５０円、１０円、５円、１円 と６種類あります。やってみるにはいい数です。 ［ｎ］をｎ個の塊とします。ｎをｎ番目の硬貨とします。 ［ｎ］ ［ｎ］ --------------------- を -------------------- Ａ Ｂ Ｃ Ａ Ｂ Ｃ に移すのに必要な操作の回数をＮ(ｎ)とします。 Ｎ(ｎ＋１)＝２Ｎ(ｎ)＋１ になります。 ［ｎ］ ［ｎ］ ｎ＋１ ｎ＋１ --------------------- → -------------------- Ａ Ｂ Ｃ Ａ Ｂ Ｃ ［ｎ］ ［ｎ］ ｎ＋１ ｎ＋１ → -------------------- → -------------------- Ａ Ｂ Ｃ Ａ Ｂ Ｃ Ｎ(１)＝１ですから Ｎ(２)＝３、Ｎ(３)＝７、・・・、Ｎ(ｎ)＝２^n－１、・・・ がすぐに分かります。 Ｎ(６)＝６３ですからやってみてください。 Ｎ(５)＝３１でも難しいです。 どういう手順でやればこんがらがらずにこの回数でやることができるかは別のルールが必要です。 それがアルゴリズムです。
- goldenleaf
- ベストアンサー率39% (29/74)
ハノイの塔、8Queen問題とも、アルゴリズムや計算量の分野で非常に有名な問題です。 従って、図書館、ネットにいくらでも資料は転がっています。調べることに困る課題では有りません。 問題の意味自体分からない、ということは講義を全く聴いていないか理解していないかですね。 そのような人は素直に落第してください。したくないなら相応の努力をしましょう。
関連するQ&A
- ハノイの塔っぽいゲームだったと思うのですがルールが思い出せません
質問お願いします。 たしかハノイの塔のようなゲームだったと思うのですが ７枚の円盤を他の器を使いながら移し変えて、もとの入れ物に逆さまの順番にする。 これが終わったら世界は崩壊するみたいな設定だと思ったのですが、これで合っているでしょうか？ 実際計算すると何万年もかかるというオチだったのですが、詳しい設定や名前、ルールなどがうろ覚えです。 円盤はたしか７枚だったと思うのですが、wikipediaのハノイの塔のバリエーションでは６４枚も使っているので別のゲームだったかなと混乱しています。 覚えてる方がいましたらこのゲームについて詳しくお願いします。
- 締切済み
- 数学・算数
- ハノイの塔のチェック関数
ユニックス等のシステムコールを使ったハノイの塔を検査するプログラムです。質問したいのは円盤数、つまり塔の枚数が30枚で実行すると、チェックします。チェックされていいのですが20枚の時はされません。 なぜされるのかをおしえてください。 チェックされる条件は円盤番号が2回以上現れる。 0以外の番号の間には0がくるです。 チェック関数を抜き出すと void *Check(void *arg){ int i,nchecks=0; while(sw) { sleep(1); nchecks++; for(i=0;i<ndisks;i++) Z[i]=0; for(i=0;i<ndisks;i++){ if (A[i]!=0) { if (Z[A[i]-1]!=0) { fprintf(stderr,"Inconsistent(1)!!! (Tower-A Tries=%d)(i=%d)\n",nchecks,i); break;} Z[A[i]-1]=1; } if (B[i]!=0) { if (Z[B[i]-1]!=0) { fprintf(stderr,"Inconsistent(2)!!! (Tower-B Tries=%d)(i=%d)\n",nchecks,i); break;} Z[B[i]-1]=1; } if (C[i]!=0) { if (Z[C[i]-1]!=0) { fprintf(stderr,"Inconsistent(3)!!! (Tower-C Tries=%d)(i=%d)\n",nchecks,i); break;} Z[C[i]-1]=1; } } for(i=0;i<ndisks;i++) { if (Z[i]==0) { fprintf(stderr,"Inconsistent(4)!!! (Final Tries=%d)(i=%d)\n",nchecks,i); break;} } } }
- 締切済み
- C・C++・C#
- 課題図書について
２年からゼミに入ることになり、そのゼミで春休みの課題として課題図書がでました。 ガイダンスが今日あり、２週間後に提出なので少しは余裕がありますが、指定校推薦の受験？のときと、大学に入る前の課題として出た時と、合わせて２回しか書いたことがありません。 ２回とも提出すれば合否や成績にかかわらないので、なんとなくで書いてました。 しかし、今回はしっかり書かなければいけないので焦っています。 いくつか質問したいことがあります。 (1)ある『ケインズ』という本をについて2500字以上のレポートを書きます。テーマは、「現代に活かす」です。 この場合、最初に要約はいれますか？ (2)本を読む上でのコツなどはありますか？ 例えば、最初に一通り読んでから、また読み直し書く、メモを片手に読んでいくなど・・・ (3)昔から読解力がないんですが、キーワードや著者が伝えたいことを適切に読み取るコツなどを教えてください 長々と書いてしましましたが、以上のことについて教えてください。
- ベストアンサー
- 日本語・現代文・国語
- ハノイの塔
★自分が理解している事 「(n-1)ハノイが解けると仮定するとnハノイも解けること」 は理解できます。 そして数学的帰納法によりすべての自然数についてハノイは「解ける」 ここまではわかります。 ★わからないのは、その「解き方」です。 「解ける」ことはわかるのですが「解き方」がわからないのです。 何故このプログラムで正解が表示されるのかが理解できないのです。 確かに、紙と鉛筆でプログラムの流れを追っていくと解けています。 しかし、何でこのプログラムで解けるのかがわからないのです。 棒ｘは出発点 棒ｙは目的地 棒ｚは作業棒 です。 (n-1)ハノイをひとかたまりと考え、作業棒Zに移す。 nハノイを目的地Yに移す。 (n-1)ハノイをひとかたまりと考え、目的地Yに移す。 そんな説明で確かに納得した気になりはします。 しかしこのプログラムでは(n-2)以下の場合についてはいっさい語っていません。 何かだまされてる気がします。 このプログラムでは(n-1)について語っていますが (n-2)以下については全く語っていません。 数学的帰納法により「解ける」ことは証明済みですが、 「その解き方」がこのプログラムでよいという「証明」はありますでしょうか？ 理解のコツはありますでしょうか？ よろしくお願いいたします。 #include<stdio.h> #include<stdlib.h> void hanoi(int n, char x, char y, char z) { if(n==0) {/* 何もしない */} else { hanoi(n-1,x,z,y); printf("%c->%c,",x,y); hanoi(n-1,z,y,x); } } int main(void) { int num; scanf("%d",&num); hanoi(num,'A','B','C'); return 0; }
- ベストアンサー
- C・C++・C#
- ハノイの塔の解き方
ハノイの塔について質問なのですが、 3本棒の 5枚の円盤をときたいのですが、 最短距離で動かす法則を知りたいのですがさっぱり分かりません。 他でも調べたのですが数式がでてきて、よくわからなかったです。すみません、どなたか教えてください！
- ベストアンサー
- その他（趣味・娯楽・エンターテイメント）
- ハノイの塔
次のｃ言語で書かれたハノイの塔のプログラムをZ80で動作させたいのですが、アセンブルするとどうなるのでしょうか？？教えてください。 void move(char n,char a,char b){ if(n>1)move(n-1,a,6-a-b); if(n>1)move(n-1,6-a-b,b); } int main(){ char n=5; move(n,1,2); }
- ベストアンサー
- その他（プログラミング・開発）
- ある程度重要な課題で、なぜか取り組めないものがあり
こんばんは。 50歳代のサラリーマンです。 仕事は普通にやっていて、家族もそれなりに元気で、周りから見ればまあ普通に生活しています。 仕事では役職にもついていますし、ある程度信頼もされていると思います。 生活していればいろいろな課題や問題が出てきますよね。 仕事でもプライベートでも、課題や問題はきちんと取り組んで、それなりに解決してきています。 職場でも家庭でも真面目な人だという評価は得ていると思います。 ただ、なぜかいくつかの課題については取り組めなかったり途中で放棄したりしてしまうことがあります。 最近で言えば年賀状ですね。 11月くらいになったら出す人をリストアップして、喪中葉書を確認して12月になったらデザインして、プリントアウトして、住所録を整理して宛名もプリントアウトして、ちょっと手書きでコメントして、郵便局に出しに行く。 これだけ。 出来る年は問題なく出来て、12月20日くらいに郵便局に出しに行けるんです。 でも、出来ない年はなぜかできなくて、途中で作業が中断し、12月25日くらいから「今日はやろう」「そろそろまずいぞ」とかって思うんだけど作業がすすまずに、12月30日くらいに一気に適当にやって、郵便局に出しに行くって感じです。そういう年はいくつもミスが出ます。 もはや出せずに、来た年賀状だけに返事を出したって年もありました。 出来る年は出来るんだけど、出来ない年はできない。 妻も最近はしょうがないと思っているのか、あまり気にしていません。 年賀状くらいだったら、出せなくてもたいした問題じゃないっていえばそうなんだろうけど、それ以外にも結構重要なことで同様に義理を欠いて人間関係がまずくなったこともありました。 その他でも、このくらいの期間で出来るだろうと思っていても、なぜか作業ができずに、とんでもなくレベルの低いものしかできないことが年に数回あります。 100個の課題があるとしたら、そのうち1，2個でそういうことがある感じですかね。 そういうとき、特に忙しいとか、特別難しいとかいうことではないんですよね。 いまも半年くらい前から課題になっているある程度重要な案件に取りかかろうと思っていて、でもなぜか進まない状態で、もう今日は寝て明日やろうと思っているんですが、「なぜ進まないんだろう。そういえばいままでもこういうことはあった」と思って質問しています。 こういったことって、あなたにもありますか？ どういった理由が考えられるんでしょうか？ 過去にこういうことがあって、解決した方はいますか？ 参考になる書籍とかありますか？ 解決策や参考になる書籍などをご存じの方がいたら教えてください。 よろしくお願いします。
- ベストアンサー
- 人生相談
