Algorithms and Data Structures Execrcice 4

(1) Wirite recurrence formulas for the following sequences.

a factorial of n f(n) = n!
a geometrical progression, in which the first term is 1 and the quotient is 2 f(n) = 2⁰ + 2¹ + 2² + ... + 2ⁿ
a Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, ... (n)
a polynomial of degree n f(x,n) = a₀ xⁿ + a₁ x^n-1 + ... a_n-1 x + a_n [Use Horner method]

(2) Consider the following function rule() below which uses a function mark(). mark() draws a line to the rule. For example, mark( 13, 3 ) draws a line of height 3 in the position 13. Illustrate in sequential order how the linse are drawn, when rule( 4, 12, 3) is executed.

void rule(int left, int right, int height){
  int middle = (left+right)/2;
  if( height>0 ){
    mark(middle, height);
    rule(middle, right, height-1);
    rule(left, middle, height-1);
  }
}

The following equation is an example of recurrence formula for an arithmetic sequeence with the first term equal to 1 and with the difference equal to 1 f(n) = n + (n-1) + ... + 2 + 1
f(n)=n+f(n-1),f(0)=0

The Horner method is a method of expanding the higher order polynomial in the form of (ax + b). For example,

f(x) = 1x⁴ + 2x³ + 3x² + 4x
      + 5

is expanded by the Horner method as follows

Question 2

Write the C-functions which perfrom the calculations specified below using recurseve calls:

factorial
geometrical progression
Fibonacci sequence
polynomial of degree 4 f(x) = 1x⁴ + 2x³ + 3x² + 4x + 5
（use the Horner method）

Call these functions in main() and calculate the following:

10!
the geometrical progression which has the first term "1" and the quotient "2", from the 1st term to 10th term
the 20th term of Fibonacci sequence
the value of the following polynomial (of degree 4) for x = 2, f(x) = 1x⁴ + 2x³ + 3x² + 4x + 5

Example of executing a program:
% ./a.out
10! = 3628800
2^0 + 2^1 + 2^2 + ... + 2^9 + 2^10 = 2047
fibonacci 20: 6765
f(2) = 57.00

You may declare the coefficients a_n which are used by the Horner method as global array, since it is easy.

A function star() draws imege in this program. Edit this function. A function line() which used in star() draws lines. For example, line(1,2,3,4) draws line from position (1,2) to position (3,4).

Algorithms and Data Structures Execrcise 4 Recursion

Algorithms and Data Structures
Execrcise 4
Recursion