Programmation algorithmique/Maths 1

Programmation algorithmique

• Introduction
• Nombre d'opérations optimal
• Mathématiques simples
• Tableaux : parcours, recherches
• Tris de tableaux
• Structures de données
  • Listes simplement chaînées
  • Listes doublement chaînées
  • Arbres

Calcul de suites

Suite récurrente niveau 1

On veut évaluer le N-ième terme de la suite définie par :

• U₀=1
• U_n+1=3.U_n+8
• Paramètres en entrée : l'entier N
• Paramètres en sortie : l'entier U
• Spécifications : U doit être égal à U_N.
• Algorithme :

0/ début suite-1
1/ écrire ("n=")
   lire (n)
2/ U<-1 
  pour i de 1 a (n-1) faire :
  U<- 3*U+8
  fin pour
3/ fin suite-1

Suite récurrence niveau 2

On veut évaluer le N-ième terme de la suite définie par :

• U₀=1
• U_n+1=3.U_n+n+4
• Paramètres en entrée : l'entier N
• Paramètres en sortie : l'entier U
• Spécifications : U doit être égal à U_N.
• Algorithme :

u,n,i : Entier

u := 1
pour i de 0 à n - 1
   u := 3*u + i + 4
fin Pour

Suite récurrence niveau 3

On veut évaluer le N-ième terme de la suite de Fibonacci définie par :

• U₀=1
• U₁=1
• U_n+2=U_n+1+U_n
• Paramètres en entrée : l'entier N
• Paramètres en sortie : l'entier U
• Spécifications : U doit être égal à U_N.
• Algorithme :

u,v,w,n,i : entier

v := 1
w := 1
si u=0 alors 
     u := w
sinon 
     si u = 1 alors
           u := v
     sinon 
           pour i de 2 à N - 2
                u := v+w
                w := v
                v := u
          fin pour
     fin si
fin si

Suite récurrence niveau 4

On veut évaluer le N-ième terme de la suite définie par :

• U₀=1
• U₁=17
• U_n+2=(n+4)*U_n+1+2.U_n+n
• Paramètres en entrée : l'entier N
• Paramètres en sortie : l'entier U
• Spécifications : U doit être égal à U_N.
• Algorithme :

u,v,w,n,i : Entier

v := 17
w := 1

si u = 0 alors 
     u := w
sinon 
     si u := 1 alors 
           u=v
     sinon 
           pour i de 2 à N - 2
                u := (i + 4)*v + 2*w + i
                w := v
                v := u
           fin pour
     fin si
fin si

Calcul de somme

Somme des N premiers entiers

• Paramètres en entrée : l'entier N
• paramètres en sortie : l'entier S
• Spécifications : S doit être égal à la somme des N premier entiers
• Algorithme :

n,s,i : Entier

s := 0
pour i de 1 à N
     s := s + i
fin pour

Calcul polynomial

Évaluation d'un polynôme par l'algorithme de Horner

• Paramètres en entrée : Un tableau de N+1 réels TABLEAU REEL a[0..N] et un réel X.
• Paramètres en sortie : le réel P
• Spécifications : P doit être égal à $\sum _{i=0}^{N}a[i].X^{i}$
• Algorithme :

a[0..N] : tableau de réel
x, i, p : réel

p := 0
pour i de 0 à n
   p := p*x + a[n - i]
fin pour