Il y a une telle tâche, je crois, qui a provoqué diverses émotions parmi de nombreux cadets de JavaRush. En septembre, lorsque j'ai commencé le cours, la tâche était formulée comme suit : Dans l'expression 1+2*3+4*5+6*7+8*9+10, placez deux paires de parenthèses pour que la valeur de la l'expression devient égale à 537
Maintenant, étant revenu à la solution, j'ai découvert que la formulation a été modifiée : il faut placer deux paires de parenthèses dans l'expression 2*3+4*5+6*7 pour que la valeur devienne égale à 382. l'état neuf, bien entendu, est plus simple que le précédent, car le nombre d'options possibles a diminué d'environ un ordre de grandeur. Mais les 85 restants suffisent amplement pour consacrer une heure ou deux à la recherche manuelle. Évidemment, la tâche n’est pas directement liée à la programmation Java. C'est pourquoi je ne l'ai pas résolu. De tels problèmes n’ont pas de solutions analytiques basées sur le raisonnement ou les propriétés des nombres, mais seulement par la force brute, c’est-à-dire par une recherche brutale de toutes les options possibles. En revanche, il n’est pas moins évident que c’est à l’aide de la programmation que l’on résout les problèmes de ce type. C'est pour ça que je suis revenu. Je viens de m'habituer à l'IDE, et les problèmes du cours au niveau 8 m'ont époustouflé et cela ne me dérangeait pas de passer une soirée ou deux à les résoudre. Vous trouverez ci-dessous comment résoudre ce problème en utilisant Java. J'ai utilisé l'ancienne condition comme base pour l'exemple. Tout d’abord, nous avons besoin d’un moyen de calculer la valeur d’une expression écrite sous forme de chaîne. Nous n'avons pas pu trouver une telle méthode dans les bibliothèques Java standard. J'ai cherché ceci sur Google : http://www.cyberforum.ru/java-j2se/thread283139.html est tout à fait adapté à nos besoins. L'algorithme est basé sur la notation polonaise inversée et fonctionne pour des chaînes valides contenant quatre opérations arithmétiques et parenthèses. Créez un nouveau projet contenant la classe PPN, copiez et collez le code du lien dans un fichier. Le problème peut être résolu dans la méthode main() de la classe PPN. Mais ce n'est pas nécessaire. L'idéologie Java est basée sur la division d'un problème en petites sous-tâches, chacune étant implémentée dans sa propre classe et méthode. Une bonne approche serait de résoudre le problème dans une autre classe, enregistrée dans un fichier séparé. Par conséquent, créez une autre classe dans laquelle vous écrirez l’algorithme d’énumération des parenthèses. Pour calculer la valeur d'une chaîne, vous devez appeler la méthode eval() de la classe PPN : Par exemple, comme ceci
System.out.println(PPN.eval(“2*3+4”));
ou alors
int result = PPN.eval(s2);
Examinons de près la ligne 1+2*3+4*5+6*7+8*9+10 et demandons-nous de combien de façons pouvons-nous mettre une parenthèse ouvrante ? Il peut être placé de dix manières. Si vous numérotez les caractères d'une chaîne à partir de zéro, alors le crochet ouvrant peut être placé aux positions {0,2,4,6,8,10,12,14,16,18}. Placer une parenthèse, par exemple, en sixième position signifie que vous devez prendre tous les caractères de zéro à cinq inclus, puis mettre une parenthèse, puis prendre tous les caractères du sixième à la fin de la ligne :
De même, la parenthèse fermante peut être placée aux positions {1,3,5,7,9,11,13,15,17,20}. Les deux derniers chiffres gâchent toute la framboise, toutes les autres positions diffèrent les unes des autres par deux, et 17 et 20 par trois. Par conséquent, il ne sera pas possible de simplement déclarer une variable contenant le numéro de position de la parenthèse fermante et d'augmenter sa valeur de deux à chaque étape suivante. Nous stockerons les valeurs de position dans des tableaux :
int[] left ={0,2,4,6,8,10,12,14,16,18};
int[] right ={1,3,5,7,9,11,13,15,17,20};
Et nous augmenterons la variable d'index de un à chaque itération de la boucle chargée d'énumérer les options. Au total, deux parenthèses ouvrantes et deux fermantes sont nécessaires, respectivement, quatre variables d'index sont requises :
int indLeft1, indLeft2, indRight1, indRight2;
Les parenthèses dans une expression peuvent être placées de deux manières :
()()(())
Pour chaque méthode, vous devez écrire votre propre algorithme ; considérez l’algorithme de la première méthode de disposition des parenthèses. L'énumération réelle des options est représentée par des boucles for imbriquées :
Faites attention à la particularité de la méthode substring() de la classe String. Une sous-chaîne est sélectionnée dont le numéro du premier caractère est égal au premier paramètre et le numéro du dernier est égal au deuxième paramètre moins un . voir https://docs.oracle.com/javase/10/docs/api/java/lang/String.html#substring(int,int) , il existe même des exemples donnés pour réduire les malentendus. Après avoir formé une chaîne avec des parenthèses, nous calculons la valeur et la comparons avec celle requise :
int result = PPN.eval(s2);if(result ==537)System.out.println(s2);
Le bloc pour la disposition imbriquée des parenthèses est écrit de la même manière. La seule chose sur laquelle je veux attirer l'attention est que lorsque les parenthèses sont imbriquées, les parenthèses ouvrantes ou fermantes peuvent être dans la même position, par exemple
1+((2*3+4*5+6)*7+8*9+10)
ou
(1+2*(3+4*5+6*7+8))*9+10
En fait, c'est tout. Après le lancement, un programme correctement écrit produit une seule réponse : 1+2*(3+4*(5+6*7)+8*9)+10
GO TO FULL VERSION