Recueil d'exercices pour apprendre Python au lycée

M_C

1597.9K views

GitHub

This is a preview

This playground version isn't public and is work in progress.

Previous: Projet Euler n°61 à 65 Next: Projet Euler n°71 à 75

Equation Diophantienne

Difficulté : Moyenne (25%) Origine : Projet Euler n°66

COnsidérons l'équation Diophantienne quadratique de la forme : $x^{2} - D y^{2} = 1$ .

Par exemple, quand $D = 13$ , la solution minimale en $x$ est $649^{2} - 13 \times 180^{2} = 1$ .

On admettra qu'il n'y a pas de solutions pour les entiers strictement positifs quand D est un carré.

En trouvant les solutions minimales en x pour D dans l'ensemble {2, 3, 5, 6, 7}, on obtient :

$3^{2} - 2 \times 2^{2} = 1$
$2^{2} - 3 \times 1^{2} = 1$
$9^{2} - 5 \times 4^{2} = 1$
$5^{2} - 6 \times 2^{2} = 1$
$8^{2} - 7 \times 3^{2} = 1$

Donc, en considérant les solutions minimales en x pour D ≤ 7, le plus grand x est obtenu pour D=5.

Trouver la valeur de D ≤ 1000 pour laquelle la valeur de x est maximale parmi les solutions minimale en x de l'équation considérée.

On affichera le résultat avec print.

Equation Diophantienne

Chemin de somme maximum II

Difficulté : Facile Origine : Projet Euler n°67

A partir d'un nombre dans les triangles ci-dessous, on peut se déplacer uniquement vers le bas soit vers le nombre juste en dessous, soit vers le nombre à droite de celui qui est en dessous. Par exemple, à partir du 6, on peut descendre uniquement vers le 9 ou le 3 mais pas vers le 5.

En partant du sommet du triangle ci-dessous, le chemin dont le total en additionnant les nombres du chemin est le plus grand est 23.

3
7 4
2 4 6
8 5 9 3

En effet, 3 + 7 + 4 + 9 = 23.

Trouver le chemin de somme maximum dans le triangle donné. (Le triangle est donné sous forme de chaine de caractère).

Note : L'énoncé est le même que le problème 18 à la différence près que cette fois ci le triangle a 100 lignes ce qui fait un total de 2^99 chemins. Même avec un ordinateur qui calcule 1000 milliard de chemins par seconde, il faudrait 20 milliard d'années pour tous les tester. Il vaut donc mieux refléchir à des stratégies plus efficaces.

On affichera le résultat avec print.

Chemin de somme maximum II

triangle='''
59
73 41
52 40 09
26 53 06 34
10 51 87 86 81
61 95 66 57 25 68
90 81 80 38 92 67 73
30 28 51 76 81 18 75 44
84 14 95 87 62 81 17 78 58
21 46 71 58 02 79 62 39 31 09
56 34 35 53 78 31 81 18 90 93 15
78 53 04 21 84 93 32 13 97 11 37 51
45 03 81 79 05 18 78 86 13 30 63 99 95
39 87 96 28 03 38 42 17 82 87 58 07 22 57
06 17 51 17 07 93 09 07 75 97 95 78 87 08 53
67 66 59 60 88 99 94 65 55 77 55 34 27 53 78 28
76 40 41 04 87 16 09 42 75 69 23 97 30 60 10 79 87
12 10 44 26 21 36 32 84 98 60 13 12 36 16 63 31 91 35
70 39 06 05 55 27 38 48 28 22 34 35 62 62 15 14 94 89 86
66 56 68 84 96 21 34 34 34 81 62 40 65 54 62 05 98 03 02 60
38 89 46 37 99 54 34 53 36 14 70 26 02 90 45 13 31 61 83 73 47
36 10 63 96 60 49 41 05 37 42 14 58 84 93 96 17 09 43 05 43 06 59
66 57 87 57 61 28 37 51 84 73 79 15 39 95 88 87 43 39 11 86 77 74 18
54 42 05 79 30 49 99 73 46 37 50 02 45 09 54 52 27 95 27 65 19 45 26 45
71 39 17 78 76 29 52 90 18 99 78 19 35 62 71 19 23 65 93 85 49 33 75 09 02
33 24 47 61 60 55 32 88 57 55 91 54 46 57 07 77 98 52 80 99 24 25 46 78 79 05
92 09 13 55 10 67 26 78 76 82 63 49 51 31 24 68 05 57 07 54 69 21 67 43 17 63 12
24 59 06 08 98 74 66 26 61 60 13 03 09 09 24 30 71 08 88 70 72 70 29 90 11 82 41 34
66 82 67 04 36 60 92 77 91 85 62 49 59 61 30 90 29 94 26 41 89 04 53 22 83 41 09 74 90
48 28 26 37 28 52 77 26 51 32 18 98 79 36 62 13 17 08 19 54 89 29 73 68 42 14 08 16 70 37
37 60 69 70 72 71 09 59 13 60 38 13 57 36 09 30 43 89 30 39 15 02 44 73 05 73 26 63 56 86 12
55 55 85 50 62 99 84 77 28 85 03 21 27 22 19 26 82 69 54 04 13 07 85 14 01 15 70 59 89 95 10 19
04 09 31 92 91 38 92 86 98 75 21 05 64 42 62 84 36 20 73 42 21 23 22 51 51 79 25 45 85 53 03 43 22
75 63 02 49 14 12 89 14 60 78 92 16 44 82 38 30 72 11 46 52 90 27 08 65 78 03 85 41 57 79 39 52 33 48
78 27 56 56 39 13 19 43 86 72 58 95 39 07 04 34 21 98 39 15 39 84 89 69 84 46 37 57 59 35 59 50 26 15 93
42 89 36 27 78 91 24 11 17 41 05 94 07 69 51 96 03 96 47 90 90 45 91 20 50 56 10 32 36 49 04 53 85 92 25 65
52 09 61 30 61 97 66 21 96 92 98 90 06 34 96 60 32 69 68 33 75 84 18 31 71 50 84 63 03 03 19 11 28 42 75 45 45
61 31 61 68 96 34 49 39 05 71 76 59 62 67 06 47 96 99 34 21 32 47 52 07 71 60 42 72 94 56 82 83 84 40 94 87 82 46
01 20 60 14 17 38 26 78 66 81 45 95 18 51 98 81 48 16 53 88 37 52 69 95 72 93 22 34 98 20 54 27 73 61 56 63 60 34 63
93 42 94 83 47 61 27 51 79 79 45 01 44 73 31 70 83 42 88 25 53 51 30 15 65 94 80 44 61 84 12 77 02 62 02 65 94 42 14 94
32 73 09 67 68 29 74 98 10 19 85 48 38 31 85 67 53 93 93 77 47 67 39 72 94 53 18 43 77 40 78 32 29 59 24 06 02 83 50 60 66
32 01 44 30 16 51 15 81 98 15 10 62 86 79 50 62 45 60 70 38 31 85 65 61 64 06 69 84 14 22 56 43 09 48 66 69 83 91 60 40 36 61
92 48 22 99 15 95 64 43 01 16 94 02 99 19 17 69 11 58 97 56 89 31 77 45 67 96 12 73 08 20 36 47 81 44 50 64 68 85 40 81 85 52 09
91 35 92 45 32 84 62 15 19 64 21 66 06 01 52 80 62 59 12 25 88 28 91 50 40 16 22 99 92 79 87 51 21 77 74 77 07 42 38 42 74 83 02 05
46 19 77 66 24 18 05 32 02 84 31 99 92 58 96 72 91 36 62 99 55 29 53 42 12 37 26 58 89 50 66 19 82 75 12 48 24 87 91 85 02 07 03 76 86
99 98 84 93 07 17 33 61 92 20 66 60 24 66 40 30 67 05 37 29 24 96 03 27 70 62 13 04 45 47 59 88 43 20 66 15 46 92 30 04 71 66 78 70 53 99
67 60 38 06 88 04 17 72 10 99 71 07 42 25 54 05 26 64 91 50 45 71 06 30 67 48 69 82 08 56 80 67 18 46 66 63 01 20 08 80 47 07 91 16 03 79 87
18 54 78 49 80 48 77 40 68 23 60 88 58 80 33 57 11 69 55 53 64 02 94 49 60 92 16 35 81 21 82 96 25 24 96 18 02 05 49 03 50 77 06 32 84 27 18 38
68 01 50 04 03 21 42 94 53 24 89 05 92 26 52 36 68 11 85 01 04 42 02 45 15 06 50 04 53 73 25 74 81 88 98 21 67 84 79 97 99 20 95 04 40 46 02 58 87
94 10 02 78 88 52 21 03 88 60 06 53 49 71 20 91 12 65 07 49 21 22 11 41 58 99 36 16 09 48 17 24 52 36 23 15 72 16 84 56 02 99 43 76 81 71 29 39 49 17

Pentagone magique

Difficulté : Moyen(25%) Origine : Projet Euler n°68

Considérons le triangle magique suivant, rempli avec les nombres de 1 à 6 tel que chaque ligne a une somme qui vaut neuf.

Triangle magique

En tournant dans le sens des aiguilles d'une montre et en commençant par le groupe de trois qui a le noeud externe dont la valeur est la plus petite (4,3,2 dans cet exemple), chaque solution peut être décrite de manière unique. Par exemple, la solution ci-dessus peut être décrite par l'ensemble : 4,3,2; 6,2,1; 5,1,3 .

Il est possible de completer ce triangle avec quatre sommes différentes : 9, 10, 11 et 12. Il y a en tout huit solutions :

Total Ensemble solution
9 4,2,3; 5,3,1; 6,1,2
9 4,3,2; 6,2,1; 5,1,3
10 2,3,5; 4,5,1; 6,1,3
10 2,5,3; 6,3,1; 4,1,5
11 1,4,6; 3,6,2; 5,2,4
11 1,6,4; 5,4,2; 3,2,6
12 1,5,6; 2,6,4; 3,4,5
12 1,6,5; 3,5,4; 2,4,6

En concaténant chaque groupe, il est possible de former une chaine de caractère de 9 chiffres. La chaine maximum pour ce triangle magique est 432621513.

En utilisant des nombres de 1 à 10, selon l'arrangement, il est possible de former ainsi des chaines de 16 ou 17 chiffres. Quelle est la chaine de caractère maximum formée de 16 chiffres pour un pentagone magique ?

Pentagone magique

On affichera le résultat avec print.

Pentagone magique

Fonction phi d'Euler et maximum

Difficulté : Moyen(10%) Origine : Projet Euler n°69

La fonction phi d'Euler, φ(n) est utilisée pour déterminer le nombre d'entiers inférieurs à n qui sont premiers avec n. Par exemple, comme les entiers 1, 2, 4, 5, 7, et 8 sont tous inférieurs à 9 et premiers avec 9, on a φ(9)=6.

n	premiers avec n	φ(n)	n/φ(n)
2	1	1	2
3	1,2	2	1.5
4	1,3	2	2
5	1,2,3,4	4	1.25
6	1,5	2	3
7	1,2,3,4,5,6	6	1.1666...
8	1,3,5,7	4	2
9	1,2,4,5,7,8	6	1.5
10	1,3,7,9	4	2.5

On peut voir que pour n=6, la valeur de n/φ(n) est maximum pour n ≤ 10.

Trouver la valeur de n ≤ 1,000,000 pour laquelle n/φ(n) est maximum.

On affichera le résultat avec print.

Fonction phi d'Euler et maximum

Fonction phi d'Euler et permutations

Difficulté : Moyen(20%) Origine : Projet Euler n°70

le nombre 1 est considéré comme premier avec tout entier strictement positif donc φ(1)=1.

Il est interessant de noter que φ(87109)=79180, en remarquant que 87109 est une permutation de 79180.

Trouver la valeur de n inférieure à $10^{7}$ pour laquelle φ(n) est une permutation de n et le ratio n/φ(n) est un minimum.

On affichera le résultat avec print.

Fonction phi d'Euler et permutations

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

This is a preview

109/127 Projet Euler n°66 à 70

Equation Diophantienne

Chemin de somme maximum II

Pentagone magique

Fonction phi d'Euler et maximum

Fonction phi d'Euler et permutations