FORMULATION OF RECURRENCE RELATION:
Before we proceed with discussing various methods of solving recurrence relation, we shall formulate some recurrence relation. The first example of formulation that we discuss is the problem of Tower of Hanoi as above.
Example: With reference to above Example, let Hn denote the number of moves required to solve the puzzle with n discs. Let us define Hn recursively.
Solution: Clearly, H1 = 1.
Consider top (n–1) discs. We can move these discs to the middle peg using
Hn–1 moves. The nth disc on the first peg can then moved to the third peg. Finally, (n–1) discs from the middle peg can be moved to the third peg with first peg as auxiliary in Hn–1 moves. Thus, total number of moves needed to move n discs are: Hn = 2Hn–1 + 1. Hence the recurrence relation for the Tower of Hanoi is:
Hn = 1 if n = 1.
Hn = 2Hn–1 + 1 otherwise.
Do'stlaringiz bilan baham: |