Le problème d'origine est ici: [Cinq problèmes de programmation que chaque ingénieur logiciel devrait être capable de résoudre en moins d'une heure](https://blog.svpino.com/2015/05/07/five-programming-problems-every- l'ingénieur-logiciel-devrait-être-capable-de-résoudre-en-moins-d'une-heure) Traduction japonaise: 5 problèmes qui disqualifieront un programmeur s'ils ne sont pas résolus en 1 heure
J'ai essayé de contester le problème 5 de ceux-ci avec Python.
Définissez la fonction f (n, M) comme une fonction qui renvoie toutes les manières dont le résultat du calcul est M, en utilisant des nombres de 1 à n (les valeurs de retour sont une liste). Alors la réponse que vous voulez est f (9, 100). Premièrement, si le calcul fonctionne tel quel (exemple: n = 3, M = 123), l'une des réponses est M sous forme de chaîne de caractères. De plus, f (n, M) peut être décomposé en n plus petit. Vous pouvez retrouver toutes les méthodes de calcul en répétant la décomposition de manière récursive.
Premièrement, la formule ne tient pas telle quelle (123 ≠ 9). f (3, 9) peut être décomposé des quatre façons suivantes (généralement, il existe (n-1) * 2 façons de décomposition). f(2, 6) "+3" f(2, 12) "-3" f(1, -14) "+23" f(1, 32) "-23"
Parmi ceux-ci, f (1, -14) et f (1, 32) ne peuvent plus être décomposés, et l'équation ne tient pas en l'état, ils ne conviennent donc pas. f (2, 6) peut être encore décomposé en f (1, 5) "+1" et f (1, 7) "-1", mais aucune des équations n'est valable. Puisque f (2, 12) est un modèle dans lequel l'équation est vraie, "12" est une solution. En outre, il peut être décomposé en f (1, 11) "+1" et f (1, 13) "-1", mais aucun n'est approprié. Par conséquent, "12-3" est recherché comme la seule solution.
Lorsque f (9, 100) est calculé, 11 modèles présentés par l'interrogateur (Solution to Problem 5 -certaines-autres-pensées-sur-ce-type-de-questions)) a la même solution.
Cependant, utiliser une telle fonction récursive est un peu désagréable, et dans le cas de Python, une erreur d'exécution se produira si la profondeur récursive dépasse 1000 (Référence. % 20script /% E3% 82% A2% E3% 82% A4% E3% 83% 87% E3% 83% B3% E3% 83% 86% E3% 82% A3% E3% 83% 86% E3% 82% A3)). Dans cet exemple, la profondeur ne dépasse pas 9, donc ça va. De plus, dans l'exemple de réponse, c'était un mécanisme qui peut gérer des nombres autres que 1 à 9, mais il est faible que je ne puisse pas le faire avec ma méthode.
def fun5(n, M):
digits = "123456789"[0:n]
out = []
if int(digits) == M:
out += [ digits ]
for i in xrange(1, n):
out += map(lambda z: z + "+" + digits[-i:n], fun5(n - i, M - int(digits[-i:n])) )
out += map(lambda z: z + "-" + digits[-i:n], fun5(n - i, M + int(digits[-i:n])) )
return out
print fun5(2, 3)
print fun5(5, 168)
print fun5(9, 100)
#['1+2']
#['123+45']
#['1+23-4+56+7+8+9', '12+3-4+5+67+8+9', '1+2+34-5+67-8+9', '1+2+3-4+5+6+78+9', '123-4-5-6-7+8-9', '123+45-67+8-9', '1+23-4+5+6+78-9', '12-3-4+5-6+7+89', '12+3+4+5-6-7+89', '123-45-67+89', '123+4-5+67-89']