Programmation Algorithmique/Maths 1

Un livre de Wikibooks.

Algorithmique

Sommaire

Accueil Introduction Nombre d'opérations optimal Les tableaux (sauf tris) Mathématiques simples Les tris Les structures de données Listes simplement chaînées Listes doublement chaînées Arbres

Modifier ce modèle

Sections 1 Calcul de suites 1.1 Suite récurrente niveau 1 1.2 Suite récurrence niveau 2 1.3 Suite récurrence niveau 3 1.4 Suite récurrence niveau 4 2 Calcul de somme 2.1 Somme des N premiers entiers 3 Calcul polynomial 3.1 Evaluation d'un polynôme par l'algorithme de Horner

[modifier] Calcul de suites

[modifier] 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 :

u,n,i : Entier

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

[modifier] 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

[modifier] 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

[modifier] 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

[modifier] Calcul de somme

[modifier] 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

[modifier] Calcul polynomial

[modifier] Evaluation 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 à
• 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