1. Fibonacci numbers (see lab 2)
A really inefficient way of computing Fibonacci numbers is by using
the recurrence directly as given: F0 = 0,
F1 = 1, Fn = Fn-1 + Fn-2.
Find a formula for the number of calls needed to compute Fn. What is the relation to the actual Fibonacci numbers? Confirm by writing a program that also prints something in the function.
2. Golden ratio
The ratio between two consecutive Fibonacci numbers rn = Fn+1/Fn converges to a number called the golden ratio.
Write a function that computes this limit, stopping when the difference between two successive approximations is lower than 1e-6. How many approximations of the ratio are computed for this precision? Avoid wasteful recomputations of Fibonacci numbers, and the same approach to write a recursive function that computes Fn efficiently.
3. Taylor series Write functions that compute the Taylor series of cos and sin for a given value of x. Stop when the current term becomes smaller than a given value (e.g. 1e-6).
4. Fractals (optional) Adapt the program written in class to draw another fractal of your choice (Koch snowflake, Sierpiński carpet, Sierpiński triangle, dragon curve, Pythagoras tree, etc.)
Marius Minea Last modified: Fri Oct 6 17:00:00 EEST 2017