Recueil d'exercices pour apprendre Python au lycée

M_C

1596.8K views

GitHub

This is a preview

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

Previous: Projet Euler n°101 à 105 Next: Projet Euler n°111 à 115

Ensembles de sommes spéciaux : Meta-Testing

Difficulté : Difficile (50%) Origine : Projet Euler n°106

Notons S(A) la somme des éléments d'un ensemble A de taille n. On dira que A est un ensemble de sommes spécial si pour tous ensembles disjoints B et C, on a les deux propriétés suivantes qui sont vérifiées :

S(B) ≠ S(C) : c'est à dire que les sommes de sous ensembles sont toutes différentes
Si B contient plus d'éléments que C alors S(B) > S(C)

Pour ce problème on va supposer que les ensembles contiennent n éléments formant une suite strictement croissante et qu'il vérifient déjà la deuxième règle.

De manière surprenante, parmi les 25 paires de sous-ensembles qu'on peut former à partir d'un ensemble à 4 éléments, seulement une de ces paires a besoin d'être testée pour vérifier la première règle. De la même manière, pour n=7, seule 70 des 966 paires de sous-ensembles ont besoin d'être testées.

Pour n=12, combien des 261625 paires de sous-ensembles qu'on peut obtenir ont elles besoin d'être testées pour vérifier la première règle ?

Note : Ce problème est en relation avec le problème 103 et 105.

On affichera le résultat avec print.

Ensembles de sommes spéciaux : Meta-Testing

Réseau minimal

Difficulté : Moyen (35%) Origine : Projet Euler n°107

Le réseau non orienté suivant est composé de 7 sommets and 12 arêtes avec un poids total de 243.

reseau

Ce réseau peut être représenté par le tableau suivant :

	A	B	C	D	E	F	G
A	-	16	12	21	-	-	-
B	16	-	-	17	20	-	-
C	12	-	-	28	-	31	-
D	21	17	28	-	18	19	23
E	-	20	-	18	-	-	11
F	-	-	31	19	-	-	27
G	-	-	-	23	11	27	-

Cependant, il est possible d'optimiser le reseau en retirant des arêtes et toujours assurer que chaque points du réseau reste connecté. Le réseau qui réussit le maximum d'économie est montré ci-dessous. Il a un poids de 93, représentant une économie de 243 − 93 = 150 par rapport au réseau d'origine.

Matrice minimale

En utilisant la matrice donnée ci-dessous, correspondant à un réseau de 40 sommets, trouver l'économie maximum qui peut être réalisée en retirant des arêtes du réseau mais en assurant que tous les sommets restent connectés entre eux.

On affichera le résultat avec print.

Minimal network

# La matrice 
matrice = [['-', '-', '-', 427, 668, 495, 377, 678, '-', 177, '-', '-', 870, '-', 869, 624, 300, 609, 131, '-', 251, '-', '-', '-', 856, 221, 514, '-', 591, 762, 182, 56,'-', 884, 412, 273, 636, '-', '-', 774], ['-', '-', 262, '-', '-', 508, 472, 799, '-', 956, 578, 363, 940, 143, '-', 162, 122, 910, '-', 729, 802, 941, 922, 573, 531, 539, 667, 607, '-', 920, '-', '-', 315, 649, 937, '-', 185, 102, 636, 289], ['-', 262, '-', '-', 926, '-', 958, 158, 647, 47, 621, 264, 81, '-', 402, 813, 649, 386, 252, 391, 264, 637, 349, '-', '-', '-', 108, '-', 727, 225, 578, 699, '-', 898, 294, '-', 575, 168, 432, 833], [427, '-', '-', '-', 366, '-', '-', 635, '-', 32, 962, 468, 893, 854, 718, 427, 448, 916, 258, '-', 760, 909, 529, 311, 404, '-', '-', 588, 680, 875, '-', 615, '-', 409, 758, 221, '-', '-', 76, 257], [668, '-', 926, 366, '-', '-', '-', 250, 268, '-', 503, 944, '-', 677, '-', 727, 793, 457, 981, 191, '-', '-', '-', 351, 969, 925, 987, 328, 282, 589, '-', 873, 477, '-', '-', 19, 450, '-', '-', '-'], [495, 508, '-', '-', '-', '-', '-',765, 711, 819, 305, 302, 926, '-', '-', 582, '-', 861, '-', 683, 293, '-', '-',66, '-', 27, '-', '-', 290, '-', 786, '-', 554, 817, 33, '-', 54, 506, 386, 381], [377, 472, 958, '-', '-', '-', '-', '-', '-', 120, 42, '-', 134, 219, 457, 639, 538, 374, '-', '-', '-', 966, '-', '-', '-', '-', '-', 449, 120, 797, 358, 232, 550, '-', 305, 997, 662, 744, 686, 239], [678, 799, 158, 635, 250, 765, '-', '-', '-', 35, '-', 106, 385, 652, 160, '-', 890, 812, 605, 953, '-', '-', '-', 79, '-', 712, 613, 312, 452, '-', 978, 900, '-', 901, '-', '-', 225, 533, 770, 722], ['-', '-', 647, '-', 268, 711, '-', '-', '-', 283, '-', 172, '-', 663, 236, 36, 403, 286, 986, '-', '-', 810, 761, 574, 53, 793, '-', '-', 777, 330, 936, 883, 286, '-', 174, '-', '-', '-', 828, 711], [177, 956, 47, 32, '-', 819, 120, 35, 283, '-', 50, '-', 565, 36, 767, 684, 344, 489, 565, '-', '-', 103, 810, 463, 733, 665, 494, 644, 863, 25, 385, '-', 342, 470, '-', '-', '-', 730, 582, 468], ['-', 578, 621, 962, 503, 305, 42, '-', '-', 50, '-', 155, 519, '-', '-', 256, 990, 801, 154, 53, 474, 650, 402, '-', '-', '-', 966, '-', '-', 406, 989, 772, 932, 7, '-', 823, 391, '-', '-', 933], ['-', 363, 264, 468, 944, 302, '-', 106, 172, '-', 155, '-', '-', '-', 380, 438, '-', 41, 266, '-', '-', 104, 867, 609, '-', 270, 861, '-', '-', 165, '-', 675, 250, 686, 995, 366, 191, '-', 433, '-'], [870, 940, 81, 893, '-', 926, 134, 385, '-', 565, 519, '-', '-', 313, 851, '-', '-', '-', 248, 220, '-', 826, 359, 829, '-', 234, 198, 145, 409, 68, 359, '-', 814, 218, 186, '-', '-', 929, 203, '-'], ['-', 143, '-', 854, 677, '-', 219, 652, 663, 36, '-', '-', 313, '-', 132, '-', 433, 598, '-', '-', 168, 870, '-', '-', '-', 128, 437, '-', 383, 364, 966, 227, '-', '-', 807, 993, '-', '-', 526, 17], [869, '-', 402, 718, '-', '-', 457, 160, 236, 767, '-', 380, 851, 132, '-', '-', 596, 903, 613, 730, '-', 261, '-', 142, 379, 885, 89, '-', 848, 258, 112, '-', 900, '-', '-', 818, 639, 268, 600, '-'], [624, 162, 813, 427, 727, 582, 639, '-', 36, 684, 256, 438, '-', '-', '-', '-', 539, 379, 664, 561, 542, '-', 999, 585, '-', '-', 321, 398, '-', '-', 950, 68, 193, '-', 697, '-', 390, 588, 848, '-'], [300, 122, 649, 448, 793, '-', 538, 890, 403, 344, 990, '-', '-', 433, 596, 539, '-', '-', 73, '-', 318, '-', '-', 500, '-', 968, '-', 291, '-', '-', 765, 196, 504, 757, '-', 542, '-', 395, 227, 148], [609, 910, 386, 916, 457, 861, 374, 812,286, 489, 801, 41, '-', 598, 903, 379, '-', '-', '-', 946, 136, 399, '-', 941, 707, 156, 757, 258, 251, '-', 807, '-', '-', '-', 461, 501, '-', '-', 616, '-'],[131, '-', 252, 258, 981, '-', '-', 605, 986, 565, 154, 266, 248, '-', 613, 664, 73, '-', '-', 686, '-', '-', 575, 627, 817, 282, '-', 698, 398, 222, '-', 649,'-', '-', '-', '-', '-', 654, '-', '-'], ['-', 729, 391, '-', 191, 683, '-', 953, '-', '-', 53, '-', 220, '-', 730, 561, '-', 946, 686, '-', '-', 389, 729, 553, 304, 703, 455, 857, 260, '-', 991, 182, 351, 477, 867, '-', '-', 889, 217, 853], [251, 802, 264, 760, '-', 293, '-', '-', '-', '-', 474, '-', '-', 168, '-', 542, 318, 136, '-', '-', '-', '-', 392, '-', '-', '-', 267, 407, 27, 651, 80, 927, '-', 974, 977, '-', '-', 457, 117, '-'], ['-', 941, 637, 909, '-', '-', 966, '-', 810, 103, 650, 104, 826, 870, 261, '-', '-', 399, '-', 389, '-', '-', '-', 202, '-', '-', '-', '-', 867, 140, 403, 962, 785, '-', 511, '-', 1, '-', 707, '-'], ['-', 922, 349, 529, '-', '-', '-', '-', 761, 810, 402, 867, 359, '-', '-', 999, '-', '-', 575, 729, 392, '-', '-', 388, 939, '-', 959, '-', 83, 463, 361, '-', '-', 512, 931, '-', 224, 690, 369, '-'], ['-', 573, '-', 311, 351, 66, '-', 79, 574, 463, '-', 609, 829, '-', 142, 585, 500, 941, 627, 553, '-', 202, 388, '-', 164, 829, '-', 620, 523, 639, 936, '-', '-', 490, '-', 695, '-', 505, 109, '-'], [856, 531, '-', 404, 969, '-', '-', '-', 53, 733, '-', '-', '-', '-', 379, '-', '-', 707, 817, 304, '-', '-', 939, 164, '-', '-', 616, 716, 728, '-', 889, 349, '-', 963, 150, 447, '-', 292, 586, 264], [221, 539, '-', '-', 925, 27, '-', 712, 793, 665, '-', 270, 234, 128, 885, '-', 968, 156, 282, 703, '-', '-', '-', 829, '-', '-', '-', 822, '-', '-', '-', 736, 576, '-', 697, 946, 443, '-', 205, 194], [514, 667, 108, '-', 987, '-', '-', 613, '-', 494, 966, 861, 198, 437, 89,321, '-', 757, '-', 455, 267, '-', 959, '-', 616, '-', '-', '-', 349, 156, 339,'-', 102, 790, 359, '-', 439, 938, 809, 260], ['-', 607, '-', 588, 328, '-', 449, 312, '-', 644, '-', '-', 145, '-', '-', 398, 291, 258, 698, 857, 407, '-', '-', 620, 716, 822, '-', '-', 293, 486, 943, '-', 779, '-', 6, 880, 116, 775, '-',947], [591, '-', 727, 680, 282, 290, 120, 452, 777, 863, '-', '-', 409, 383, 848, '-', '-', 251, 398, 260, 27, 867, 83, 523, 728, '-', 349, 293, '-', 212, 684,505, 341, 384, 9, 992, 507, 48, '-', '-'], [762, 920, 225, 875, 589, '-', 797, '-', 330, 25, 406, 165, 68, 364, 258, '-', '-', '-', 222, '-', 651, 140, 463, 639, '-', '-', 156, 486, 212, '-', '-', 349, 723, '-', '-', 186, '-', 36, 240, 752], [182, '-', 578, '-', '-', 786, 358, 978, 936, 385, 989, '-', 359, 966, 112, 950, 765, 807, '-', 991, 80, 403, 361, 936, 889, '-', 339, 943, 684, '-', '-', 965, 302, 676, 725, '-', 327, 134, '-', 147], [56, '-', 699, 615, 873, '-', 232, 900, 883, '-', 772, 675, '-', 227, '-', 68, 196, '-', 649, 182, 927, 962, '-', '-', 349, 736, '-', '-', 505, 349, 965, '-', 474, 178, 833, '-', '-', 555, 853, '-'], ['-', 315, '-', '-', 477, 554, 550, '-', 286, 342, 932, 250, 814, '-', 900, 193, 504, '-', '-', 351, '-', 785, '-', '-', '-', 576, 102, 779, 341, 723, 302, 474, '-', 689, '-', '-', '-', 451, '-', '-'], [884, 649, 898, 409, '-', 817, '-', 901, '-', 470, 7, 686, 218, '-', '-', '-', 757, '-', '-', 477, 974, '-', 512, 490, 963, '-', 790, '-', 384, '-', 676, 178, 689, '-', 245, 596, 445, '-', '-', 343], [412, 937, 294, 758, '-', 33, 305, '-', 174, '-', '-', 995, 186, 807, '-',697, '-', 461, '-', 867, 977, 511, 931, '-', 150, 697, 359, 6, 9, '-', 725, 833, '-', 245, '-', 949, '-', 270, '-', 112], [273, '-', '-', 221, 19, '-', 997, '-', '-', '-', 823, 366, '-', 993, 818, '-', 542, 501, '-', '-', '-', '-', '-', 695, 447, 946, '-', 880, 992, 186, '-', '-', '-', 596, 949, '-', 91, '-', 768, 273], [636, 185, 575, '-', 450, 54, 662, 225, '-', '-', 391, 191, '-', '-', 639, 390, '-', '-', '-', '-', '-', 1, 224, '-', '-', 443, 439, 116, 507, '-', 327, '-','-', 445, '-', 91, '-', 248, '-', 344], ['-', 102, 168, '-', '-', 506, 744, 533, '-', 730, '-', '-', 929, '-', 268, 588, 395, '-', 654, 889, 457, '-', 690, 505, 292, '-', 938, 775, 48, 36, 134, 555, 451, '-', 270, '-', 248, '-', 371, 680],['-', 636, 432, 76, '-', 386, 686, 770, 828, 582, '-', 433, 203, 526, 600, 848,227, 616, '-', 217, 117, 707, 369, 109, 586, 205, 809, '-', '-', 240, '-', 853,'-', '-', '-', 768, '-', 371, '-', 540], [774, 289, 833, 257, '-', 381, 239, 722, 711, 468, 933, '-', '-', 17, '-', '-', 148, '-', '-', 853, '-', '-', '-', '-', 264, 194, 260, 947, '-', 752, 147, '-', '-', 343, 112, 273, 344, 680, 540, '-']]

Equation diphantienne réciproque I

Difficulté : Moyen (30%) Origine : Projet Euler n°108

Considérons l'équation suivante pour x, y et n des entiers positifs :

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

Pour n=4, il y a exactement trois solutions distinctes :

$\frac{1}{5} + \frac{1}{20} = \frac{1}{4}$
$\frac{1}{6} + \frac{1}{12} = \frac{1}{4}$
$\frac{1}{8} + \frac{1}{8} = \frac{1}{4}$

Quelle est la plus petit valeur de n pour laquelle le nombre de solutions distinctes dépasse 1000 ?

Ce problème est une version plus facile du problème 110. Il est fortement conseillé de le résoudre en premier.

On affichera le résultat avec print.

Equation diphantienne réciproque I

Flechettes

Difficulté : Moyen (45%) Origine : Projet Euler n°109

Au jeu de flechettes, un joueur lance 3 flechettes sur une cible qui est divisée en 20 secteurs égaux numérotés de 1 à 20.

Cible

Le score d'une flechette est déterminé par le nombre du secteur dans lequelle elle est tombée. Une flechette qui tombe en dehors du cercle rouge et vert extérieur compte pour 0. Les parties de couleur noire ou crème représentent un score simple. Cependant, les cercles rouges et verts extérieurs et intérieurs représentent un score doublé et triplé respectivement.

Au centre de la cible il y a un anneau vert qui rapporte 25 points et un disque rouge qui rapporte 50 points.

Il y a différentes règles mais les plus populaires sont que le joueur commence avec un score de 301 ou 501 et le premier joueur à réduire son total à 0 gagne. Cependant, pour gagner, il faut faire un double (y compris le double au centre de la cible) sur sa fleche qui fait descendre en dessous de 0. Toutes les autres flechettes qui réduise le score en dessous de 1 ne suffisent pas pour gagner.

Quand un joueur est capable de finir à partir de son score, on dit que c'est un "check out" et le plus grand checkout est 170 : T20 T20 D25 (2 triples 20 et un double 25 au centre de la cible)

Il y a exactement 11 différentes façon d'obtenir un check out de 6 :

D3
D1 D2 S2 D2
D2 D1
S4 D1
S1 S1 D2
S1 T1 D1
S1 S3 D1
D1 D1 D1
D1 S2 D1
S2 S2 D1

Il faut remarquer que D1 et D2 sont considérés comme différents car ils finissent par des doubles différents. Cependant, S1 T1 D1 et T1 S1 D1 sont considérés comme identiques.

De plus, On n'inclut pas les manqués dans les combinaisons considérées. Par exemple D3 et identique ) 0 D3 et 0 0 D3.

Il y a 42336 différents check out en tout.

Combien de façons différentes existent il pour un joueur de faire un check-out s'il a un score inférieur strictement à 100 ?

On affichera le résultat avec print.

Flechettes

Equation diphantienne réciproque II

Difficulté : Moyen (40%) Origine : Projet Euler n°110

Considérons l'équation suivante pour x, y et n des entiers positifs :

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$

Pour n=4, il y a exactement trois solutions distinctes :

$\frac{1}{5} + \frac{1}{20} = \frac{1}{4}$
$\frac{1}{6} + \frac{1}{12} = \frac{1}{4}$
$\frac{1}{8} + \frac{1}{8} = \frac{1}{4}$

Quelle est la plus petit valeur de n pour laquelle le nombre de solutions distinctes dépasse quatre million ?

Ce problème est une version plus difficile du problème 108. Il est fortement conseillé de le résoudre en premier.

On affichera le résultat avec print.

Equation diphantienne réciproque II

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

This is a preview

117/127 Projet Euler n°106 à 110

Ensembles de sommes spéciaux : Meta-Testing

Réseau minimal

Equation diphantienne réciproque I

Flechettes

Equation diphantienne réciproque II