N88-BASIC,Cでハノイの塔 (2回目)
2024/12/27(金)
N88-BASIC,Cでハノイの塔 (2回目)
再帰を使用しない手順(hanoi)
■ 前提
▼ 参照
https://ulprojectmail.blogspot.com/2024/12/hanoi-3.html
ハノイの塔 (3回目)
より
▼ 前提
3本(A,B,C)の棒とn枚の円盤(小さい順に1～nとする)がある
Aに1～nの円盤が上から順に積まれている
▼ 目標
1～nの円盤全てをCに移動させる
▼ ルール
小さい円盤の上に大きい円盤は置けない
1度に動かせる円盤は1枚のみ
▼ 定義
A,B,Cの一番上の円盤をpA, pB, pCとし、円盤が無い時は最大値とする
円盤をAからCに移動する事をA->Cと書くことにする
▼ nの場合
nが奇数の時
A = Aのtop, pB = Bのtop, pC = Cのtop
pAB = A->B, pBC = B->C, pCA = C->A
pBA = B->A, pCB = C->B, pAC = A->C
nが偶数の時(A⇔B)
pA = Bのtop, pB = Bのtop, pC = Cのtop
pAB = B->A, pBC = A->C, pCA = C->B
pBA = A->B, pCB = C->A, pAC = B->C
と定義する
つまり以下偶数の時は(A⇔B)と読み替える
nが偶数の時のみ以下の2行を追加
pBA
pB < pC なら pBC 違うなら pCB
pAC
pA ≠ pBの間以下を繰り返す
pA < pB なら pAB 違うなら pBA
pCB
pC < pA なら pCA 違うなら pAC
pBA
pB < pC なら pBC 違うなら pCB
pAC
▼ 移動回数N(n)
N(n) = 2n - 1 回
▼ n = 64の移動時間T(64)
N(64) = 264 - 1 = 18,446,744,073,709,551,615回
グレゴリオ暦(現在の使用されている暦)
3600×24×365.2425 = 31,556,952秒/年
α = 18,446,744,073,709,551,615 / 31,556,952 年/(秒/回)
= 584,554,049,253.855429859005… 年/(秒/回)
n移動する時間をT(n)とすると
T(64) = αT(n)/N(n) (年)
■ 動作
変数名など内部ではA,B,Cを(pole)1,2,3または0,1,2と表現しています
nを入力し
1:A->Cの様に円盤の番号1～n(小～大)と棒A,B,C間の移動を表示する
今回の手順は再帰を使用していません
VL,NL,XL-BASICとdlg～.zip(han002.bas)は
このブログ(以下のリンク)から
ダウンロードできます
https://ulprojectmail.blogspot.com
Readme.txtを読んで遊んで下さい
N88-BASIC,Cでハノイの塔 (2回目)
再帰を使用しない手順(hanoi)
■ 前提
▼ 参照
https://ulprojectmail.blogspot.com/2024/12/hanoi-3.html
ハノイの塔 (3回目)
より
▼ 前提
3本(A,B,C)の棒とn枚の円盤(小さい順に1～nとする)がある
Aに1～nの円盤が上から順に積まれている
▼ 目標
1～nの円盤全てをCに移動させる
▼ ルール
小さい円盤の上に大きい円盤は置けない
1度に動かせる円盤は1枚のみ
▼ 定義
A,B,Cの一番上の円盤をpA, pB, pCとし、円盤が無い時は最大値とする
円盤をAからCに移動する事をA->Cと書くことにする
▼ nの場合
nが奇数の時
A = Aのtop, pB = Bのtop, pC = Cのtop
pAB = A->B, pBC = B->C, pCA = C->A
pBA = B->A, pCB = C->B, pAC = A->C
nが偶数の時(A⇔B)
pA = Bのtop, pB = Bのtop, pC = Cのtop
pAB = B->A, pBC = A->C, pCA = C->B
pBA = A->B, pCB = C->A, pAC = B->C
と定義する
つまり以下偶数の時は(A⇔B)と読み替える
nが偶数の時のみ以下の2行を追加
pBA
pB < pC なら pBC 違うなら pCB
pAC
pA ≠ pBの間以下を繰り返す
pA < pB なら pAB 違うなら pBA
pCB
pC < pA なら pCA 違うなら pAC
pBA
pB < pC なら pBC 違うなら pCB
pAC
▼ 移動回数N(n)
N(n) = 2n - 1 回
▼ n = 64の移動時間T(64)
N(64) = 264 - 1 = 18,446,744,073,709,551,615回
グレゴリオ暦(現在の使用されている暦)
3600×24×365.2425 = 31,556,952秒/年
α = 18,446,744,073,709,551,615 / 31,556,952 年/(秒/回)
= 584,554,049,253.855429859005… 年/(秒/回)
n移動する時間をT(n)とすると
T(64) = αT(n)/N(n) (年)
■ 動作
変数名など内部ではA,B,Cを(pole)1,2,3または0,1,2と表現しています
nを入力し
1:A->Cの様に円盤の番号1～n(小～大)と棒A,B,C間の移動を表示する
今回の手順は再帰を使用していません
VL,NL,XL-BASICとdlg～.zip(han002.bas)は
このブログ(以下のリンク)から
ダウンロードできます
https://ulprojectmail.blogspot.com
Readme.txtを読んで遊んで下さい
