Mélanger et inverser un tableau

Extrait de la fiche de révision

Plan du Cours

  1. Échange de deux cases
  2. Mélange de Fisher–Yates
  3. Inversion d’un préfixe
  4. Copie et partage de tableaux

1. Échange de deux cases

Points essentiels

  • Pour échanger tab[i] et tab[j] sans perdre leur valeur, on copie d’abord tab[i] dans une variable temporaire, on affecte tab[j] à tab[i], puis on affecte la variable temporaire à tab[j].

Astuce mémo

Sauver, remplacer, restituer : temporaire → première case → seconde case.

2. Mélange de Fisher–Yates

★ À maîtriser

  • Dans le mélange moderne de Fisher–Yates, aussi appelé mélange de Durstenfeld, on part de i = tableau.length - 1, on tire uniformément j entre 0 et i inclus, on échange les cases i et j, puis on recommence avec i - 1 jusqu’à i = 1.

📌 L’expression (int)(Math.random() * i) produit un indice de 0 à i - 1, tandis que Fisher–Yates exige un indice de 0 à i inclus ; elle ne permet donc pas de tirer la case i.

  • Pour un tableau de taille n ≥ 1, Fisher–Yates effectue exactement n−1n - 1 tirages et échanges, avec un temps Θ(n) et une mémoire auxiliaire Θ(1).

Compléments

  • Dans Java, nextInt(i + 1) renvoie un entier compris entre 0 inclus et i + 1 exclu, soit un indice de 0 à i inclus.

  • Le mélange d’un tableau vide ne demande aucun échange.

Astuce mémo

Dernière case → tirage jusqu’à i inclus → échange → reculer jusqu’à 1.

Lire la fiche complète →

Aperçu du QCM

1. Dans un tableau, `tab[i]` vaut 12 et `tab[j]` vaut 5. Quelle suite d’affectations échange ces valeurs sans en perdre une ?

2. Un tableau contient 6 éléments. Lors d’une étape de Fisher–Yates, quelle opération faut-il effectuer lorsque l’indice actif vaut i = 4 ?

3. Dans une étape de mélange, l’indice actif vaut i = 5 et le programme calcule j avec `(int)(Math.random() * i)`. Quelle conséquence cette expression a-t-elle sur l’échange ?

Faire le QCM (7 questions) →

Aperçu des flashcards

Quelle valeur faut-il copier dans une variable temporaire pour échanger tab[i] et tab[j] ?

La valeur de tab[i].

Après avoir affecté tab[j] à tab[i], que faut-il affecter à tab[j] ?

La variable temporaire.

Comment choisit-on l’indice d’échange à l’étape i du mélange moderne de Fisher–Yates ?

Uniformément entre 0 et i, bornes incluses.

Quelle est la borne supérieure exclue de nextInt(i + 1) en Java ?

i + 1.

Quelle est la première étape pour échanger tab[i] et tab[j] sans perdre leur valeur ?

Copier tab[i] dans une variable temporaire.

Après la copie temporaire, quelle affectation effectue l’échange de tab[i] et tab[j] ?

Affecter tab[j] à tab[i], puis la variable temporaire à tab[j].

Voir toutes les 10 flashcards →

Questions fréquentes

Que contient la fiche de révision sur Mélanger et inverser un tableau ?

La fiche de révision couvre les notions essentielles de Mélanger et inverser un tableau. Elle est structurée par thématiques pour faciliter l'apprentissage et la mémorisation, avec des définitions clés, des explications et des synthèses.

Lire la fiche complète →

Combien de questions contient le QCM sur Mélanger et inverser un tableau ?

Le QCM contient 7 questions à choix multiples avec corrections détaillées et explications pour chaque réponse. Idéal pour tester tes connaissances et identifier tes lacunes.

Faire le QCM (7 questions) →

Comment réviser Mélanger et inverser un tableau avec les flashcards ?

Revizly propose 10 flashcards interactives sur Mélanger et inverser un tableau. Chaque carte présente une question au recto et la réponse au verso, permettant une révision active et efficace basée sur la répétition espacée.

Voir toutes les 10 flashcards →

Cours similaires

À redécouvrir en Informatique

Crée tes propres fiches depuis tes cours

Importe ton PDF ou colle ton cours, l'IA génère fiches, QCM et flashcards en 30 secondes.