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
etb
puis entreb
eta
, 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 indicesi
etj
deL
, 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]
alorssomme0 = True
puisque(-4) + 1 + 9 + (-6) = 0
, - si
L=[-4, 0, 5, 1]
alorssomme0 = True
puisque la liste contient un terme nul, - si
L=[-3, 2, 4]
alorssomme0 = 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
où \(\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\) où \(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.\)
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\).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 deb
- \(\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 deb
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îtrap
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¶
Écrire un code qui, à partir d’un entier \(n>0\), dessine \(n\) piles de \(n\) disques (\(n=5\) ci-dessous) :
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 desn
lignes, la boucle interne va dessiner chaque disque desn
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 entieri
de 0 à \(\mathtt{n-1}\) et de même pour les lignes ; - 2e méthode : on utilise deux variables
x
ety
pour systématiquement désigner les coordonnées du centre du disque à dessiner. On dessine alors le disque puis on met à jourx
ety
pour le centre du disque suivant à dessiner.
- 1re méthode : on calcule les coordonnées de chaque centre en imaginant que le disque en bas à droite a pour coordonnées
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 :
Pour cela, on pourra par exemple imaginer que chaque disque est indexé par un couple
(i, j)
de deux entiers entre 0 etn-1
oùi
représente la colonne contenant le disque et de mêmej
pour la ligne. On observera alors que la couleur noire ou rouge dépend de la parité dei
etj
.
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 :
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}\).
Dessiner un carré tel que chaque côté soit composé de \(\mathtt{n}\) disques rouges de diamètre \(\mathtt{d}\) :
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.
- le code est composée de 4 boucles
On demande de dessiner un motif tel que le suivant :
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.
- calculer à l’avance le nombre
Carrés concentriques en dégradé de gris¶
Dessiner une figure suivant le modèle ci-dessous :
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¶
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 !.
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}\) où \(\mathtt{n}\) est la longueur de
L
- pour la partie entière, importer la fonction
ceil
du modulemath
- pour le logarithme en base 2, importer la fonction
log2
du modulemath
- pour la partie entière, importer la fonction
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
.
Le code suivant montre comment, à partir d’un entier
n
, générer la liste formée den-1
,n
etn+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]
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