Cha chapter 4

The algorithms
recurring

Acquire problem-solving skills

through the learning of numerical algorithms.

Propose solutions to some recurring problems.

I- Introduction
II- Calculation of sum
III- Recurrent algorithm on chains
IV- Pascal's triangle
V- The Fibonacci sequence
VI- The golden ratio
Let's remember
Exercises
Lecture

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark.
 Chapter

4
The recursive algorithms

I. Introduction

An algorithm or process is said to be recursive if it uses an iterative procedure or

recursive to generate a result that may depend on p previous results, we
Let's talk about an algorithm or a recurrent processing of order p.

Order 1: A first-order recurrent algorithm is an algorithm that produces a result

dependent on the previous result.

Order 2: A second-order recursive algorithm is an algorithm that produces a result

dependent on the two previous results.

Order 3: A third-order recursive algorithm is an algorithm that produces a result

dependent on the three previous results.

Order p: A recurrent algorithm of order p is an algorithm that produces a result

dependent on the previous results.

II. Calculation of sum

Activity 1

We want to calculate the sum of the elements of a square matrix

of integers of order n (4 in 20).
Questions :
1- Determine if this treatment is recurring. If so, provide its
order.
2- Propose an analysis, then deduce the algorithm of the function
named SOMME_MAT, which calculates the sum of the elements of the
square matrix.

1- The calculation of the sum of the elements of a matrix requires initialization to zero of
the variable S containing the sum; we add to it the first element of the
matrix, ( S← S + M[1, 1]), we obtain a second result S to which we add
the second element of the matrix (S← S + M[1, 2]) and so on. It is the accumulation of
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 124
 all the elements of the matrix in the variable S.
Since this treatment always refers to the previous element, therefore it is a
first-order recurrent treatment.

2/ Analysis of the SUM_MATRIX function

Result: SUM_MAT
Processing: To calculate the sum of the elements of the matrix M of type MAT, we
we must sum all the integers it contains:
[S← 0]
Line up from 1 to NMake
Column from 1 to NMake
S← S + M [line, column]

Algorithm of the SUM_MATRIX function

0) Start function SUM_MAT (M : MATRIX ; N : Unsigned Integer) : Integer
1) S← 0
Line up from 1 to N
For the column from 1 to N
S← S + M [line, column]
End For
End For
SUM_MAT← S
End SUM_MAT

Local objects coding table

Objects Type / Nature Role
S Whole Cumulative variable
Line Entire Matrix line counter
Column Whole Column counter of the matrix
Translation in Pascal:

FUNCTION SUM_MAT (M : MATRIX; N : Word) : Integer;

VAR S, line, column: Integer;
Start
S := 0;
For line := 1 To N Do
For columns := 1 to N do
S := S + M[row, column];
SOMME_MAT := S ;
End;
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 125
 Chapter

III. Recursive algorithm on strings

Activity 2: Thue-Morse Sequence (Sequences of character strings)

With every transformation of one string into another, we can
define recurrent sequences.
For example, if we consider the set of strings made up of 0s and 1s
(also called chains or binary words) the transformation that involves replacing all
occurrence of the character '0' by the string '01' and any occurrence of the character '1' by the
chain "10", we can define the Thue-Morse sequence starting from the string "0":

U0→ 0
U1→ 01
U2→ 0110
U3→ i
U4→ k6

Questions:
What is the recurrence order of this sequence?
2- Propose an analysis, then deduce the algorithms from the problem
allowing to calculate and display N th term of the sequence of
Thue-Morse starting from a character A"0" or"1" ) given.
3- Translate and test the solution to the problem. Save your
program under the name Thue_Morse.

The first result depends on the first value of the character ('0' or '1'), a second
the result is obtained from the previous one found, and so on. We conclude that it is
a recurrent sequence of order 1.
2) Problem analysis

a) Analysis of the main program

Résultat :Ecrire ("La suite de Thue-morse à partir de ", A, " Est ",FNThue_Morse
(N, A)
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 126
 Processing: Thue_Morse is a function called at the program level.
main in a display context. This function generates the Thue_Morse sequence to
starting from a character A.
Data: The Input procedure will have the task of reading the integer N and the character A.

b) Algorithm of the main program and coding of objects

0) Start Suite_Thue_Morse
1) Proc Capture (N, A)
2) Write ("The Thue-Morse sequence starting from ", A, " Is ", FNThue_Morse (N, A) )
3) Fin Suite_Thue_Morse

Coding table of global objects

Objects Type / Nature Role

N Unsigned integer Order of the term to be calculated
A Character 0 or 1
Thue-Morse Function Generate the Thue-Morse sequence

c) Analysis of the Thue_Morse function

Résultat :Thue_Morse
Treatment :[CH← A]
From 1 to NDo
j← 1
Repeat
SiCH[j] = "0"Alorsinsère ("1", CH, j+1)
Insert ("0", CH, j+1)
End If
L← Length (CH)
j← j + 2
Until j > L
End For

d) Algorithm of the Thue_Morse function

0) Start Function Thue_Morse (N: Unsigned Integer; A: Character): String

1) CH← A

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark.
127
 Chapter

4
Pour from 1 to N
j←1
Repeat
SiCH[j] = "0"Alorsinsère ("1", CH, j+1)
Insert ('0', CH, j+1)
End If
L← Length (CH)
j←j+2
Until j > L
End For
2) Thue_Morse← CH
3) End Thue_Morse
Local Objects Coding Table
Objects Type / Nature Role
j, i Unsigned integer Meters
CH Chain String representing the Thue-Morse sequence

L Unsigned integer Length of the chain

e) Translation in Pascal

PROGRAMSuite_Thue_Morse
USESCrt ;

VARN : Word ;
A : Char ;

PROCEDURE Input (VAR N : Word ; VAR A: Char );

Begin
Repeat
Write('Give the number of elements in the sequence: ');
readLn (N);
UntilN In [2 .. 100] ;

Repeat
Give a character 0 or 1:
readLn (A);
UntilA In ['0', '1'] ;
End;

This PDF document was edited via Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 128
 FUNCTIONThue_Morse (N: Word; A : Char ) : String ;
VARCh : String ;
i, j, L : Word ;
Begin
Ch := A ;
For i := 1 To N Do
Begin
j := 1 ;
Repeat
If Ch[j] = '0' Then Insert ('1', Ch, j+1)
Else Insert ('0', Ch, j+1);
L := Length (Ch) ;
j := j + 2;
Until > L ;
End;
Thue_Morse := Ch ;
End;

{ Programme principal }
BEGIN
Input (N, A);
WriteLn('The Thue-Morse sequence starting from ', A, ' Is ', )
Thue_Morse (N, A) ) ;
END .

IV. Pascal's Triangle

Activity 3
We want to display the first n rows of Pascal's Triangle
(2 n 100).
We remind that the principle of filling the first n lines of the
Matrix MAT representing Pascal's Triangle is as follows:
For a given line:
The first and last elements are equal to 1,
The other elements are determined by applying the following formula:
MAT [row, column] = MAT [row-1, column] + MAT [row-1, column-1]
Example:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 129
 Chapter

4
Questions:
1- Is this treatment recurrent? If so, provide its rank.
2- Propose an analysis of the problem using an iterative process.
3- Deduce the corresponding algorithms.
4- Propose an analysis of the problem using a recursive process.
5- Deduce the corresponding algorithms.

1) Example:
For n = 3, the displayed Pascal's Triangle is as follows:

Line 1 1
Line 2 1 1
Line 3 121
Columns
1 2 3
MAT[3,2]=MAT[2,2]+MAT[2,1]

For n = 5, the displayed Pascal's Triangle is as follows:

Line 1 1
Line 2 1 1
Line 3 1 2 1
Line 4 1 3 3 1
Line 5 1 4 6 4 1
Columns
1 2 3 4 5
MAT[5,4]=MAT[4,4]+MAT[4,3]

We note that the calculation of the content of cell (5,4) refers to the content of
two cells (4,4) and (4,3). It is a recurring treatment of order 2.

2) Iterative solution:
a) Analysis of the main program
Result: Display of a matrix containing the different values of Pascal's Triangle.
executed by the Display_Triangle procedure
This PDF document was edited using Icecream PDF Editor.
Upgrade to PRO version to remove the watermark. 130
 Processing: Filling the Pascal's Triangle, represented by a square matrix
of order n. It is the task of the procedure Fill_MAT.
Data: an integer N that represents the number of lines of the Triangle, we use
the procedure Enter.

b/ Algorithm of the main program and coding of objects

0) Start Pascal_Triangle
1) Proc Enter (N)
2) Proc Fill_MAT (N, MAT)
3) Proc Display_Triangle (N, MAT)
4) End Triangle_Pascal
Coding table for new types:

Type
Matrix = Array of maximum rows and maximum columns of integers

Coding table of global objects

Objects Type / Nature Role

Max Constant = 20 Maximum number of rows and columns

N Unsigned integer Number of rows in Pascal's Triangle
MAT Matrix Representing Pascal's Triangle
Allows you to enter the number of lines
Enter Procedure of the Triangle
Allows to fill the matrix representing the
Fill_MAT Procedure
Pascal's Triangle
Display_Triangle Procedure Allows displaying Pascal's Triangle

c/ Analysis of the Fill_MAT procedure

Result: Fill the matrix MAT
Treatment: We note that:
Line 1→ MAT [1,1] contains the value 1
Line 2→ MAT [2,1] and MAT [2,2] contain the value 1
Line x→
Outline from 3 to NDo
MAT [line, 1]← The first box in the line receives 1
MAT [line, line]← the last box of the line receives 1
Fill column from 2 to line -1
MAT [row, column]← MAT[line-1, column] + MAT[line-1, column-1]
End For
End For
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 131
 Chapter

4
d/ Algorithm of the Fill_MAT procedure
0) Start procedure Fill_MAT (N: Integer; VAR MAT: Matrix);
1) MAT [1,1]← 1
2) MAT [2,1]← 1
3) MAT [2,2]← 1
4) Highlight from 3 to N
MAT [line, 1]← 1
MAT [line, line]← 1
For column 2 to line -1 Do
MAT [row, column]← MAT [row-1, column] + MAT [row-1, column-1]
End for
End for
5) Fill out_MAT

Local objects coding table

Objects Type / Nature Role
line Unsigned integer Line count of the matrix
column Unsigned integer Column count of the matrix

e/ Analysis of the procedure Display_Triangle

Result: Display the matrix MAT

Treatment:
Line from 1 to N Do
Write ( ) {with line break }
Column from 1 to line Make
Write(Mat [row, column]," ") Without line return
EndFor
FinPour
f/ Algorithm of the procedure Display_Triangle

0) Procedure Display_Triangle (n : Unsigned Integer ; matrix)

1) Draw from 1 to N Do
Write()
For column 1 to line To do
Write(Mat [row, column], " ")
FinPour
FinPour
2) End Display_Triangle
This PDF document was edited via Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 132
 Local object coding table

Objects Type / Nature Role

line Unsigned integer Line number
column Unsigned integer Column number

Translation in Pascal

PROGRAM Triangle_Pascal ;
USESCrt ;
constMax = 20;

TYPEMatrix = ARRAY[1.. max, 1.. max] Of Integer;

VARN : Word ;
MAT : Matrix ;

PROCEDURE Enter (VAR N : Word);

Begin
Repeat
Write('Nombre de lignes du triangle : ');
ReadLn(N);
Until N In [3.. max];
End

PROCEDURE Fill_MAT (N: Word; VAR MAT : Matrix);

VARline, column: Word;
Begin
MAT [1,1] := 1 ;
MAT [2,1] := 1 ;
MAT [2,2] := 1 ;
For line := 3 To N Do
Begin
MAT [line, 1] := 1;
MAT [line, line] := 1;
For column := 2 To line-1 Do
Begin

MAT [row, column] := MAT [row-1, column] + MAT

[line-1, column-1];
End;
End
End;
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 133
 Chapter

PROCEDURE Show_Triangle (N : Word; MAT : matrix);

VARline, column : Word ;
Begin
For line := 1 To N Do
Begin
WriteLn ;
For column := 1 To line Do
Write(Mat [line, column]:2,' ') ;
End;
End

{ Programme principal }
BEGIN
Enter (N);
Fill_MAT(N, MAT);
Display_Triangle (N, MAT);
END.

3/ Recursive solution:

a) Analysis of the main program

Result: Display of a matrix containing the different values of the Triangle of

Pascal, created by the procedure Display_Triangle
Processing: Filling the Pascal's Triangle, represented by a square matrix
of order N. It is the task of the Fill_Triangle procedure that calls a function
Val_Triangle allowing to determine the different values.
Data: an integer N that represents the number of lines of the Triangle, we will use
the procedure Enter.

b) Main program algorithm and coding of objects

0) Start Pascal_Triangle
1) Proc Enter (N)
2) Procedure Fill_Triangle (N, MAT)
3) Proc Display_Triangle (N, MAT)
Fin Triangle_Pascal
The coding table of new types and the coding table of objects
global ones are the same as those of the iterative solution except that the name of the
procedure Fill_TRIANGLE has become Fill_Triangle.
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 134
 c) Analysis of the Fill_Triangle procedure

Result: Filled matrix representing Pascal's Triangle relative to N lines

Processing: For each of the N lines of the matrix, a traversal of the columns.
(from the first to the one with the line number), is necessary for
determine their values using the recursive function Val_Triangle.

Algorithm of the Fill_Triangle procedure

0) Procedure Fill_Triangle (N : unsigned integer; VAR MAT : matrix)

1) Outline from 1 to n Do
For column 1 to line Do
Matrix [row, column]← FNVal_Triangle (column, line)
EndFor
FinPour
2) End Fill_Triangle

Table of coding for local objects

Objects Type / Nature Role
line Unsigned integer Line number
column Unsigned integer Column number
Val_Triangle Function Allows to determine the values of the Triangle.

d) Analysis of the function Val_Triangle

Result: Val_Triangle
Processing: Determine a value of the Triangle according to the line (x) and the column (y)
data as parameters.
For the first column, the value is equal to 1,
If the row number is equal to the column number, the value is also equal to 1,
otherwise the found value is equal to (the found value at the intersection of column x and
from line y-1) + (the value found at the intersection of column x-1 and
line y-1)
If (x = 1) OR (y = x) Then Val_Triangle← 1
SinonVal_Triangle← FN Val_Triangle (x, y-1) + FN Val_Triangle (x - 1, y - 1)

Recursive algorithm of the Val_Triangle function

0) Function Val_Triangle (x, y : Integer) : Integer
1) If (x = 1) OR (y = x) Then Val_Triangle← 1
SinonVal_Triangle← FN Val_Triangle (x, y-1 ) + FN Val_Triangle (x - 1, y - 1)
Finsi
2) End Val_Triangle

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 135
 Chapter

4
The analyses and algorithms of the procedures Input and Display_Triangle are the
the same as those of the iterative solution.

g) Translation in Pascal of the function Val_Triangle

FUNCTION Val_Triangle (x, y : Integer) : Integer ;

Begin
If(x = 1) OR (y = x) Then Val_Triangle := 1
ElseVal_Triangle := Val_Triangle (x, y-1) + Val_Triangle (x-1, y-1) ;
End;

V. The Fibonacci sequence

Leonardo of Pisa, better known as Fibonacci, studied from the perspective
digital rabbit reproduction. The basic unit is a pair of rabbits, it
consider that a couple of young rabbits takes a season to become adults, wait a
second season of gestation, then gives birth to a pair of young rabbits each
next season. Assuming that rabbits never die, we
let's obtain the diagram below:

This PDF document was edited using Icecream PDF Editor.

Upgrade to PRO version to remove the watermark. 136
 When we put side by side the number of pairs of rabbits in each season,
we will obtain... the Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, etc.
Curiously, we notice that the ratio between a number in the sequence and its
The previous one is increasingly approaching the golden ratio, which we will discover in
the following paragraph:
21/13−≅1,615 ; 34/21−≅1,619 ; 144/89−≅ 1,617 610/377
; ≅
1,618
−
The number of rabbit pairs U in season
n n is equal to the number of rabbit pairs
adults, that is to say the total number of rabbits that there were in the previous season (n-1)
to which we add the number of pairs of young rabbits, which is equal to the number of
adult rabbit couples from the previous season, therefore the total number of couples for the
season (n-2). That is why we have: U = U + nU n-1 n-2

The Fibonacci sequence is a recurrent sequence where each element obeys the relation of
next recurrence: U = U n+ U n-1 n-2
withU = 1 1 and U 2= 1
So it is a second-order recurrent sequence.

Activity 4

For a given integer N, calculate n eme term of the Fibonacci sequence

1) Write a function FIBO_IT1, an iterative solution without an array.
2) Write a function FIBO_IT2, iterative solution using an array.
3) Write a function FIBO_REC, recursive solution.

1) Iterative solution without using an array:

Analysis of the function Fibo_IT1

Result: the n eme term of the Fibonacci sequence
Treatment:
FIBO_IT1← F
[u1 ← 1, u2← 1]
If N ≤ 2 Then F← 1
Otherwise
Pouri from 3 to NMake
F← u1 + u2
u1← u2
u2← F
End For
End If
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark.
137
 Chapter

4
Algorithm
0) Start function FIBO_IT1 (N: Integer): Integer
u1← 1, u2← 1
If N ≤ 2 Then F← 1
Otherwise
Pouri from 3 to NMake
F← u1 + u2
u1← u2
u2← F
End For
End If
2) FIBO_IT1← F
3) End FIBO_IT1

2) Iterative solution using an array:

Analysis of the function Fibo_IT2
Result: the N th term of the Fibonacci sequence
Treatment:
FIBO_IT2← F
[T[1]← 1, T[2] ← 1]
If N ≤ 2 Then F← 1
Pouri from 3 to NFaire
T[i]← T[i-1] + T[i-2]
End For
F← T[n]
End If

Algorithm
0) Start function FIBO_IT2 (N : Integer ; T : Array) : Integer
T[1]← 1, T[2]← 1
If Sin ≤ 2 Then F← 1
Otherwise
Pouri from 3 to NDo
T[i]← T[i-1] + T[i-2]
End For
F← T[n]
End If
2) FIBO_IT2← F
3) End FIBO_IT2

This PDF document was edited via Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 138
 3) Recursive solution:
Analysis of the function Fibo_Rec
Result :Fibo_Rec
Treatment: The N th The term of the Fibonacci sequence is obtained as follows:
Special case: If N ≤ 2 then FIBO_REC← 1
General case:
SinonFIBO_REC← FN FIBO_REC (N-1) + FN FIBO_REC (N-2).

Algorithm
0) Start function FIBO_REC (N : Integer) : Integer
1) If N ≤ 2 Then FIBO_REC← 1
SinonFIBO_REC← FN FIBO_REC (N-1) + FN FIBO_REC (N-2)
End Yes
2) End FIBO_REC

VI. The golden number

Activity 5

Complétez le tableau suivant par Fib (n+1) / Fib (n) et par sa valeur
approached. What do you deduce?

Approximate value of
n Fib (n) Fib (n+1) / Fib (n)
Fib (n+1) / Fib (n)
1 1 1 1
2 1 2 2
3 2 3/2 1.5
4 3 5/3 1,666
5 5 8/5 1.6
6 8 13/8 1,625
7 13 21/13 1,615
8 21
9 34
10 55
11 89
12 144
13 233

This PDF document was edited via Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark.
139
 Chapter

The sequence Fib (n+1) seem to converge towardsλ = 1 + √5

n (V) defined on N* by Vn = Fib (n) 2
called the golden number, of which an approximate value is 1.618.

Definition and value of the golden ratio

The golden ratio is the positive solution of the equation: x2 - x - 1 = 0

1 + √5
That is to say the number
2
The first 100 decimals of the golden ratio are: 1.618 033 988 749 894 848 204 586
834 365 638 117 720 309 179 805 762 862 135 448 622 705 260 462 189 024 497 072
072 041.
We observe that:
The Fibonacci sequence is a sequence of integers. Here is the beginning of this sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.
A number in the sequence is the result of the sum of its two predecessors.
(N3 = N1 + N2). Here is now why the golden ratio and the Fibonacci sequence
are closely linked:
1/0 = does not exist.
1/1= 1
2/1 = 2
3/2 = 1.5
5/3 = 1.6666...
8/5 = 1.6 Fib (n+1)
13/8= 1,625 = 1.6....
Fib (n)
21/13 = 1.61538...
34/21= 1.61904...

The golden ratio is usually designated by the letterλ (phi) of the Greek alphabet
in honor of Phidias, sculptor and architect of the Parthenon (see reading section).

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 140
 Activity 6

Let there be two sequences U and V defined by:

U1 = 1 et 2U = 2
Ui = Ui-1+ U i-2 for U 3
Vi = Ui / Ui-1 for all i 2

The sequencen V converges to a limit called the golden ratio.

We suppose that the n th Term of the sequence V is V, therefore
n one
approximated number of the golden ratio with a precision e as soon as
⏐V n - V
⏐n-1
< e.

Write a Pascal program named Nombre_Or, which looks for V to n

10 -4 close and its rank.
Practical Bac 2004

PROGRAMName_Or ;
USESCrt ;

TYPETAB_E = ARRAY[1..1000] OF Integer ;

TAB_R = ARRAY[1..100] OF Real ;

VARU: TAB_E;
V: TAB_R ;
i: Integer;

PROCEDURE Init (VAR U : TAB_E);

BEGIN
U[1] := 1;
U[2] := 2;
i := 2 ;
End;

PROCEDURE Calculate (VAR u : TAB_E; VAR V : TAB_R; VAR i : Integer);

BEGIN
Repeat
i := i+1;
U[i] := U[i-1] + U[i-2];
V[i] := U[i] / U[i-1];
Until ABS(V[i] - V[i-1]) < 0.0001 ;
END;

This PDF document was edited via Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 141
 Chapter

PROCEDURE Display (V : TAB_R ; i : Integer) ;

BEGIN
Write('Number of gold: ', V[i]);
Write('Rank: ', i);
END;

{Programme principal }
BEGIN
Init (U) ;
Calculation (U, V, i);
Display (V, i) ;
END.

Ce document PDF a été édité viaIcecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 142
 Let's remember

An algorithm or a process is said to be recursive if it

use an iterative or recursive process to generate
a result that may depend on p previous results.
A first-order recurrent algorithm is an algorithm whose
a result depends on the previous result.
A second-order recurrent algorithm is an algorithm whose
a result depends on the two previous results.
A recurrent algorithm of order 3 is an algorithm whose
a result depends on the three previous results.
A recurrent algorithm of order p is an algorithm whose
a result depends on the p previous results.

This PDF document was edited using Icecream PDF Editor.

Switch to the PRO version to remove the watermark. 143
 Exercise 1
Répondez par V (Vrai) ou F (Faux) à chacune des questions suivantes :

A recurrent treatment of order 1 refers to:

At the first element of the sequence
At the last element of the sequence
To the middle element of the sequence
A recurring treatment of order 2 refers to:
To the first two elements of the sequence
In the last two elements of the sequence
To the middle element and to the end element of the sequence

c. What does the following set of instructions do:

A :='Fi'; B :='bonacci'; FIBO :=1 ;
For i :=1 To LENGTH ( Copy (A+B,6,3) ) * 4 Do
FIBO := FIBO * (i-1) + FIBO * (i-2);
Calculate a term of the Fibonacci sequence
Calculate the sum of the first 12 terms of the Fibonacci sequence.
Calculate any sum

Exercise 2
Write a program that calculates and displays the sum of the squares of the first n
odd integers.
For example, for n = 5
The program displays:
n = 5, the series is: 1 + 23 + 52+ 7 +
2 9 =2165. 2

This PDF document was edited using Icecream PDF Editor.

Upgrade to PRO version to remove the watermark. 144
 Exercise 3

Write a program that displays an isosceles triangle made of stars with N lines (N
is provided to the keyboard):

Example for a number of lines = 8

*
***
*****
*******
*********
***********
*************
***************

Exercise 4

We define the sequence (x) nwith n∈ In the following way:

x0 = a
and
n+1 x= 4xn(1 - x).n
Write a program that calculates x based
n on given a and n.

Exercise 5: Calculation of the Heron's sequence

Write a program to calculate the first n terms of the sequence
Heron defined by:

U0 = x
Un+1 (U / 2)
n + (x / 2U) n

Where x is a positive real number.

Exercise 6

We remind you that the function Random (i: Integer) returns a random integer.
ranging from 0 to i-1. The call to RANDOMIZE allows to initialize this
function.

We provide the following program:

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 145
 PROGRAMmystery ;
UsesCrt ;
VART: array[1..20001] Of Integer;
U,S,i,n : Integer;
coincide : Boolean;

PROCEDUREX
Begin
Randomize ; {initialization of the Random function}
For i := 1 TO 20001 DO T[i] := 1 + Random(20000);
End;

{Programme principal}
BEGIN
X;
i:=1; coincide:=false;
Repeat
i := i + 1; S:=0 ;
While (S < i - 1) AND NOT (coincide) Do
Begin
S:=S+1;
If T[S]=T[i] Then coincide:=TRUE
End;
Untilcoincide=true;
U:= i ;
For n:=1 to i Do
Write (T[n] , ' ; ');
WriteLn ;
WriteLn ('U = ', U);
Writeln ('S = ', S);
Readln;
END.

1/ At the end of the program, what do the variables S and U contain?

2/ Determine the role of this program.
3/ Check your hypothesis by adding lines of code to the program if necessary.

Exercise 7: Two sequences

We define a double sequence:

U0 = 1, n+1
U (U +nV) / 2n
V0 = 2, n+1
V = √ Un+1 * nV
This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 146
 We admit that the sequences (U) and
n (V) are
n adjacent with a limit of √27/π.
Write a program that reads an integer n and displays the approximation of the number π obtained from
starting from
n V.

Exercise 8
Calculate the th
N term U of
n the Fibonacci sequence which is given by the
the following recurrence relation:
U1= 1
U2= 1
Un= Un-1 + Un-2 (for N>2)
Determine the rank N and the value U
n of the maximum term that can be calculated if
we use for U: n
the integer type
the long integer type.
Exercise 9: Vieta's Formula
Let there be two recurrent sequences u and v:

V0 = 0 Vn+1 =

Un
and U
0 =2 Un+1 =
Vn + 1
Check this assertion with a program.
Exercise 10: Sequence converging towards the square root of N
Let the sequence be defined by U0 = N/2 and
n+1U(U +nN / U) / 2,
n where N is an integer
natural
Assuming its convergence, verify that its limit is the square root of N.
- Calculate its successive terms as long as the absolute value of the difference between the two
-6 is | U
consecutive terms exceed 10, that -6
n+1 - Un| > 10
Display the number of iterations performed.

Ce document PDF a été édité viaIcecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 147
 Lecture

Leonardo Pisano

Fibonacci.
Leonardo Fibonacci (Pisa, c. 1170 - c. 1250) is a
Italian mathematician. Fibonacci (by his modern name),
known at the time as Leonardo Pisano
(Leonardo of Pisa), but also of Leonardo Bigollo
(bigollo meaning traveler), was actually called
Leonardo Guilielmi.
Biography
Born in Pisa, Italy, his education was largely completed in
North African party. His father, Guilielmo Bonacci,
managed the markets of the Republic of Pisa in Algeria, in
Tunisia and Morocco. In 1202, he brought back the figures.
Arabs and algebraic notation (which some attribute)
the introduction to Gerbert of Aurillac.
In 1202, he published Liber Abaci ('The Book of Calculations'), a treatise on calculations and the
accounting based on decimal calculation at a time when all of the West was still using the
Roman numerals and calculation on an abacus. This book is heavily influenced by his life in foreign countries.
Arabic; it is also written partly from right to left.
With this publication, Fibonacci introduced the Indian numeral system to Europe. This system
is much more powerful and faster than Roman notation, and Fibonacci is fully aware of it.
However, it struggles to assert itself for several centuries. The invention will be poorly received because the public does not
understood more the calculations that merchants were making. In 1280, Florence even prohibited
the use of Arabic numerals by bankers. It was judged that the 0 brought confusion and
difficulties to the point that they called this system cifra, which means 'secret code'.
Fibonacci is known today for a problem leading to numbers and the sequence that
as its name suggests, but in its time, it was mainly the applications of arithmetic to calculation
commercials that made it recognized: transaction profit calculation, currency conversion
from different countries. His work on number theory was ignored during his lifetime. Later, some
serious studies conducted about him led to esoteric uses, which can even be found
at the level of certain stock market methods (technical analysis). The name of Fibonacci,
corresponding to the "son of Bonacci", was posthumously attributed to him.

According to the website: [Link]

This PDF document was edited using Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 148
 A brief history of the golden ratio
His name
It is designated by the Greek letterλ ( phi ) in homage to the Greek sculptor Phidias (born around 490 and
mort around 430 BC) who decorated the Parthenon in Athens. It was Theodore Cook who introduced
this notation in 1914.

The story
10,000 years ago: First human manifestation of knowledge of the golden ratio (temple
d'Andros discovered underwater in the Bahamas.
2800 BC: The pyramid of Khufu has dimensions that highlight its importance.
what are architects attached to the golden ratio.
Vth century BC (447-432 BC): The Greek sculptor Phidias uses the golden ratio to
decorate the Parthenon in Athens, especially to sculpt the statue of Athena Parthenos. He used
is also the square root of 5 as a ratio.
IIIème century BC: Euclid mentions the division of a segment into "extreme and mean ratio"
in Book VI of the Elements.
1498: Fra Luca Pacioli, a monk professor of mathematics, writes De divina proportione ("The Divine Proportion")
divine proportion.
In the 19thth century: Adolf Zeising (1810-1876), doctor of philosophy and professor in Leipzig
then Munich, speaks of 'golden section' (der goldene Schnitt) and is interested in it not only in terms of geo-
but when it comes to aesthetics and architecture. He seeks this relationship, and finds it (one
easily find what one is looking for ...) in many classical monuments. It is he who intro-
it says the mythical and mystical side of the golden number.
th
At the beginning of the 20th
century: Matila Ghyka, Romanian diplomat, relies on the works of the phi-
German philosopher Zeising and German physicist Gustav Theodor Fechner; his works
The Aesthetics of Proportions in Nature and Arts (1927) and The Golden Ratio. Rites and Rhythms
my Pythagoreans in the development of Western civilization (1931) emphasize the pre-
eminence of the golden number and definitively establish the myth.
During the 20th th century: painters such as Dali and Picasso, as well as architects like Le
Corbusier resorted to the golden ratio.
1945: Le Corbusier patents his Modulor which provides a system of proportions between the dif-
referenced parts of the human body.

The Pyramid of Khufu The Parthenon of Athens

This PDF document was edited via Icecream PDF Editor.
Upgrade to the PRO version to remove the watermark. 149
 The Cowardly Love, Géricault

Where do we encounter the golden ratio

It seems that ...

The ratio of the height of the Pyramid of Khufu to its half base is the golden number.
It seems that this is true, beyond any esoteric consideration.
According to Herodotus, Egyptian priests said that the dimensions of the great pyramid
were
< chosen as follows: "The square built on the vertical height was exactly equal to
the area of each of the triangular faces
The Parthenon of Athens features the golden ratio everywhere.
Some have worked to find him and of course they found him! And if he had searched 2,
Would they have found it?
The Parthenon is inscribed in a golden rectangle, it is-
that is to say, the ratio of length to height
was equal to the golden number.
In the figure: DC/DE =λ.

On the roof of the temple, GF/GI = λ.

The rectangle GBFH is called the Parthenon rectangle.

According to the site: [Link]

This PDF document was edited using Icecream PDF Editor.

Upgrade to the PRO version to remove the watermark. 150