On 03/10/15 23:20, C Smith wrote:
On Sat, Oct 3, 2015 at 11:55 AM, Alan Gauld <alan.ga...@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
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
