Question:
What is the recurrence relation for the Tower of Hanoi puzzle with \(n\) disks, and what is its minimum move solution?
\(n\) डिस्कों के साथ टावर ऑफ हनोई पहेली के लिए पुनरावृत्ति संबंध और न्यूनतम चालों का समाधान क्या है?
Options:
- \(T(n) = 2T(n-1) + 1\) with solution \(2^n – 1\)
- \(T(n) = T(n-1) + n\) with solution \(n(n+1)/2\)
- \(T(n) = 2T(n-1) + n\) with solution \(2^{n+1} – n\)
- \(T(n) = 3T(n-1) + 1\) with solution \(3^n – 1\)
- \(T(n) = 2T(n-1) + 1\), समाधान: \(2^n – 1\)
- \(T(n) = T(n-1) + n\), समाधान: \(n(n+1)/2\)
- \(T(n) = 2T(n-1) + n\), समाधान: \(2^{n+1} – n\)
- \(T(n) = 3T(n-1) + 1\), समाधान: \(3^n – 1\)
Correct Answer: a)
Explanation:
To move \(n\) disks: move top \(n-1\) disks to auxiliary peg (\(T(n-1)\)), move largest disk to target (1 move), then move \(n-1\) disks onto target (\(T(n-1)\)). Thus \(T(n) = 2T(n-1) + 1\), which expands to \(2^n – 1\).
टावर ऑफ हनोई में \(n\) डिस्कों को स्थानांतरित करने के लिए \(T(n) = 2T(n-1) + 1\) संबंध बनता है, जिसका कुल मान \(2^n – 1\) चालें होता है।