CODEWITHSUNDEEP
recursionrecurrence
raphytaffy
raphytaffy

Reputation: 1

Towers of Providence problem

The Towers of Providence is a variation of the classical Towers of Hanoi problem. There are four pegs, denoted A, B, C, and D, and N disks of different sizes. Originally, all the disks are on peg A, stacked in decreasing size from bottom to top. Our goal is to transfer all the disks to peg D, and the rules are that we can only move one disk at a time, and no disk can be moved onto a smaller one. We can solve this problem with a recursive method: If N = 1, move this disk directly to peg D, and we are done. Otherwise (N > 1), perform the following steps:

(a) transfer the top N-2 disks on peg A to peg B applying the method recursively;
(b) move the second largest disk from peg A to peg C;
(c) move the largest disk from peg A to peg D;
(d) move the second largest disk from peg C to peg D;
(e) fill in this step

Upvotes: 0

Views: 1091

Answers (1)

lily
lily

Reputation: 2998

Step e: Transfer N-2 pegs from B to D by applying the method recursively.

Upvotes: 1

Related Questions