[Tutor] Mutable data type in python
Alan Gauld
alan.gauld at btinternet.com
Sun Oct 4 01:13:27 CEST 2015
On 03/10/15 23:20, C Smith wrote:
> On Sat, Oct 3, 2015 at 11:55 AM, Alan Gauld <alan.gauld at btinternet.com> wrote:
>> On 03/10/15 19:10, C Smith wrote:
>>>> Here is my modified version which I think works as you want:
>>>>
>>>> def findMinDepthPath(n):
>>>> if n <= 0: raise ValueError
>>>> elif n==1:
>>>> return 0
>>>> elif n==2 or n==3:
>>>> return 1
>>>> else:
>>>> d1 = findMinDepthPath(n-1)+1
>>>> d2 = d3 = (d1+1) # initialize to higher than d1
>>>>
>>>> if n%3 == 0:
>>>> d3 = findMinDepthPath(n/3)+1
>>>> if n%2 == 0:
>>>> d2 = findMinDepthPath(n/2)+1
>>>>
>>>> return min(d1,d2,d3)
> What I meant was that the algorithm assumes that the lowest value from
> one "action" (minus one, divide by 2, divide by 3) is the best
> possible branch in the tree. That seems intuitively correct, but is it
> necessarily so?
I see. The answer is I don't know mathematically speaking.
But I figured that the minimum path for (n-1|n/2|n/3) plus 1
must be the minimum path for n. But that was an entirely
inuitive assumption.
Also because the minimum path is being figured from the
bottom to the top - ie it finds the minimum path for 1..3
first, then for 4 via n/2 then 5 via n-1 and so on. It *feels* like
that it should always select the minimum path. But I have learnt
that in math intuitive is not always right :-)
So if anyone can mathematically prove my hunch right
or wrong that would be interesting...
--
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos
More information about the Tutor
mailing list