6
は、実行時間O Nは、ディスクの数が移動することである（2 N）未満であるハノイの塔のための解決策はありますか？私の解はO（2 n）時間かかる。O（2^n）より良いハノイ解の塔？
また、以下の解決策は再帰を伴います。私たちは、より短時間でこれを解決するためにメモ帳の概念を使って動的プログラミングを使用できますか？
public void towersOfHanoi(
int num,
MyStack<Integer> from,
MyStack<Integer> to,
MyStack<Integer> spare
) {
if (num == 1) {
int i = from.pop();
to.push(i);
System.out.println("Move "+i+" from "+from.getName()+" to " + to.getName());
return;
}
towersOfHanoi(num - 1, from, spare, to);
towersOfHanoi(1, from, to, spare);
towersOfHanoi(num - 1, spare, to, from);
}
MyStacknameフィールドとアクセサを追加し、JavaのStackクラスの拡張版です。
また、同じ問題のバリエーションはありますか？
「ソリューションはありハノイ塔の稼働時間がO（2^n）未満の場合、ここでnは移動するディスクの数ですか？ - そうです。それは不正行為と呼ばれています:-) –
そしてどうすればいいのですか？ – dharam
...スタック全体をピックアップして一気に移動します。いいえ、2^nより優れたルールに従う方法はありません。 –