Vidéo 29 : Triangles de Floyd

\(\newcommand{\ds}{\displaystyle}\) \(\newcommand{\Frac}{\ds\frac}\) \(\renewcommand{\r}{\mathbb{ R}}\) \(\newcommand{\C}{\mathbb{ C}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\z}{\mathbb{ Z}}\) \(\newcommand{\Q}{\mathbb{ Q}}\) \(\newcommand{\N}{\mathbb{ N}}\) \(\newcommand{\n}{\mathbb{ N}}\) \(\newcommand{\ol}{\overline}\) \(\newcommand{\abs}[1]{\left| \,{#1} \right|}\) \(\newcommand{\pv}{\;;\;}\) \(\newcommand{\ens}[1]{\left\{ {#1} \right\}}\) \(\newcommand{\mens}[1]{\setminus\left\{ {#1} \right\}}\) \(\newcommand{\Par}[1]{\left({#1}\right)}\)

Vidéo 29 : Triangles de Floyd

Triangle de Floyd

  1. Le triangle suivant est un triangle de Floyd à 5 lignes :

    1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

    Le triangle de Floyd à \(n\) lignes est obtenu en plaçant sur \(n\) lignes successives, dans l’ordre croissant, les entiers consécutifs à partir de 1, la ligne numéro \(k\) comportant exactement \(k\) entiers. Ecrire un code qui, à partir d’un nombre de lignes \(n >0\), affiche le triangle de Floyd à \(n\) lignes. Par exemple, le code exécuté pour \(\mathtt{n=5}\) affichera le triangle ci-dessus.

  2. Ecrire un code qui à partir d’un entier \(\mathtt{N}\), construit une liste à deux éléments qui sont le numéro de ligne et le numéro de colonne dans le triangle de Floyd de la position où se trouve l’entier \(\mathtt{N}\). Par exemple, si \(\mathtt{N=13}\), la liste cherchée est [5, 3] car 13 se trouve à la 5ème ligne et en 3ème position dans sa ligne. De même, si \(\mathtt{N=4}\), la liste cherchée est [3, 1].

Triangle de Floyd vertical

On donne un entier \(n\geq 1\) et on demande de générer un motif dépendant de \(n\). A titre d’illustration, si \(n=9\) le motif est le suivant

1
2 10
3 11 18
4 12 19 25
5 13 20 26 31
6 14 21 27 32 36
7 15 22 28 33 37 40
8 16 23 29 34 38 41 43
9 17 24 30 35 39 42 44 45

Le motif est un triangle formé de \(n\) lignes et de \(n\) colonnes et composé d’entiers consécutifs à partir de 1 et disposés en colonnes de la manière suivante :

  • on lit les \(n\) premiers entiers à partir de 1 dans la première colonne,
  • on lit les \(n-1\) entiers suivants dans la 2e colonne à partir de la 2e ligne,
  • et ainsi de suite jusqu’à la dernière colonne qui ne contient qu’un seul entier.

Indication de résolution : on pourra remarquer que si le motif a \(n\) lignes alors

  • les éléments de la 2e colonne s’obtiennent en additionnant \(n-1\) à chaque élément de la 1ère colonne
  • les éléments de la 3e colonne s’obtiennent en additionnant \(n-2\) à chaque élément de la 2ème colonne
  • et ainsi de suite.