MESSAGE
| DATE | 2015-02-27 |
| FROM | Ruben Safir
|
| SUBJECT | Subject: [LIU Comp Sci] Read the FUCKING NOTES
|
From owner-learn-outgoing-at-mrbrklyn.com Fri Feb 27 16:31:15 2015
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix)
id 330101612F0; Fri, 27 Feb 2015 16:31:15 -0500 (EST)
Delivered-To: learn-outgoing-at-mrbrklyn.com
Received: by mrbrklyn.com (Postfix, from userid 28)
id 1E44D1612F7; Fri, 27 Feb 2015 16:31:14 -0500 (EST)
Delivered-To: learn-at-nylxs.com
Received: from mailbackend.panix.com (mailbackend.panix.com [166.84.1.89])
by mrbrklyn.com (Postfix) with ESMTP id 2D7351612E6;
Fri, 27 Feb 2015 16:31:13 -0500 (EST)
Received: from [10.0.0.19] (unknown [96.57.23.82])
by mailbackend.panix.com (Postfix) with ESMTPSA id 4AF5010534;
Fri, 27 Feb 2015 16:31:13 -0500 (EST)
Message-ID: <54F0E220.5010209-at-panix.com>
Date: Fri, 27 Feb 2015 16:31:12 -0500
From: Ruben Safir
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: learn-at-nylxs.com, hangout
Subject: [LIU Comp Sci] Read the FUCKING NOTES
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 8bit
Sender: owner-learn-at-mrbrklyn.com
Precedence: bulk
Reply-To: learn-at-mrbrklyn.com
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
|
|
