tag:blogger.com,1999:blog-6314876008291942531.post3608638575106615668..comments2024-01-14T00:36:43.430-08:00Comments on Antonio Gulli's coding playground: A children can hop either 1, 2, or 3 steps in a stairway of N steps.Unknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-6314876008291942531.post-43321697927052481582013-01-01T02:54:34.863-08:002013-01-01T02:54:34.863-08:00Why such a complex code? We can see overlapped sub...Why such a complex code? We can see overlapped sub problems solving again and again and they are combined for end result. Here is simple smart code (linear in time and constant space),<br /><br />int ChildHop(int N) {<br /> int A[] = {1, 2, 4};<br /> if( N <= 3 )<br /> return A[N-1];<br /><br /> int x = 0, y = 1, next = 2;<br /> int prev_next;<br /> for(int i = 0; i < N-3; i++) {<br /> prev_next = next;<br /> next = (next+1)%3;<br /> A[next] = A[prev_next] + A[x] + A[y];<br /> x = y;<br /> y = prev_next;<br /> }<br /><br /> return A[next];<br />}<br /><br />Use template with BigInteger typename to solve larger size stairs.<br /><br />These days I am using Bing also along with Google. Surprise, when I search my name in Bing, I saw link of this page in results :)<br /><br />@Antonio, I have two questions.<br /><br />1. It would be helpful to get email alerts on comments.<br /><br />2. Blogspot is pathetic to type and submit. It won't even accept HTML tags. Why not move to some good CMS frameworks such as Joomla, WordPress, etc... ?Anonymoushttps://www.blogger.com/profile/09855100606552890649noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-78001524028323393292012-02-13T14:18:23.965-08:002012-02-13T14:18:23.965-08:00This blog is so much better than watching TV :)
S...This blog is so much better than watching TV :)<br /><br />So this is I think best to solve with a tree algorithm as Venkata suggested earlier. An initial naive solution might be to use a simple breadth first search like:<br /><br /> static Stack<long> nodes = new Stack<long>();<br /> static long Combinations( int n )<br /> {<br /> long leafs = 0;<br /> nodes.Push(n);<br /> while (nodes.Count > 0)<br /> {<br /> var x = nodes.Pop();<br /><br /> // Leaf, just count<br /> if (x <= 0) leafs++;<br /> else<br /> {<br /> // Only push down options where the child can actually complete<br /> // the stair jump on a complete jump (i.e. not taking last 1 step in a 3step jump)<br /> if (x - 1 >= 0) nodes.Push(x - 1);<br /> if (x - 2 >= 0) nodes.Push(x - 2);<br /> if (x - 3 >= 0) nodes.Push(x - 3);<br /> }<br /> }<br /> return leafs;<br /> }<br /><br /><br />But it is soon obvious that for non-trivial N then this naive BFS is simply too slow. <br /><br />However when looking at the ternary-tree it becomes obvious that it is simply a repeating pattern of the same subtrees. So enhancing this algorithm to be recursive and having a simple caching map for previously calculated subtrees drastically improves performance. Like so:<br /><br />static Dictionary<int, BigInteger> map = new Dictionary<int, BigInteger>();<br /> static BigInteger Combinations2(int n)<br /> {<br /> // Wooha, at a leaf<br /> if (n <= 0) return 1;<br /><br /> BigInteger leafs = 0;<br /> if (map.TryGetValue(n, out leafs))<br /> return leafs;<br /><br /> // We need to calculate it if not found<br /> if (n - 1 >= 0)<br /> leafs += Combinations2(n - 1);<br /> if (n - 2 >= 0)<br /> leafs += Combinations2(n - 2);<br /> if (n - 3 >= 0)<br /> leafs += Combinations2(n - 3);<br /><br /> map[n] = leafs;<br /> return leafs;<br /> }<br /><br />At least Combinations2 is a little bit more intelligent than before :)Sverrir Sigmundarsonhttps://www.blogger.com/profile/01793802096339611603noreply@blogger.comtag:blogger.com,1999:blog-6314876008291942531.post-20335297952368385222011-12-31T03:26:56.273-08:002011-12-31T03:26:56.273-08:00Isn't a recursive function? I am thinking the ...Isn't a recursive function? I am thinking the solution as a tree, the number of leaf nodes is our target. Mathematically,<br /><br />F(N) = 1 if N = 1<br /> = 2 if N = 2<br /> = 4 if N = 3<br /> = F(N-1) + F(N-2) + F(N-3) if N > 3<br /><br />Any comments?Anonymoushttps://www.blogger.com/profile/09855100606552890649noreply@blogger.com