| 6. Clock
Let c1(d) be the cost of moving a stack of d disks one peg clockwise.
Let c2(d) be the cost of moving a stack of d disks two pegs clockwise.
Then c1(0) = c2(0) = 0, c1(1) = 1, c2(1) = 2, and
c1(d) = c2(d-1) + 1 + c2(d-1)
c2(d) = c2(d-1) + 1 + c1(d-1) + 1 + c2(d-1)
Or,
c2(d) = 2 c2(d-1) + 2 c2(d-2) + 3
Letting f(d) = c2(d) + 1, then f(0) = 1, f(1) = 3, and
f(d) = 2 f(d-1) + 2 f(d-2)
d d
Then, f(d) = w x + y z , where
x = 1 + sqrt(3)
z = 1 - sqrt(3)
w = (3 + 2 sqrt(3))/6
y = (3 - 2 sqrt(3))/6
2
(x and z are roots of x - 2 x - 2 = 0, w and y are chosen to fit the
initial conditions).
Thus,
3 + 2 sqrt(3) d 3 - 2 sqrt(3) d
c2(d) = ------------- (1 + sqrt(3)) + ------------- (1 - sqrt(3)) - 1
6 6
d d
c1(d) = (3 + sqrt(3)) (1 + sqrt(3)) + (3 - sqrt(3)) (1 - sqrt(3)) - 1
Or (much prettier),
sqrt(3) [ d+1 d+1 ]
c1(d) = ------- [ (1 + sqrt(3)) + (1 - sqrt(3)) ] - 1
6 [ ]
sqrt(3) [ d+2 d+2 ]
c2(d) = ------- [ (1 + sqrt(3)) + (1 - sqrt(3)) ] - 1
12 [ ]
- Gilbert
|
| 4. Patriot
The following set of 11 recurrence relations yields a solution for
the patriot mutant. P(n) is the number of moves required to move
n disks from one peg to another, and p(1)=q(1)=...=z(1)=1.
For large n, p(n) seems to grow as: k * x^n, where x is a root of
2x^2 + x = 13 (for the thirteen original colonies, of course!).
The derivation of these equations is not particularly difficult,
except that the notation gets pretty gruesome.
Note that there are 4 relations which may be solved independently
of the other 7 (namely, s,w,v and z, marked with an "*"). Also,
no two of the 11 functions happen to be identical.
p(i) = 2*q(i-1) + 1
q(i) = q(i-1) + r(i-1) + 1
r(i) = s(i-1) + t(i-1) + u(i-1) + 2
* s(i) = v(i-1) + w(i-1) + 1
t(i) = s(i-1) + x(i-1) + 1
u(i) = v(i-1) + y(i-1) + 1
* v(i) = 2*s(i-1) + z(i-1) + 2
* w(i) = 2*v(i-1) + 1
x(i) = r(i-1) + u(i-1) + 1
y(i) = 2*r(i-1) + 1
* z(i) = 2*s(i-1) + 1
A small table of p(n) follows.
- Gilbert
Table of p(n), for n < 50
n p(n)
- ------------------
1 1
2 3
3 7
4 19
5 43
6 99
7 235
8 535
9 1239
10 2879
11 6619
12 15323
13 35451
14 81823
15 189263
16 437543
17 1011059
18 2337731
19 5403987
20 12491223
21 28877687
22 66755519
23 154315883
24 356738411
25 824668747
26 1906384015
27 4407016991
28 10187707927
29 23550975203
30 54442996563
31 125856166851
32 290942533447
33 672573989511
34 1554793681263
35 3594227304667
36 8308800562043
37 19207511250747
38 44402137601023
39 102644731732399
40 237284539657159
41 548532326102867
42 1268046007224291
43 2931350797033395
44 6776424099061175
45 15665106892563351
46 36213136933143071
47 83714161449950539
48 193522611430039179
49 447367571779515947
|
| For the people that haven't seen the execution of
the solution of the Tower's of Hanoi?
Here's a simple graphical program that could
show the use the results of the method of solution
I wrote the program in C for the Recursiveness.
Required DCL:
$ CC HANOI
$ LINK HANOI,SYS$LIBRARY:CRTLIB.OLD
$ HANOI == "$SYS$DISK:[]HANOI.EXE"
$ Hanoi 3
/*
* Hanoi.
*/
#include stdio.h
int top[3] = { 22, 22, 22 };
int atoi(), fprintf(), printf();
main(argc, argv)
char *argv[];
{
register int n;
if (argc == 0) {
argc = 2;
argv[0] = "hanoi";
argv[1] = "5";
}
if (argc < 2) {
fprintf(stderr, "Arg. count!\n");
exit(1);
}
n = atoi(argv[1]);
if ( n < 0 || n > 13 ) {
fprintf(stderr, "Bad number of rings!\n");
exit(1);
}
setup(n);
hanoi(n, 0, 2, 1);
}
hanoi(n, a, b, c)
{
if (n == 0)
return;
hanoi(n-1, a, c, b);
movering(n, a, b);
hanoi(n-1, c, b, a);
}
setup(n)
{
register i;
printf("\033[2J");
for ( i = 11; i < 23; ++i ) {
cput(15, i, '|');
cput(40, i, '|');
cput(65, i, '|');
}
curse(5, 23);
for ( i = 5; i < 76; ++i )
putchar('-');
for ( i = n; i > 0; --i )
draw(i, 15, top[0]--, 'x');
}
curse(x, y)
{
printf("\033[%d;%dH", y+1, x+1);
}
cput(x, y, c)
{
curse(x, y);
putchar(c);
}
draw(ring, centre, y, ch)
{
register int i;
curse(centre-ring, y);
for ( i = 0; i < ring; ++i )
putchar(ch);
curse(centre+1, y);
for ( i = 0; i < ring; ++i )
putchar(ch);
}
movering(ring, from, to)
{
int fromc, toc;
int fromy, toy;
fromc = 15 + from*25;
toc = 15 + to*25;
fromy = ++top[from];
toy = top[to]--;
while (fromy != 10) {
draw(ring, fromc, fromy, ' ');
draw(ring, fromc, --fromy, 'x');
}
if (fromc < toc)
while (fromc != toc) {
cput(fromc-ring, fromy, ' ');
cput(fromc, fromy, 'x');
cput(fromc+1, fromy, ' ');
cput(fromc+ring+1, fromy, 'x');
++fromc;
}
else if (fromc > toc)
while (fromc != toc) {
cput(fromc+ring, fromy, ' ');
cput(fromc, fromy, 'x');
--fromc;
}
while (fromy != toy) {
draw(ring, fromc, fromy, ' ');
draw(ring, fromc, ++fromy, 'x');
}
}
Have fun with it.....
Al Meier
|
| For the patriot mutant, moving a stack of n disks requires p(n) moves,
n n n n n
p(n) = a0 r0 + a1 r1 + a2 r2 + a3 r3 + a4 r4 +
n n n n
+ a5 r5 + a6 r6 + a7 r7 + a8 r8 + a9,
4 2
Where r0 through r3 are roots of r - 2 r - 6 r - 4 = 0,
r0 = 2.31170698134063,
r1 = -0.81444031337008,
r2 = -0.74863333398527 + 1.25064102146243 * i,
r3 = -0.74863333398527 - 1.25064102146243 * i,
5 2
And r4 through r8 are roots of r - 3 r - 2 = 0,
r4 = 1.56303765441336,
r5 = 0.06210288664806 + 0.79369475055732 * i,
r6 = 0.06210288664806 - 0.79369475055732 * i,
r7 = -0.84362171385475 + 1.14330501709387 * i,
r8 = -0.84362171385475 - 1.14330501709387 * i,
And the coefficients a0 through a9 are
a0 = 0.65759432442712,
a1 = 0.04589563937290,
a2 = 0.06245317948915 - 0.05876363440754 * i,
a3 = 0.06245317948915 + 0.05876363440754 * i,
a4 = 0.04412890243680,
a5 = 0.05973351224700 - 0.05356885709716 * i,
a6 = 0.05973351224700 + 0.05356885709716 * i,
a7 = -0.13235976121822 + 0.08472845082312 * i,
a8 = -0.13235976121822 - 0.08472845082312 * i,
a9 = -0.72727272727272.
Unfortunately, I see no obvious structure of a0 through a8.
- Gilbert
|