SICP - Solution: Exercise 1.14 #39

MartinMihalev · 2024-10-31T18:12:44Z

First I want to say thank you for the detailed explanation of the exercise that really helped me to wrap my head around the problem. I found though a little issue with the formula $$T(n,2) = \frac{n^2-3n}5+1$$. When n=12 it results in 22.6 which is more than twice as less the correct answer 49(as seen on the image). Although math is not of my strengths I suspected that starting the summation with index of zero is somehow wrong and I ended up with the following formula:

$$T(n,2) = Ceil\left(\frac n5\right)+1+\sum_{i=1}^{Ceil(n/5)}T(n-5(i-1),2)$$

From this formula I derive two, because of the ceiling. When the amount is divisible by 5 without reminder:

$$T(n,2) = \left(\frac n5\right)+1+\sum_{i=1}^{n/5}T(n-5(i-1),2)$$ $$T(n,2) = \frac{n^2+7n}5+1$$

With reminder:

$$T(n,2) = \left(\frac n5+1\right)+1+\sum_{i=1}^{(n/5)+1}T(n-5(i-1),2)$$ $$T(n,2) = \frac{n^2+7n}5+3$$

The latter one gives as result 48,6 $$\approx$$ 49 when the amount is 12. The former one gives correctly 35 when the amount is 10. I hope that is helpful. Thank you again for sharing this valuable knowledge.

ghost · 2024-11-08T07:48:34Z

I found a different issue but it's related to the same exercises.

When calculating the number of calls of the cc function for kind of coins = 2, or T(n,2), I would expect the number of green nodes to be ceil of (n/5), rather than floor.
Am I correct or am I missing something?

MartinMihalev · 2024-11-08T20:30:47Z

I found a different issue but it's related to the same exercises.

When calculating the number of calls of the cc function for kind of coins = 2, or T(n,2), I would expect the number of green nodes to be ceil of (n/5), rather than floor. Am I correct or am I missing something?

I think you are correct.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

SICP - Solution: Exercise 1.14 #39

SICP - Solution: Exercise 1.14 #39

Uh oh!

Uh oh!

SICP - Solution: Exercise 1.14 #39

SICP - Solution: Exercise 1.14 #39

Comments

Uh oh!

Uh oh!