Énumération
Table des matières :
I. Concept des algorithmes d'énumération
II. Problème des cubes parfaits
III. Cycles physiologqiues
IV. Problème de la fausse monnaie
I. Concept des algorithmes d'énumération
Énumération : Explorer systématiquement toutes les solutions possibles.
La mise en œuvre d'algorithmes d'énumération se fait souvent simplement en utilisant des boucles (imbriquées), ce qui ne présente pas une grande complexité intellectuelle.
Approche de résolution :
- Pour chaque paramètre de la solution, utiliser des boucles pour explorer toutes les valeurs possibles, et pour chaque combinaison, utiliser des instructions conditionnelles pour vérifier si c'est une solution valide et si elle est optimale.
Consiels pour l'énumération :
- Parfois, si les valeurs énumérées suivent une formule spécifique, on peut réduire le nombre de boucles nécessaires. Par exemple, pour énumérer A+B+C=100, on peut simplement énumérer A et B, puis calculer C comme 100-A-B, réduisant ainsi une boucle.
- Changer l'ordre d'énumération est également une technique utile. Bien que l'ordre croissant ou décroissant soit courant, d'autres ordres peuvent être utilisés, ce qui fait appel à des algorithmes gloutons.
- Parfois, nous devons énumérer l'état de plusieurs éléments (généralement deux états possibles). Nous pouvons utiliser les valeurs 0/1 du binaire pour représenter ces états. Par exemple (énumération binaire), pour 5 enfants, nous pouvons indiquer s'ils ont lu un blog en utilisant 0 (non) et 1 (oui). Avec le nombre 5 (binaire 101), cela signifie que le 1er et le 3ème enfant ont lu le blog. Nous pouvons donc énumérer de 0 à 31 pour représenter tous les états possibles des 5 enfants.
- Lorsque l'énumération directe est trop lente, on peut précalculer et stocker tous les résultats, puis les utiliser directement dans un programme séparé. C'est l'idée des tables précalculées.
- Parfois, les boucles imbriquées simples ne suffisent pas, et on peut avoir recours à des algorithmes récursifs.
II. Problème des cubes parfaits
Cubes parfaits****Description du problèmeUne équation de la forme a³ = b³ + c³ + d³ est appelée équation de cube parfait. Par exemple, 12³ = 6³ + 8³ + 10³. Écrivez un programme qui, pour un entier positif N (N ≤ 100), recherche tous les quadruplets (a, b, c, d) tels que a³ = b³ + c³ + d³, où a, b, c, d sont supérieurs à 1 et inférieurs ou égaux à N, et b ≤ c ≤ d.
EntréeUn entier positif N (N ≤ 100). SortieChaque ligne affiche un cube parfait. Le format de sortie est : Cube = a, Triple = (b,c,d) où a, b, c, d sont remplacés par les valeurs réelles du quadruplet trouvé.
Affichez les résultats dans l'ordre croissant de a. Pour deux cubes parfaits ayant la même valeur de a, celui avec la plus petite valeur de b est affiché en premier. Si les valeurs de b sont égales, comparez c, et si nécessaire, d. Exemple d'entrée24 Exemple de sortieCube = 6, Triple = (3,4,5) Cube = 12, Triple = (6,8,10) Cube = 18, Triple = (2,12,16) Cube = 18, Triple = (9,12,15) Cube = 19, Triple = (3,10,18) Cube = 20, Triple = (7,14,17) Cube = 24, Triple = (12,16,20)
Nous avons quatre variables à énumérer : a, b, c, d. L'approche consiste à tester toutes les combinaisons possibles, ce qui nécessite au minimum quatre boucles imbriquées. Pour chaque combinaison, nous vérifions si le cube de a est égal à la somme des cubes de b, c et d. Si la condition est satisfaite, nous affichons les valeurs.
Approche de résolution :
Utiliser quatre boucles imbriquées pour énumérer a, b, c, d, avec a dans la boucle la plus externe et d dans la boucle la plus interne. Chaque boucle parcourt les valeurs dans l'ordre croissant.
La portée de a : [2, N] La portée de b : [2, a-1] La portée de c : [b, a-1] La portée de d : [c, a-1]
Solution :
1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7 int limite;
8 cin >> limite;
9
10 // Quatre boucles imbriquées pour a, b, c, d
11 // a dans la boucle externe, d dans la boucle interne
12 // Porte de a : [2, limite], b : [2, a-1], c : [b, a-1], d : [c, a-1]
13 for (int a = 2; a <= limite; a++)
14 {
15 for (int b = 2; b < a; b++)
16 {
17 for (int c = b; c < a; c++)
18 {
19 for (int d = c; d < a; d++)
20 {
21 if (a*a*a == b*b*b + c*c*c + d*d*d)
22 {
23 cout << "Cube = " << a << " Triple = (" << b << "," << c << "," << d << ")" << endl;
24 }
25 }
26 }
27 }
28 }
29 return 0;
30 }
III. Cycles physiologiques
Chaque être humain possède trois cycles physiologiques : physique, émotionnel et intellectuel, avec des durées respectives de 23, 28 et 33 jours.
Chaque cycle a un jour de pic, où la personne excelle dans le domaine correspondant. Par exemple, lors du pic du cycle intellectuel, une personne pense rapidement et concentre son énergie efficacement.
Étant donné que les durées des cycles sont différentes, leurs pics ne coïncident généralement pas le même jour.
Pour chaque personne, nous voulons savoir quand les trois pics se produisent le même jour.
Pour chaque cycle, nous donnons le nombre de jours à partir du premier jour de l'année où se produit le pic (ce n'est pas nécessairement le premier pic de l'année).
Votre tâche est, étant donné un nombre de jours à partir du premier jour de l'année, de déterminer quand les trois pics coïncideront à nouveau à partir de cette date (excluant la date donnée).
Par exemple : si la date donnée est 10 et que la prochaine coïncidence des trois pics est le jour 12, nous devons sortir 2 (notez que ce n'est pas 3).
Format d'entrée
Il y a plusieurs ensembles de données.
Pour chaque ensemble, lisez quatre entiers p, e, i, d. Où p, e, i représentent les jours de pic pour les cycles physique, émotionnel et intellectuel (comptés à partir du premier jour de l'année). d est la date donnée.
Quand p = e = i = d = -1, les données d'entrée se terminent.
Format de sortie
Affichez le nombre de jours jusqu'à la prochaine coïncidence des trois pics, à partir de la date donnée.
Utilisez le format :
Cas 1 : la prochaine coïncidence des trois pics aura lieu dans 1234 jours.
Même si le résultat est 1 jour, utilisez toujours la forme plurielle "jours".
Plage de données
0 ≤ p, e, i, d < 3650 La réponse est garantie d'être inférieure à 21252.
Exemple d'entrée :
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1
Exemple de sortie :
Cas 1 : la prochaine coïncidence des trois pics aura lieu dans 21252 jours.
Cas 2 : la prochaine coïncidence des trois pics aura lieu dans 21152 jours.
Cas 3 : la prochaine coïncidence des trois pics aura lieu dans 19575 jours.
Cas 4 : la prochaine coïncidence des trois pics aura lieu dans 16994 jours.
Cas 5 : la prochaine coïncidence des trois pics aura lieu dans 8910 jours.
Cas 6 : la prochaine coïncidence des trois pics aura lieu dans 10789 jours.
Approche de résolution :
À partir du jour d+1, testez chaque jour jusqu'au 21252ème jour. Pour chaque jour k, vérifiez si (k - p)%23 == 0 && (k - e)%28 == 0 && (k - i)%33 == 0.
Comment tester plus efficacement ? En sautant certains jours.
Solution :
1 #include <iostream>
2
3 #define MAX_JOURS 21252
4 using namespace std;
5
6 int main()
7 {
8 /*
9 À partir du jour d+1, testez jusqu'au jour 21252.
10 Pour chaque jour k, vérifiez si (k - p)%23 == 0 && (k - e)%28 == 0 && (k - i)%33 == 0
11 Comment tester plus efficacement ? En sautant certains jours.
12 */
13 int physique, emotionnel, intellectuel, jourDepart, numeroCas = 0;
14 while (cin >> physique >> emotionnel >> intellectuel >> jourDepart && physique != -1)
15 {
16 numeroCas++;
17 int jourActuel;
18 // Trouver le prochain jour où le physique est à son pic
19 for (jourActuel = jourDepart + 1; (jourActuel - physique) % 23 != 0; jourActuel++);
20 // À partir de ce jour, trouver le prochain jour où l'émotionnel est à son pic
21 for (; (jourActuel - emotionnel) % 28 != 0; jourActuel += 23);
22 // À partir de ce jour, trouver le prochain jour où l'intellect est à son pic
23 for (; (jourActuel - intellectuel) % 33 != 0; jourActuel += 23 * 28);
24 cout << "Cas " << numeroCas << " : la prochaine coïncidence des trois pics aura lieu dans " << jourActuel - jourDepart << " jours." << endl;
25 }
26 return 0;
27 }
IV. Problème de la fausse monnaie
Sally Jones possède une douzaine de pièces de monnaie voyageurs. Onze sont authentiques et une est contrefaite. La fausse pièce a la même couleur et la même taille que les vraies, mais son poids est différent. Malheureusement, Sally ne sait pas si la fausse pièce est plus lourde ou plus légère.
Heureusement, son ami lui prête une balance très précise. L'ami lui permet d'effectuer trois pesées pour trouver la fausse pièce.
Par exemple, si elle place deux pièces de chaque côté de la balance et que celle-ci reste équilibrée, les deux pièces sont authentiques. Ensuite, en comparant une vraie pièce avec une troisième, si la balance penche, on peut déterminer que la troisième pièce est contrefaite, et selon le sens de l'inclinaison, si elle est plus lourde ou plus légère.
Avec une bonne organisation, elle peut déterminer laquelle des pièces est contrefaite en trois pesées.
Format d'entrée
Trois lignes, décrivant chacune une pesée. Les pièces sont étiquetées de A à L. Chaque ligne contient deux chaînes de deux lettres représentant les pièces sur chaque côté de la balance (le nombre de pièces de chaque côté est toujours égal), suivies d'un mot : up (la droite monte), down (la droite descend) ou even (équilibré).
Format de sortie
Affichez une ligne au format : XX est la fausse pièce et elle est XXX. où XX est l'étiquette de la fausse pièce, et XXX indique si elle est plus légère (light) ou plus lourde (heavy).
Plage de données
Une solution est garantie d'exister.
Exemple d'entrée :
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
Exemple de sortie :
K est la fausse pièce et elle est légère.
Approche de résolution :
Pour chaque pièce, supposons d'abord qu'elle soit légère et vérifions si cela correspond aux résultats des pesées. Si c'est le cas, le problème est résolu. Sinon, supposons qu'elle soit lourde et vérifions à nouveau. En testant toutes les pièces, nous trouverons nécessairement la fausse pièce.
Solution
1 #include <iostream>
2 #include <cstring>
3
4 using namespace std;
5
6 char Gauche[3][7]; // Pièces sur le côté gauche de la balance
7 char Droite[3][7]; // Piètes sur le côté droit de la balance
8 char Resultat[3][7]; // Résultats des pesées
9 bool EstFausse(char piece, bool estLegere); // EstLegere = true si on suppose la pièce légère, false si on suppose qu'elle est lourde
10
11
12 bool EstFausse(char piece, bool estLegere)
13 {
14 for (int i = 0; i < 3; i++)
15 {
16 char* coteGauche, * coteDroite; // Pointeurs vers les chaînes de caractères des côtés de la balance
17 if (estLegere)
18 {
19 coteGauche = Gauche[i];
20 coteDroite = Droite[i];
21 }
22 else // Si on suppose que la pièce est lourde, on échange les côtés dans l'interprétation des résultats
23 {
24 coteGauche = Droite[i];
25 coteDroite = Gauche[i];
26 }
27 switch (Resultat[i][0])
28 {
29 case 'u': // up (la droite monte)
30 if (strchr(coteDroite, piece) == NULL)
31 {
32 return false;
33 }
34 break;
35 case 'e': // even (équilibré)
36 if (strchr(coteGauche, piece) || strchr(coteDroite, piece))
37 {
38 return false;
39 }
40 break;
41 case 'd': // down (la droite descend)
42 if (strchr(coteGauche, piece) == NULL)
43 {
44 return false;
45 }
46 break;
47 }
48 }
49 return true;
50 }
51
52
53 int main()
54 {
55 int nbTests;
56 cin >> nbTests;
57 while (nbTests--)
58 {
59 for (int i = 0; i < 3; i++)
60 {
61 cin >> Gauche[i] >> Droite[i] >> Resultat[i];
62
63 }
64 for (char piece = 'A'; piece <= 'L'; piece++)
65 {
66 if (EstFausse(piece, true))
67 {
68 cout << piece << " est la fausse pièce et elle est légère." << endl;
69 break;
70 }
71 else if (EstFausse(piece, false))
72 {
73 cout << piece << " est la fausse pièce et elle est lourde." << endl;
74 break;
75 }
76 }
77 }
78
79 return 0;
80 }