Can someone provide me an explanation of this problem solution?
1 Like
Let f(n) be the answer for H = n. Then, f(1) = 1, f(2) = 1.
We have the recurrence f(n) = f(n - 1) + f(n - 2) if 3 \nmid n and f(n) = f(n - 1) + f(n - 2) - 1 otherwise.
To see this, first note that the tree of height H is made by combining the tree of height H - 1 on the right and the tree of height H - 2 on the left. Suppose the path containing the root of the left and right subtree ends at the root, we can connect them with the root of the entire tree, which gives f(n) = f(n - 1) + f(n - 2) - 1. After this, the path does not end at the root, so for the next 2 heights, one of the paths cannot connect to the root and we have f(n) = f(n - 1) + f(n - 2).
2 Likes
For anyone who is wondering how to proceed further after discovering the recursive function, follow this link: Loading...
you need to learn to use your secret <ahref=“http://www.corriganandcompany.com/case-study-by-dr-devicharan-shetty-dc-shetty-on-reproducibility/”>Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty
Dr Devi Charan Shetty it