MESSAGE
| DATE | 2015-02-27 |
| FROM | prmarino1@gmail.com
|
| SUBJECT | Re: [NYLXS - HANGOUT] Read the FUCKING NOTES
|
Umm correct me if I'm wrong but 2 to the power of one is 2 so to simplify the first equation 2-1=1. So n=1 is a really bad example.
Beyond that off the top of my head it looks like you may be dealing with RAID stripe, and stride equations. In that case I think you are over thinking the problem.
Sent from my BlackBerry 10 smartphone.
Original Message
From: Ruben Safir
Sent: Friday, February 27, 2015 16:31
To: learn-at-nylxs.com; hangout
Reply To: hangout-at-nylxs.com
Subject: [NYLXS - HANGOUT] Read the FUCKING NOTES
The minimum number of moves required to solve the Towers of Hanoi puzzle
with n disks is ***2^n − 1***.
Proof is by mathematical induction:
Basis: n = 1. Number of moves required is 2^1 − 1 = 1.
Inductive step: Assume result true for n disks. Suppose now n + 1 disks are
given. In order to move the largest disk from its initial location at
the bottom
of pile 1 to the final location at the bottom of pile 3, we clearly need
to first
have moved all other disks to pile 2, which by inductive hypothesis
requires at
least 2^n − 1 moves. Then one move is required to move the largest disk from
pile 1 to pile 3. Finally at least 2n − 1 moves are required to move the
remaining
disks from pile 2 to pile 3. So the total number of moves required is at
least
(2^n − 1) + 1 + (2^n − 1) = ***2^(n+1) − 1***.
What don't i understand hear
|
|
