Towers of Hanoi: Difference between revisions
Content added Content deleted
({{out}}) |
(jq) |
||
Line 1,240: | Line 1,240: | ||
Using it (5 is the number of disks.) |
Using it (5 is the number of disks.) |
||
<lang joy>[source destination temp] 5 hanoi.</lang> |
<lang joy>[source destination temp] 5 hanoi.</lang> |
||
=={{header|jq}}== |
|||
{{works with|jq|1.4}} |
|||
The algorithm used here is used elsewhere on this page but it is worthwhile pointing out that it can also be read as a proof that: |
|||
(a) move(n;"A";"B";"C") will logically succeed for n>=0; and |
|||
(b) move(n;"A";"B";"C") will generate the sequence of moves, assuming sufficient computing resources. |
|||
The proof of (a) is by induction: |
|||
* As explained in the comments, the algorithm establishes that move(n;x;y;z) is possible for all n>=0 and distinct x,y,z if move(n-1;x;y;z)) is possible; |
|||
* Since move(0;x;y;z) evidently succeeds, (a) is established by induction. |
|||
The truth of (b) follows from the fact that the algorithm emits an instruction of what to do when moving a single disk. |
|||
<lang jq># n is the number of disks to move from From to To |
|||
def move(n; From; To; Via): |
|||
if n > 0 then |
|||
# move all but the largest at From to Via (according to the rules): |
|||
move(n-1; From; Via; To), |
|||
# ... so the largest disk at From is now free to move to its final destination: |
|||
"Move disk from \(From) to \(To)", |
|||
# Move the remaining disks at Via to To: |
|||
move(n-1; Via; To; From) |
|||
else empty |
|||
end;</lang> |
|||
'''Example''': |
|||
move(5; "A"; "B"; "C") |
|||
=={{header|K}}== |
=={{header|K}}== |