アルゴリズム脳を身につけるためには、まずは再帰処理だ その1
アルゴリズムの基本の基本である再帰処理を0から考えることができていない。
例えば、ハノイの塔のアルゴリズムを考える際、3つの円盤を左の杭から右の杭に移動するだけのプログラムだと簡単にできる。
var n = 3; var hanoiList = init(n); console.log(hanoiList); moveDisk(0,2); moveDisk(0,1); moveDisk(2,1); moveDisk(0,2); moveDisk(1,0); moveDisk(1,2); moveDisk(0,2); function init(n){ var list = [[],[],[]]; for (var i = n; i>0; i--) { list[0].push(i); } return list } function moveDisk(from, to){ var disk = hanoiList[from].pop(); hanoiList[to].push(disk); console.log(hanoiList); }
しかし、円盤の数がN個になるとこの処理を沢山記載しないといけない。。くそだりぃ。
なので、そこでハノイの塔を動かすための規則性を考える。
①初期状態
0:n, n-1, ・・・3, 2, 1 1: 2:
②杭0から円盤を杭1に移動させる
0:n, n-1, ・・・3, 2 1:1 2:
③杭0から円盤を杭2に移動させる
0:n, n-1, ・・・3, 1:1 2:2
④杭1から円盤を杭2に移動させる
0:n, n-1, ・・・3, 1: 2:2,1
⑤杭0から円盤を杭1に移動させる
0:n, n-1, ・・・ 1:3 2:2,1
①〜⑤の処理を繰り返していくと下記の状態になる。
0:n 1:n-1, ・・・3, 2, 1 2:
⑥杭0から円盤を杭2に移動させる
0: 1:n-1, ・・・3, 2, 1 2:n
①〜⑥の処理を繰り返していくことで、杭3に移動することができる。
0: 1: 2:n,n-1, ・・・3, 2, 1
次回は、これをプログラミングに起こしてみる。