ハノータ詳細(初)
ハノータ(河内塔とも呼ばれる)問題はインドの古い伝説に由来する.大梵天は世界を創造する際にダイヤモンドの柱を3本作り、1本の柱に64枚の黄金の円盤を下から上へ大きさ順に積み上げた.大梵天はボロモンに円盤を下から大きさ順に別の柱に並べ直すよう命じた.そして小円盤には円盤を拡大することはできないと規定している.3本の柱の間で一度に1つの円盤しか移動できず、関数を利用してN枚の円盤のハンノッタの移動ステップを実現
アルゴリズムの理解:
理解1:
マクロ的には,A上のn個の皿を要求通りにC上に移動するには,上のn−1の皿をB上に移動し,上のn−2個の皿をAに移動し,B上の皿をC上に移動し,A上のすべての皿をC上に移動し,Bをペダルとすることが考えられるが,これは比較的簡単な理解であるが,アルゴリズムの実現過程については,まだ徹底していない.
理解2:
皿数がnの場合、移動回数は2^n−1であるべきであることが分かった.これは式H(n)=2 H(n−1)+1で得られ,上のn−1個の皿を先にBに反転させ,最大の皿をCに移動させ,1ステップを費やした後,B上の皿をCに反転させ,2 H(n−1)ステップを要すると理解される.
その後、アメリカのある学者は意外な簡単なアルゴリズムを発見しました.順番に2歩操作すれば実現できます.まず、3つのテーブルを順番に最初と後ろに並べて、リングを形成し、Aの皿を移動し始め、時計回りにA B Cの順番に並べます.
nが奇数であれば、円盤の移動順序はA−>C−>B−>A−>C−>B−>Aである…つまり、2ステップ間隔で移動します.ここでnは皿位の層数を表し、例えば3層のハノータは1、3番目の皿を下から上へ移動する順番である.
nが偶数であると、円盤の移動の順序はA->B->C->A->B->C->A…である.つまり、1ステップ間隔で移動します.nの解釈は上の2番目の皿と同じA−>B−>C移動であった.
下は2つの類似の解題構想で、唯一異なるのは、3つの位置変数の順序に違いがあり、しばらく学業の原因で、完備していないので、まだ責任を持って、後期は引き続き完備します.
一、
二、下の方式はまだ改善しなければならないので、結果を出すことができますが、手順の詳細はしていません.参考にします.
アルゴリズムの理解:
理解1:
マクロ的には,A上のn個の皿を要求通りにC上に移動するには,上のn−1の皿をB上に移動し,上のn−2個の皿をAに移動し,B上の皿をC上に移動し,A上のすべての皿をC上に移動し,Bをペダルとすることが考えられるが,これは比較的簡単な理解であるが,アルゴリズムの実現過程については,まだ徹底していない.
理解2:
皿数がnの場合、移動回数は2^n−1であるべきであることが分かった.これは式H(n)=2 H(n−1)+1で得られ,上のn−1個の皿を先にBに反転させ,最大の皿をCに移動させ,1ステップを費やした後,B上の皿をCに反転させ,2 H(n−1)ステップを要すると理解される.
その後、アメリカのある学者は意外な簡単なアルゴリズムを発見しました.順番に2歩操作すれば実現できます.まず、3つのテーブルを順番に最初と後ろに並べて、リングを形成し、Aの皿を移動し始め、時計回りにA B Cの順番に並べます.
nが奇数であれば、円盤の移動順序はA−>C−>B−>A−>C−>B−>Aである…つまり、2ステップ間隔で移動します.ここでnは皿位の層数を表し、例えば3層のハノータは1、3番目の皿を下から上へ移動する順番である.
nが偶数であると、円盤の移動の順序はA->B->C->A->B->C->A…である.つまり、1ステップ間隔で移動します.nの解釈は上の2番目の皿と同じA−>B−>C移動であった.
下は2つの類似の解題構想で、唯一異なるのは、3つの位置変数の順序に違いがあり、しばらく学業の原因で、完備していないので、まだ責任を持って、後期は引き続き完備します.
一、
#!/bin/bashcount=0n_1()
# ，
{ let count++
echo " ${count} : ${2} ${1} ${3}"}n_2()
{ if [ $1 -eq 1 ];then
# 1 1 ， ，
n_1 $2 1 $4
else
# ， ， 。
n_2 $[$1-1] $2 $4 $3
# ， 。
n_1 $2 $1 $4
# ， n_2 ，
# n_2 。
# n_1 。
n_2 $[$1-1] $3 $2 $4
fi
}
read -p "please input the number: " num
n_2 $num X Y Z
num=3
n_2 3 X Y Z
n_2 2 X Z Y
n_2 1 X Y Z
n_1 X 1 Z
： 1 ： 1 X Z
n_1 X 2 Y
： 2 ： 2 X Y
n_2 1 Z X Y
n_1 Z 1 Y
： 3 ： 1 Z Y
n_1 X 3 Z
： 4 ： 3 X Z
n_2 2 Y X Z
n_2 1 Y Z X
n_1 Y 1 X
： 5 ： 1 Y X
n_1 Y 2 Z
： 6 ： 2 Y Z
n_2 1 X Y Z
n_1 X 1 Z
： 7 ： 1 X Z二、下の方式はまだ改善しなければならないので、結果を出すことができますが、手順の詳細はしていません.参考にします.
#!/bin/bash
sun=0
funa() {
let asd--
let sun++
echo " : $sun : $1 : $2 ----> $3 "
}
funb() {
if [ $1 -eq 1 ];then #
funa $1 $2 $4
# N A C
else
funb "$[$1-1]" $2 $4 $3
if [ $? -eq 0 ];then
echo "==================================================================$asd ---fun1"
fi
#1 N-1(4) A C B ------> A(A) B(C) C(b)
#3 B a c
# N-2(3) A B C -------> A B C Ab Bc Ca
# 2 a c b -------> A Bc Cb
# 1 a c b ------ a b c
funa $1 $2 $4
if [ $? -eq 0 ];then
echo "-=================================================================$asd ----fun2"
fi
#1 N A C
# N-1(4) A B
# N-1(4) B C
#N-2 (3) \
# b--a
# c--b
funb "$[$1-1]" $3 $2 $4
if [ $? -eq 0 ];then
echo "===================================================================$asd ----fun3"
fi
#1 N-1 4 B A C ----> A(B) B(A) C(C )
#3 a c b
#2 N-1 3 a B C ----> Ac Ba Cb
# 2 B a C
# 1
fi
}
read -p "shuru panshu : " asd
funb $asd A B C