Boucles imbriquées

\(\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)}\) \(\newcommand{\pe}[1]{\left\lfloor {#1} \right\rfloor}\) \(\newcommand{\trans}[1]{\,^t\!{#1}}\)

Boucles imbriquées

Cours

Boucles for imbriquées

Soit à écrire un code Python qui affiche un texte comme le suivant :

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

Plus précisément, chaque ligne L reprend la ligne précédente K mais L est complétée par l’entier qui suit le dernier entier de la liste affichée dans K.

Noter qu’il y a deux types de répétition d’actions :

  • répétition d’affichage de ligne
  • répétition d’affichage de nombres dans chaque ligne

Un code répondant au problème pourrait être le suivant :

1
2
3
4
for lig in range(1,15):
    for col in range(1,lig + 1):
        print(col, end = " ")
    print()

On constate qu’une boucle for (lignes 2-3) est imbriquée dans une boucle for (lignes 1-4). On dit que :

  • la boucle ligne 1 est la boucle externe ;
  • la boucle ligne 2 est la boucle interne (ou encore la boucle la plus profonde).

La boucle for (ligne 1) contrôle la progression par ligne. Un numéro lig de ligne étant fixée, l’autre boucle for (ligne 2) contrôle la progression de gauche à droite dans la ligne fixée.

Noter à la ligne 3 la présence de l’argument nommé de la fonction print :

end = " "

qui permet

  • d’empêcher le passage à la ligne pendant qu’on affiche les éléments de la \(i^\text{e}\) ligne,
  • de séparer deux nombres par un espace.

Noter aussi ligne 4, l’appel à la fonction print pour séparer deux lignes consécutives de l’affichage.

D’une façon générale, le corps de toute boucle for peut contenir n’importe quel type d’instructions, et en particulier une autre boucle for.

Exercice type : Liste d’entiers sans éléments consécutifs

On donne une liste L d’entiers et on cherche à construire un booléen sansConsecutifs et qui vaut True si L ne contient pas deux entiers consécutifs. Voici en fonction de L différentes valeurs pour le booléen sansConsecutifs

1
2
3
4
[9, 2, 0, 4, 4, 0, 7] -> True
[9, 5, 0, 4, 4, 0, 7] -> False
[7, 2, 0, 4, 4, 3, 7] -> False
[7] -> True

Explication :

  • dans le 1er cas, on observe bien qu’il n’y a aucune valeur \(k\) de la liste pour laquelle \(k-1\) ou \(k+1\) soit présente dans la liste ;
  • dans le 2ème cas, la liste contient un 5 et un 4 (qui sont consécutifs)
  • dans le 3ème cas, la liste contient un 2 et un 3 (qui sont consécutifs) ; on pouvait aussi remarquer qu’il y a un 4 et un 3.

On cherchera à examiner toutes les paires possibles d’éléments de la liste.

Solution

On rappelle que consécutif signifie qu’il y a 1 d’écart, comme entre 2020 et 2021 ou entre 42 et 41.

L’idée est d’essayer tous les cas : on compare le premier élément de L à chaque élément de L et on regarde s’il y aurait 1 d’écart entre les éléments et si oui, on met à jour un drapeau sansConsecutifs en le faisant passer à True (il est placé à False au départ). Puis on recommence avec le deuxième élément de L.

Dans le cas du 2e exemple ci-dessus, il y aura 1 d’écart avec le 4e élément de L et donc le drapeau va changer. Et ainsi de suite jusqu’à épuisement de la liste.

Si après toutes ces comparaisons, le drapeau est resté inchangé (à False donc), c’est qu’il n’y a jamais deux éléments consécutifs dans la liste et si au contraire, il a un moment basculé à True , c’est que la liste contient deux éléments consécutifs.

D’où le code suivant :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
tests=[
    [9, 2, 0, 4, 4, 0, 7],
    [9, 5, 0, 4, 4, 0, 7],
    [7, 2, 0, 4, 4, 3, 7],
    [7]]


for L in tests:
    sansConsecutifs=False
    for a in L:
        for b in L:
            if a-b==1:
                sansConsecutifs=True
    print(L, '->', not sansConsecutifs)

Signalons juste que ce code présente plusieurs défauts :

  • il compare systématiquement l’écart entre a et b puis entre b et a, ce qui est inutile ;
  • les boucles continuent à tourner si le drapeau est passé à True ce qui évidemment n’est pas optimal.

Exercice type : Grille : remplissage par lignes

Vous allez devoir écrire un code qui affiche un motif dont un exemple est visible ci-dessous :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
42 43 44 45
46 47 48 49
50 51 52 53
54 55 56 57
58 59 60 61
62 63 64 65
66 67 68 69
70 71 72 73
74 75 76 77
78 79 80 81

Ce motif consiste en une grille rectangulaire de dimensions n x p données (n : nombre de lignes, p : nombre de colonnes) de tous les entiers consécutifs à partir d’un entier donné d, le remplissage devant se faire ligne par ligne.

Ci-dessus, l’affichage est obtenu pour \(n=10\), \(p=4\) et \(d=42\). Noter que deux colonnes sont séparées par un espace.

On répétera \(n\) fois l’écriture d’une ligne et chaque ligne sera formée de la répétition des \(p\) éléments de la ligne. Pour savoir quel nombre afficher à une position donnée on maintiendra à jour une variable N initialisée à d.

Solution

Un motif 2D nécessite typiquement deux boucles imbriquées. Ici, on doit répéter \(n\) fois l’écriture d’une ligne et chaque ligne est formée de la répétition des \(p\) éléments de la ligne. On a donc un schéma du type :

1
2
3
for i in range(n):
    for j in range(p):
        # A COMPLÉTER

D’où, par exemple, le code suivant :

1
2
3
4
5
6
7
8
9
n=10
p=4
d=42
k=0
for i in range(n):
    for j in range(p):
        print(d+k, end=' ')
        k+=1
    print()

Effectuer plusieurs tests à l’aide d’une boucle for

Pour conforter la validité d’un programme, il est d’usage d’effectuer des tests. Pour tester un morceau de code sur un grand nombre d’entrées, on peut utiliser une boucle for qui parcourt une liste de données à tester.

Soit un code qui doit tester si un entier \(n\geq 0\) est strictement plus grand que 1000 ou, sinon, multiple de 10 mais pas multiple de 100. Par exemple, 2021 vérifie le test car \(2021 > 1000\), \(120\) aussi (c’est un multiple de 10 mais pas de 100) mais pas 700 car \(700 < 1000\) et \(700\) est multiple de 100.

D’une façon générale , pour vérifier le caractère correct d’un programme, on ne se limite pas à un ou deux tests de ce programme. On accumule les tests en ayant la volonté de mettre en défaut le programme :

1
2
3
4
5
6
7
tests = [700, 20, 42, 2020, 2021, 3000, 1000, 0]
for i in range(len(tests)):
    x=tests[i]
    if x > 1000 or (x % 10 == 0 and x % 100 != 0):
        print(x, True)
    else:
        print(x, False)
 8
 9
10
11
12
13
14
15
700 False
20 True
42 False
2020 True
2021 True
3000 True
1000 False
0 False
  • Ligne 1 : les données à tester sont placées dans une liste
  • La totalité du code à tester (lignes 3-7) est placée dans le corps de la boucle for parcourant la liste (ligne 2).
  • Lignes 5 et 7 : la sortie (lignes 8-15) doit être lisible pour qu’on puisse vérifier rapidement l’exactitude de la réponse donnée par le programme (c’est pour cela que x est affiché)
  • Ligne 1 : on essaye de mettre en défaut le programme en examinant tous les cas typiques possibles et en étudiant les valeurs particulières situées aux bords comme ici 0, 1000.

Exercices

Intersection de listes

On donne deux listes L et M chacune formée d’entiers distincts, par exemple L = [8, 9, 3, 5] et M = [1, 2, 3, 4, 6, 8, 9]. On demande d’écrire une liste inter valant la liste des élements communs aux deux listes. Voici quelques exemples de comportements

L = [8, 9, 3, 5] M = [1, 2, 3, 4, 6, 8, 9] -> [8, 9, 3]
L = [8, 9, 2, 4] M = [8, 4, 7] -> [8, 4]
L = [6] M = [1, 2, 5] -> []

Répéter l’affichage du contenu d’une liste

Soit une liste L d’entiers (entre 0 et 9, pour des raisons d’esthétique de l’affichage). On demande d’afficher \(n\) fois cette liste où \(n>0\) est un entier donné. Par exemple, si L est la liste de contenu :

4 8 0 9 6 3 2 8

et si \(n=6\), l’affichage obtenu doit être :

4 8 0 9 6 3 2 8
4 8 0 9 6 3 2 8
4 8 0 9 6 3 2 8
4 8 0 9 6 3 2 8
4 8 0 9 6 3 2 8
4 8 0 9 6 3 2 8

Deux chiffres successifs seront séparées d’un espace.

Remplir une liste avec des 0, des 1 et des 2

Afficher toutes les listes de 4 éléments formées d’éléments parmi 0, 1 ou 2.

Par exemple, les listes suivantes conviennent

[0, 2, 0, 1]
[0, 2, 0, 2]
[1, 1, 1, 1]

Somme qui vaut 42

On donne deux listes d’entiers L et M. Créer un booléen somme42 qui vaut True si la somme de deux nombres, l’un dans L et l’autre dans M, vaut 42. Sinon, le booléen vaudra False. Voici quelques exemples de comportements attendus :

[17, 22, 5, 5, 33, 8] [34, 8, 20] -> True
[6, 22, 5, 5, 33, 8] [35, 8, 25]  -> False

Explication pour le premier cas : remarquer que \(8+34=42\) ce qui explique la réponse.

Entiers opposés dans une liste

On donne une liste L d’entiers non nuls et on demande de dire si cette liste contient deux entiers opposés (comme \(-42\) et \(42\)). Par exemple, si la liste L est

[-2, 1, -3, 5, -7, -4, 5, -5, 3, -8]

alors, L contient deux entiers opposés (\(-3\) et \(3\)) aux indices 2 et 8.

et si la liste L est

L = [-5, 4, -1, 4, 8, 6, -9, 8, -3, 8]

alors cette liste ne contient jamais deux éléments qui sont opposés.

Ecrire un code qui définit une variable opp qui vaut

  • None si deux entiers quelconques de la liste ne sont jamais opposés ;
  • une liste [i, j] si aux indices i et j de L, les éléments sont opposés.

Dans le cas de la première liste donnée en exemple, une réponse possible attendue est

opp = [2, 8]

et dans le cas de la seconde, la réponse attendue est :

opp = None

Somme nulle

On donne une liste L d’entiers et on demande de construire un booléen somme0 valant True s’il existe des entiers successifs dans L et dont la somme vaut 0.

Par exemple,

  • si L=[-4, 2, -4, 1, 9, -6, -4] alors somme0 = True puisque (-4) + 1 + 9 + (-6) = 0,
  • si L=[-4, 0, 5, 1] alors somme0 = True puisque la liste contient un terme nul,
  • si L=[-3, 2, 4] alors somme0 = False.

On utilisera trois ou même deux boucles for imbriquées. L’idée est de parcourir toutes les sous-listes de L dont la somme est à calculer. Chacune de ces sous-listes commence à l’indice d et termine à l’indice f\(\mathtt{0\geq d\leq f<n}\). On génère d dans une première boucle puis f dans une boucle imbriquée. Ensuite, on calcule la somme correspondante ce qui nécessite une troisième boucle for imbriquée. En fait, il est possible de calculer la somme avec la 2e boucle for.

Etude d’une suite définie par une somme

On pose, pour \(n\geq 1\) entier, \(S_n=\displaystyle\sum_{k=1}^n\left(\frac k{n} \right)^k\). Par exemple,

\(S_5=\frac 1{5} +\frac 4{25} +\frac {27}{125} +\frac {256}{625} +\frac {3125}{3125} =1241/625=1.9856\)

En calculant, les 20 premiers termes de la suite, examiner si la suite \(S_n\) est monotone (autrement dit, elle croît toujours ou elle décroît toujours).

La suite semble-t-elle tendre vers une certaine valeur ?

Afficher les effectifs d’une liste d’entiers

On donne une liste L d’entiers, par exemple

L = [81, 31, 81, 12, 81, 9, 12, 65]

On demande d’afficher le nombre de fois que les différents nombres de la liste L apparaissent dans L. L’ordre d’affichage devra respecter l’ordre d’apparition dans la liste L. Avec l’exemple ci-dessus, le programme devra afficher

81 : 3
31 : 1
12 : 2
9 : 1
65 : 1

La ligne

12 : 2

de l’affichage signifie juste que 12 apparaît 2 fois dans la liste L. On remarquera que dans la colonne de gauche de l’affichage , aucun élément de la liste n’est répété.

On pourra appliquer la méthode suivante. On parcourra la liste L dans une boucle for. Auparavant, on aura créé une liste vide dejaVus destinés à enregistrer les éléments déjà rencontrés à l’indice i de la boucle de parcours. À chaque indice i de la liste L, on regardera si l’élément L[i] est dans la liste dejaVus et si non, on comptera, avec une boucle for imbriquée, le nombre d’éléments de L d’indices \(\mathtt{j> i}\) et valant L[i].

Pièces de monnaie

Dans un pays imaginaire, les pièces de monnaie sont de a unités ou de b unités. On demande d’écrire un code qui détermine si, oui ou non, il est possible de régler un certain montant donné de m unités. Par exemple si a = 49 et b = 10 alors on ne peut pas régler m = 42 unités ni m = 105 mais on peut régler m = 128 puisque 128 = 3*10 + 2*49.

Vous ne devez pas utiliser de boucles imbriquées.

Montant irréalisable

Un objet de type A coûte \(n\) euros, un objet de type B coûte \(n+1\) euros. On dit qu’un montant \(m\) est réalisable s’il est possible de choisir des objets de type A ou B et dont l’achat corresponde à ce montant \(m\).

Par exemple, si \(n=10\) alors le montant 119 est réalisable car il correspond à l’achat de 2 objets de type A et de 9 objets de type B : \(\mathtt{119 = 2\times 10 + 9\times 11}\). Mais certains montants sont irréalisables, par exemple \(m=45\) ou \(m=78\).

Par ailleurs, on peut montrer que tout montant assez grand est forcément réalisable. On demande de conjecturer, en expérimentant autant de valeurs de \(n\) qu’il vous paraît nécessaire, le plus grand montant non réalisable en fonction de \(n\). Pour \(n=10\), ce montant est de 89 euros.

On pourra utiliser la fonction sorted(L) qui renvoie une liste de même contenu que L mais triée.

Multiple de 42 qui soit somme de deux carrés

Un carré est un nombre qui est de la forme \(n\times n=n^2\)\(n\) est un entier strictement positif, par exemple 36 ou 49 sont des carrés mais pas 42.

Noter que, pour la suite, 0 n’est pas considéré comme un carré.

En examinant toutes les sommes de carrés possibles, on peut, par exemple, affirmer que

  • 42 n’est pas une somme de deux carrés
  • 41 est une somme de deux carrés : \(41=4^2+5^2\)
  • 25 est une somme de deux carrés non nuls : \(25=3^2+4^2\)
  • 9 n’est pas une somme de deux carrés non nuls.

Il se trouve qu’il existe 5 entiers entre 1 et 10000 qui sont multiples de 42 et qui peuvent s’écrire comme somme de deux carrés. On vous demande de trouver ces 5 nombres.

On recherchera toutes les façons d’obtenir une somme de deux carrés et on observera aussi que \(100\times 100 = 10000\) en sorte que si \(n=a^2+b^2\) alors on peut supposer que \(0\leq a, b\leq 100\).

Nombre de rectangles d’aire plafonnée

Les rectangles différents à côtés entiers et d’aire valant au plus 6 sont de tailles :

1x1, 1x2, ..., 1x6, 2x2, 2x3

il y en a donc 8.

Plus généralement, on donne un entier strictemement positif \(\mathtt{N}\) et on demande de dire combien de rectangles de dimensions entières \(\mathtt{a, b}\) avec \(\mathtt{a\leq b}\) ont une aire valant au plus \(\mathtt{N}\).

Par exemple, pour \(\mathtt{N=1821}\), on en trouvera 7000.

Pour une recherche compétitive, voir sur SPOJ le problème Rectangles. Voir aussi cette suite.

Problème de programmation linéaire

On cherche à maximiser la quantité \(z=x+6y\) lorsque \(x\) et \(y\) sont des entiers satisfaisant les contraintes suivantes :

\(\begin{cases}x, y \geq 0\\x\leq 200\\y\leq 300\\x+y\leq 400\end{cases}\)

Pour cela on testera tous les cas possibles en utilisant deux boucles for imbriquées. On trouvera une valeur maximum de \(z=1900\).

Problème de dénombrement

Ce problème a été posé dans un questionnaire de Mathraining. On donne un entier positif \(\mathtt{n}\), typiquement \(\mathtt{n=60}\). Déterminer le nombre de triplets \(\mathtt{(x, y, z)}\) d’entiers strictement positifs vérifiant \(\mathtt{x+y+z=n}\). Pour \(\mathtt{n=60}\), on trouvera 1711 triplets.

Nombres consécutifs dont la somme vaut 54

Trouver toutes les listes d’entiers positifs consécutifs dont la somme vaille 54. Parmi toutes les solutions, on trouvera la liste d’entiers 17, 18 et 19 puisque \(17+18+19=54\).

Cet exercice a pour origine cette question.

Nombres de Harshad

On dit qu’un entier n>0 est un nombre de Harshad s’il est divisible par la somme de ses chiffres. Par exemple, 42 est un nombre de Harshad car la somme de ses chiffres est 6 et 42 est un multiple de 6. En revanche, 32 n’est pas un nombre de Harshad puisque 32 n’est pas un multiple de 5.

Déterminer la liste des nombres de Harshad ayant 1, 2 ou 3 chiffres (on trouvera une liste de 212 entiers). On utilisera 3 boucles for imbriquées.

Somme de sommes

Soit la suite \((U)\) des entiers positifs qui ne s’écrivent, en base 10, qu’avec le chiffre 1 :

\(1, 11, 111, 1111, 11111, \dots\)

On remarquera qu’un tel nombre est une somme de puissances de 10, par exemple pour mille cent-onze :

\(1111= 10^0+10^1+10^2+10^3=1+10+100+1000.\)

  1. Soit \(n\geq 1\) un entier donné. Calculer, avec une boucle for, le \(n\)-ième nombre de la suite \((U)\) (on ne se contentera pas d’afficher le nombre mais on le placera dans une variable). Par exemple, si \(n=4\), le programme doit calculer le nombre \(1111\).

  2. Calculer la somme des \(N\) premiers nombres de la suite \((U)\). Par exemple, si \(N=20\) :

    \(1 + 11 + 111 + 1111 + 11111 + ... + 1111111111111111111\)

    Par exemple, pour \(N=10\) on trouvera 1234567900.

    Pour cela, on utilisera une boucle for suivant deux méthodes :

    • placer une partie du code de la question précédente dans le corps de la boucle (donc deux boucles imbriquées);
    • générer simultanément les termes de la somme et les sommes partielles (simple boucle).

Tri-casier

On donne une liste L d’entiers positifs, par exemple

[47, 5, 5, 49, 23, 31, 13, 46, 48, 20,
9, 19, 19, 40, 42, 31, 38, 9, 45, 26]

On demande de construire une nouvelle liste M dont les éléments sont ceux de L mais triés suivant leur chiffre des unités.

Par exemple, dans le cas de la liste ci-dessus, M est la liste suivante :

[20, 40, 31, 31, 42, 23, 13, 5, 5, 45,
46, 26, 47, 48, 38, 49, 9, 19, 19, 9]

Explication : on lit d’abord les éléments de L qui se terminent par 0 (20, 40) puis ceux qui se terminent par 1 (31, 31), et ainsi de suite jusqu’aux éléments de L qui se terminent par 9.

Inversions dans une liste

On donne une liste L d’entiers, par exemple

[5, 5, 4, 11, 9, 1, 5]

On appelle inversion de L tout couple (a, b) de valeurs dans L telles que :

  • a apparaisse à gauche de b
  • \(\mathtt{a > b}\).

Par exemple, (4, 1) est un inversion de la liste précédente.

Ecrire un code qui affiche toutes les inversions d’une liste L. Dans le cas de la liste ci-dessus, le code doit afficher :

5 4
5 1
5 4
5 1
4 1
11 9
11 1
11 5
9 1
9 5

mais pas forcément dans cet ordre.

Ecart minimal d’indices (boucles imbriquées)

On donne une liste L d’entiers, par exemple

L = [16, 14, 17, 13, 15, 14, 16, 15, 13, 14, 16, 15, 13, 16]

On demande de déterminer l’écart minimal d’indices où se trouveraient des valeurs identiques. Cette valeur est 3 dans la liste ci-dessus ; en effet, 15 apparaît aux indices 4 et 7 et tout autre répétition de valeur, comme 13, apparaît dans la liste avec un écart d’indices valant au moins 3. On notera que l’écart minimal est aussi atteint pour la valeur 16 aux indices 10 et 13.

Si la liste ne contient que des valeurs différentes, le nombre minimal recherché sera 0.

L’algorithme à appliquer est le suivant : on parcourra la liste en utilisant deux boucles for imbriquées. Ce n’est pas une méthode optimale et elle ne conviendrait pas pour une liste ayant plusieurs millions d’éléments.

Cet exercice est inspiré de l’exercice Distance minimale de la demi-finale du concours Algoréa 2017.

Différences successives

On donne une liste L d’entiers, par exemple :

L = [9, 5, 6, 3, 6, 2, 6]

et on va réduire L à un unique élément par le procédé suivant : à chaque étape, on constitue une nouvelle liste dont les éléments sont la différence de deux éléments successifs de L. Avec l’exemple, la nouvelle liste M est :

M = [4, -1, 3, -3, 4, -4]

(par exemple, le coefficient -1 en 2e position provient de la différence \(\mathtt{5-6}\) entre le 2e et le 3e coefficient de L)

On recommence ainsi avec la nouvelle liste et ainsi de suite jusqu’à ce que la liste ne contienne plus qu’un élément. A chaque étape, la nouvelle liste a un élément de moins que la précédente.

La question posée est de calculer l’unique élément de la dernière liste.

Dans le cas de l’exemple ci-dessus, la valeur à trouver est 42.

Damier de nombres

Réaliser un programme qui affiche un damier de forme carrée, de côté de longueur \(n>0\) et rempli alternativement du nombre 4 et du nombre 2. La case en haut à gauche sera toujours 4. Par exemple, pour \(n=7\), le damier aura l’allure suivante :

4 2 4 2 4 2 4
2 4 2 4 2 4 2
4 2 4 2 4 2 4
2 4 2 4 2 4 2
4 2 4 2 4 2 4
2 4 2 4 2 4 2
4 2 4 2 4 2 4

Il est possible de coder l’exercice de plusieurs façons. On pourra imaginer que la grille est numérotée par ligne et par colonne et on remarquera que tous les 4 de la grille sont à des indices de ligne et de colonne qui ont toujours la même parité (soit les deux indices sont pairs, soit les deux indices sont impairs).

Pyramide croissante de nombres

Observez le motif suivant obtenu pour \(n=6\) :

1
2 2
3 3 3
4 4 4 4
5 5 5 5 5
6 6 6 6 6 6

On vous donne un entier \(n>0\) et on vous demande de construire le motif formé de \(n\) lignes de la manière suivante :

  • la 1ère ligne contient le nombre 1 écrit une seule fois,
  • la 2ème ligne contient le nombre 2 écrit 2 fois,
  • la 3ème ligne contient le nombre 3 écrit 3 fois,
  • et ainsi de suite jusqu’à avoir écrit \(n\) lignes.

Sur une même ligne, deux nombres seront séparés par un espace.

Motif carré formé des chiffres 4 ou 2

Écrire un programme qui à partir d’un entier \(n>0\) affiche un carré de côté \(n\), dont la bordure est faite avec le nombre 4 et l’intérieur rempli par le nombre 2. Deux chiffres successifs seront séparés par une espace.

Voici un exemple avec un carré de côté \(n=8\) :

4 4 4 4 4 4 4 4
4 2 2 2 2 2 2 4
4 2 2 2 2 2 2 4
4 2 2 2 2 2 2 4
4 2 2 2 2 2 2 4
4 2 2 2 2 2 2 4
4 2 2 2 2 2 2 4
4 4 4 4 4 4 4 4

Méthode. On affichera ligne par ligne, en commençant par le haut. Chaque ligne sera affichée par une boucle for. La première et la dernière ligne seront traitées à part. Les autres lignes seront traitées par une boucle for répétant \(n-2\) fois le même motif. On peut aussi imaginer chaque ligne et chaque colonne indexée par un entier i et un entier j et afficher le chiffre qu’il faut en fonction des valeurs de i et de j.

Motif carré et sa diagonale

Étant donné un entier naturel \(n\geq 1\), on demande de construire un carré de côté \(n\) et rempli de chiffres et respectant les deux contraintes suivantes :

  • la diagonale descendante est constituée du chiffre 0,
  • les autres cases du carré sont constituées du chiffre 1.

Par exemple, si \(n=10\), le carré a l’allure suivante :

0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1 1 1
1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 0

Deux chiffres côte à côte sur une même ligne sont séparés par exactement un espace.

Triangle décroissant de nombres

Observez le motif suivant obtenu pour \(n=6\) :

6 6 6 6 6 6
5 5 5 5 5
4 4 4 4
3 3 3
2 2
1

On vous donne un entier \(n>0\) et on vous demande de construire le motif formé de \(n\) lignes de la manière suivante :

  • la 1ère ligne contenant le nombre \(n\) écrit \(n\) fois,
  • la 2ème ligne contenant le nombre \(n-1\) écrit \(n-1\) fois,
  • la 3ème ligne contenant le nombre \(n-2\) écrit \(n-2\) fois
  • et ainsi de suite jusqu’à avoir écrit \(n\) lignes.

Sur une même ligne, deux nombres seront séparés par un espace.

Triangles de 0 et de 1

Dans cet exercice, vous allez devoir afficher un motif dépendant d’un entier \(n\). Par exemple, pour \(n=6\) le motif est le triangle suivant :

0
1 1
0 0 0
1 1 1 1
0 0 0 0 0
1 1 1 1 1 1

Explications :

  • il y a \(n\) lignes
  • les lignes de 0 et les lignes de 1 alternent
  • chaque ligne contient un chiffre de plus que la précédente
  • deux chiffres voisins sont séparés par un espace.

Ecrire une code qui partant de l’entier n génère le motif ci-dessus.

Triangle à lignes alternés

Dans cet exercice, vous allez devoir afficher un motif dépendant d’un entier \(n\) et de deux entiers \(a\) et \(b\). Par exemple, pour \(n=6\), \(a=42\) et \(b=81\), le motif est le triangle suivant :

42
81 81
42 42 42
81 81 81 81
42 42 42 42 42
81 81 81 81 81 81

Explications :

  • il y a \(n\) lignes
  • la première ligne ne contient que le nombre a
  • les lignes de a et les lignes de b alternent
  • chaque ligne contient un nombre de plus que la précédente
  • deux nombres voisins sont séparés par un espace.

Ecrire une code qui partant de l’entier n génère le motif ci-dessus.

Triangle : lignes consécutives décroissantes

Vous devez écrire un code qui dépend d’un entier \(n\) et qui affiche un motif dont un exemple est visible ci-dessous pour \(n=6\) :

1
2 1
3 2 1
4 3 2 1
5 4 3 2 1
6 5 4 3 2 1

Explication

  • il y a \(n\) lignes
  • chaque ligne contient un nombre de plus que la précédente
  • la \(k\)-ème ligne affiche tous les entiers en décroissant de \(k\) à 1.

Ecrire un code qui partant d’un entier \(n\) génère le motif ci-dessus.

Grille : remplissage par colonnes

Vous devez écrire un code qui affiche un motif dont un exemple est visible ci-dessous :

42 52 62 72
43 53 63 73
44 54 64 74
45 55 65 75
46 56 66 76
47 57 67 77
48 58 68 78
49 59 69 79
50 60 70 80
51 61 71 81

Ce motif consiste en une grille rectangulaire de dimensions n x p données (n : nombre de lignes, p : nombre de colonnes) de tous les entiers consécutifs à partir d’un entier donné d, le remplissage devant se faire colonne par colonne.

Ci-dessus, l’affichage obtenu pour n=10, p=4 et d=42. Noter que deux colonnes sont séparées par un espace.

Vous pourrez remarquer que dans chaque ligne, les valeurs des nombres se suivent avec un écart valant le nombre p de colonnes, par exemple 42, 52, 62 et 72 dans la première ligne.

Sapin

Dessiner, en mode texte, un sapin suivant le modèle ci-dessous. Le dessin dépendra de l’entier \(n>0\) qui représente la hauteur du feuillage (dans l’exemple, \(n=10\)).

Avant de faire apparaître le bord gauche du feuillage, il faut placer des espaces (caractère " ") en début de ligne.

         *
        ***
       *****
      *******
     *********
    ***********
   *************
  ***************
 *****************
*******************
         #
         #

Triangle et son bord

On donne un entier \(\mathtt{n\geq 1}\) et on demande de dessiner en mode texte un triangle de côté \(\mathtt{n}\). Ci-dessous, ce que le programme doit afficher si \(\mathtt{n=9}\) :

*
**
* *
*  *
*   *
*    *
*     *
*      *
*********

L’intérieur du triangle est obtenu avec le caractère espace, tapé avec la barre d’espace. De haut en bas, le nombre d’espaces va en augmentant de 1. Chaque côté est formé de \(\mathtt{n}\) astérisques. Bien vérifier le résultat pour \(\mathtt{n}\) valant 1, 2 ou 3.

Carrés concentriques alternés

On demande de construire un motif ayant la forme d’un carré de côté n. Par exemple, si n=9 le motif est :

+ + + + + + + + +
+ . . . . . . . +
+ . + + + + + . +
+ . + . . . + . +
+ . + . + . + . +
+ . + . . . + . +
+ . + + + + + . +
+ . . . . . . . +
+ + + + + + + + +

ou si n=10 le motif est :

+ + + + + + + + + +
+ . . . . . . . . +
+ . + + + + + + . +
+ . + . . . . + . +
+ . + . + + . + . +
+ . + . + + . + . +
+ . + . . . . + . +
+ . + + + + + + . +
+ . . . . . . . . +
+ + + + + + + + + +

Il s’agit de dessiner des carrés concentriques formés alternativement du symbole plus et du symbole point, le carré extérieur étant formé de signe plus et de côté n.

En indexant chaque symbole du carré par deux indices \(\mathtt{i\geq 0}\) et \(\mathtt{j\geq 0}\), on pourra considérer le plus petit des 4 entiers \(\mathtt{i, j, n-1-i, n-1-j}\) ce qui mesure la distance du symbole considéré avec les bords du carré (on pourra utiliser la fonction standard min).

Liste des entiers k répétés k fois

On considère la suite infinie des entiers écrits dans l’ordre croissant telle chaque entier \(k\geq 1\) est répété \(k\) fois :

1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 7 etc

Etant donné p un entier strictement positif, construire une liste L dont les éléments sont, dans l’ordre, les suivants :

  • 1 une seule fois
  • 2 deux fois de suite,
  • 3 trois fois de suite
  • etc
  • jusqu’à p qui apparaîtra p fois de suite.

Par exemple, si p=5 alors L est la liste suivante :

[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5]

Damier de disques

  1. Écrire un code qui, à partir d’un entier \(n>0\), dessine \(n\) piles de \(n\) disques (\(n=5\) ci-dessous) :

    ../../../_images/mpl_disques_noirs.png

    Les disques seront bord à bord, de couleur noire et de diamètre \(d\) de votre choix.

    Le motif est obtenu en réalisant deux boucles for imbriquées : la boucle externe va dessiner chaque ligne des n lignes, la boucle interne va dessiner chaque disque des n disques d’une ligne.

    Il y a deux méthodes pour obtenir les centres des différents disques à dessiner.

    • 1re méthode : on calcule les coordonnées de chaque centre en imaginant que le disque en bas à droite a pour coordonnées (0, 0). Pour cela, on imaginera que chaque colonne de disques est indexée par un entier i de 0 à \(\mathtt{n-1}\) et de même pour les lignes ;
    • 2e méthode : on utilise deux variables x et y pour systématiquement désigner les coordonnées du centre du disque à dessiner. On dessine alors le disque puis on met à jour x et y pour le centre du disque suivant à dessiner.
  2. Modifier le code précédent pour obtenir le dessin d’un damier de \(n\times n\) disques alternant les couleurs noir/rouge. Le disque en bas à gauche sera noir :

    ../../../_images/mpl_disques_couleurs.png

    Pour cela, on pourra par exemple imaginer que chaque disque est indexé par un couple (i, j) de deux entiers entre 0 et n-1i représente la colonne contenant le disque et de même j pour la ligne. On observera alors que la couleur noire ou rouge dépend de la parité de i et j.

Dessin d’un motif en forme de croix

On vous donne un entier impair \(n>1\) et un entier \(c>0\) et vous devez générer un motif de forme carrée de côté \(c\) et rempli de \(n^2\) disques colorés. Par exemple, si \(n=7\), le motif a la forme suivante :

../../../_images/croix_carree_mpl.png

Le motif est un carré rempli de \(n\times n\) disques noirs ou rouges. Deux disques voisins seront tangents. Les axes vertical et horizontal de symétrie du carré sont formés de disques noirs et les autres disques sont de couleur rouge.

Dessiner des carrés concentriques alternés

On donne un entier \(\mathtt{n\geq 1}\) et un diamètre entier \(\mathtt{d>0}\), par exemple \(\mathtt{d=40}\).

  1. Dessiner un carré tel que chaque côté soit composé de \(\mathtt{n}\) disques rouges de diamètre \(\mathtt{d}\) :

    ../../../_images/carre_bord_disque.png

    Voici quelques indications :

    • le code est composée de 4 boucles for
    • (optionnel) dans chaque boucle, on n’a besoin de ne dessiner que \(\mathtt{n-1}\) disques
    • faire en sorte que (x,y) désigne la position du centre du disque courant.
  2. On demande de dessiner un motif tel que le suivant :

    ../../../_images/carres_concentriques_alternes_sous_turtle.png

    Le motif est une succession de carrés concentriques formés de disques de couleur alternativement orange et bleue. Le carré extérieur est de côté n et formé de disques bleus (sur le dessin, \(\mathtt{n=9}\)).

    Voici quelques indications :

    • calculer à l’avance le nombre N de carrés à dessiner et boucler sur ce nombre
    • à la fin de chaque étape de la boucle précédente, on ajuste la couleur et le côté du prochain carré à dessiner (le nombre diminue de 2 à chaque étape)
    • dans de corps de la boucle, placer le code de dessin de la question précédente mais adapté au carré à construire.

Carrés concentriques en dégradé de gris

Dessiner une figure suivant le modèle ci-dessous :

../../../_images/carre_degrader_gris.png

Le côté du carré contient \(n\) disques (13 sur le modèle ci-dessus). La figure est formée d’une succession de \(p\) carrés concentriques (sur le modèle \(p=7\)) constitués de disques. Les couleurs des disques des carrés successifs sont plus clairs lorsqu’on se rapproche du centre. Une couleur grise sera codée en RGB décimal entre 0 et 1, par exemple dans la figure ci-dessus, la couleur du carré extérieur est c = 0.30 et la couleur suivante s’obtient en ajoutant 0.09. On poura utiliser que \(\mathtt{p = (n+1)//2}\). Comme l’option de couleur doit être donnée sous forme de chaîne, on devra utiliser le constructeur str pour faire évoluer la valeur de la couleur.

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. Cette question est corrigée dans cette vidéo et si vous êtes en TP, merci de la regarder plus tard !.

  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].

Affichage en tas binaire (boucles for imbriquées)

Observez l’exemple suivant que l’on demande de coder dans toute sa généralité : on donne une liste L d’entiers telle que

[99, 28, 51, 76, 85, 52, 97, 97, 20, 78, 74, 34, 72, 75]

et on demande de l’afficher comme suit :

99
28 51
76 85 52 97
97 20 78 74 34 72 75

La première ligne contient le premier élément, la 2e les deux éléments suivants, la 3e contient les 4 éléments suivants et ainsi de suite, chaque ligne (sauf éventuellement la dernière) contenant deux fois plus d’éléments que la précédente.

Indications

  • Le nombre \(\mathtt{N}\) de lignes est la partie entière supérieure du logarithme en base 2 de \(\mathtt{n+1}\)\(\mathtt{n}\) est la longueur de L

    • pour la partie entière, importer la fonction ceil du module math
    • pour le logarithme en base 2, importer la fonction log2 du module math
  • Boucler sur \(\mathtt{N-1}\) et imbriquer une boucle pour afficher les éléments de la ligne courante

  • En fin de corps de la boucle principale, mettre à jour la longueur de la ligne courante

  • Il restera à afficher la dernière ligne (dont la longueur n’est pas une puissance de 2)

Générer toutes les permutations

On se donne un entier \(\mathtt{n\geq 1}\) et on veut générer itérativement toutes les permutations des entiers de 1 à \(\mathtt{n}\), autrement dit tous les alignements possibles de ces entiers. Par exemple, si \(\mathtt{n=4}\), la liste [3, 1, 4, 2] est une permutation, parmi 24 possibles. On demande d’écrire un code qui crée une liste contenant, sous forme de listes, toutes les permutations des entiers de 1 à \(\mathtt{n}\). Par exemple, si \(\mathtt{n=3}\), on devra trouver une liste de 6 listes comme celle-ci :

[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]

On appliquera l’algorithme décrit ci-après. Pour construire la liste L des permutations des entiers de 1 à \(\mathtt{n}\), on suppose qu’on aura déjà construit la liste M des permutations de 1 à \(\mathtt{n-1}\). On obtiendra alors toutes les permutations cherchées en insérant l’objet \(\mathtt{n}\) à l’une des \(\mathtt{n}\) positions possibles d’une quelconque permutation venant de la liste \(\mathtt{M}\). Par exemple, avec \(\mathtt{n=4}\), la permutation [2,1,3] donnera les \(\mathtt{n}\) permutations suivantes :

[4, 2, 1, 3], [2, 4, 1, 3], [2, 1, 4, 3], [2, 1, 3, 4]

et si on répète cette opération avec les 6 permutations de 1, 2 et 3, on obtiendra toutes les permutations sur 1, 2, 3 et 4.

Il s’agit de créer les permutations itérativement, sans utiliser une fonction récursive.

Tester avec une boucle for

Dans chaque question, les tests sont à effectuer au sein d’une boucle for.

  1. Le code suivant montre comment, à partir d’un entier n, générer la liste formée de n-1, n et n+1 :

    n=42
    L=[n-1, n, n+1]
    

    Tester le code précédent pour les entiers n valant 42, 100, 0 et 2020. On devra obtenir l’affichage suivant :

    42 -> [41, 42, 43]
    100 -> [99, 100, 101]
    0 -> [-1, 0, 1]
    2020 -> [2019, 2020, 2021]
    
  2. Le code suivant montre (et on l’admettra) comment coder un booléen qui traduit que le minimum d’une liste L d’entiers est unique :

    L=[81, 42, 87, 63, 50, 42, 42]
    miniUnique = L.count(min(L))==1
    print(miniUnique)
    
    False
    

    Appliquer le code précédent aux 5 listes suivantes :

    [42], [42, 42, 42], [81, 42, 87, 63, 50, 42, 42], [80, 42, 53, 64]

    Le code devra afficher

    [42] -> True
    [42, 42, 42] -> False
    [81, 42, 87, 63, 50, 42, 42] -> False
    [80, 42, 53, 64] -> True
    

Tests aléatoires

Le code suivant montre comment coder un booléen qui traduit que le minimum d’une liste L d’entiers est unique :

L=[81, 42, 87, 63, 50, 42, 42]
miniUnique = L.count(min(L))==1
print(miniUnique)
False

Générer aléatoirement 10 listes d’entiers entre 0 et 9, de longueur variable et s’assurer que le code précédent fonctionne en testant les 10 listes avec une boucle for. La sortie pourra être de la forme suivante :

[7, 9, 3, 0, 6] -> True
[2, 4, 4, 7, 3, 6, 2] -> False
[1, 7, 0] -> True
[1, 1, 3, 2, 5, 1] -> False
[6, 9, 2] -> True
[1, 9, 8, 7, 9, 2] -> True
[4, 7, 0, 7, 8, 0] -> False
[4, 9, 6] -> True
[8, 8, 1, 7] -> True
[4, 9, 5, 0, 6, 4, 8, 2] -> True