SDD Question 1 Juin 2007

1)
Entrée: Un tableau A contenant des entiers.
Sortie: /
Effet : Place les entiers pairs au début du tableau.
algo_rec(A):
    alog_rec_in(A, 0, 0)

Entrée: Un tableau A contenant des entiers.
        L'entier i qui est l'indice de l'élément courant.
        L'entier j qui est l'indice de l'endroit ou placer le prochain nombre pair.
Sortie: /
Effet : Place les entiers pairs au début du tableau.
algo_rec_in(A, i, j):
    si i <= n:
        si A[i] est pair:
            tmp <- A[j]
            A[j] <- A[i]
            A[i] <- tmp
            algo_rec_in(A, i+1, j+1)
        sinon:
            algo_rec_in(A, i+1, j)

2) /

3)
Cas de base: i = n+1: alors T(n) = O(1)
Cas général: T(n) = O(1) + T(n-1)

Par une proposition vue au cours, T(n) = O(n^(0+1)) = O(n)

4)

algo_ite(A):
    j <- 0
    pour i allant de 1 à n:
        si A[i] est pair:
            tmp <- A[j]
            A[j] <- A[i]
            A[i] <- tmp
            j = j+1