Apprendre les bases de Python pour réussir en N.S.I.

sebmalicet

110.7K views

GitHub

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

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

Open Source Your Knowledge, Become a Contributor

107/135 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

Les bases de Python pour le lycée

Recueil d'exercices pour apprendre Python au lycée

Apprendre Python dans le secondaire

Python pour le collège et le lycée. Exercices, Cours, TP, Projets.