Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
les_programmes_a_connaitre:algorithmique_term:diviser_pour_regner_algo [2021/01/26 10:25] rd |
les_programmes_a_connaitre:algorithmique_term:diviser_pour_regner_algo [2021/01/26 11:03] (Version actuelle) rd |
||
---|---|---|---|
Ligne 3: | Ligne 3: | ||
- | Comme son nom l' | + | Cette méthode algorithmique permet de résoudre un problème. Tout d' |
+ | |||
+ | Comme son nom l' | ||
+ | * **__DIVISER :__** sépare le problème initial en multiples petits problèmes. | ||
+ | * **__RÉGNER :__** résolus les sous problèmes étant plus simples. | ||
+ | * **__COMBINER :__** assemble les solutions des sous problèmes afin d' | ||
+ | |||
+ | \\ | ||
+ | |||
+ | L' | ||
+ | |||
+ | < | ||
+ | VARIABLE | ||
+ | A : tableau d' | ||
+ | L : tableau d' | ||
+ | R : tableau d' | ||
+ | p : entier | ||
+ | q : entier | ||
+ | r : entier | ||
+ | n1 : entier | ||
+ | n2 : entier | ||
+ | |||
+ | |||
+ | DEBUT | ||
+ | |||
+ | FUSION (A, p, q, r): | ||
+ | n1 ← q - p + 1 | ||
+ | n2 ← r - q | ||
+ | créer tableau L[1..n1+1] et R[1..n2+1] | ||
+ | pour i ← 1 à n1: | ||
+ | L[i] ← A[p+i-1] | ||
+ | fin pour | ||
+ | pour j ← 1 à n2: | ||
+ | R[j] ← A[q+j] | ||
+ | fin pour | ||
+ | L[n1+1] ← ∞ | ||
+ | R[n2+1] ← ∞ | ||
+ | i ← 1 | ||
+ | j ← 1 | ||
+ | pour k ← p à r: | ||
+ | si L[i] ⩽ R[j]: | ||
+ | A[k] ← L[i] | ||
+ | i ← i + 1 | ||
+ | sinon: | ||
+ | A[k] ← R[j] | ||
+ | j ← j + 1 | ||
+ | fin si | ||
+ | fin pour | ||
+ | fin FUSION | ||
+ | |||
+ | TRI-FUSION(A, | ||
+ | si p < r: | ||
+ | q = (p + r) / 2 | ||
+ | TRI-FUSION(A, | ||
+ | TRI-FUSION(A, | ||
+ | FUSION(A, p, q, r) | ||
+ | fin si | ||
+ | fin TRI-FUSION | ||
+ | FIN | ||
+ | </ | ||