Ecrivez une fonction qui donne une chaîne de chiffres et une valeur cible, imprime où placer les + et les * entre les chiffres afin qu'ils se combinent exactement à la valeur cible. Notez qu'il peut y avoir plus d'une réponse, peu importe celle que vous imprimez.algorithme de combinaison de nombres
Exemples:
"1231231234",11353 -> "12*3+1+23*123*4"
"3456237490",1185 -> "3*4*56+2+3*7+490"
"3456237490",9191 -> "no solution"
Ceci peut être résolu soit par retours en arrière ou par programmation dynamique.
Si vous avez une valeur numérique N, il y a N-1 emplacements possibles pour les opérateurs + ou *. Donc force brute, il y a 3^(N-1) possibilités. Tester tout cela est inefficace.
MAIS
Vos exemples sont les 10 chiffres. 3^9 = 19683, donc la force brute est FINE! Pas besoin d'avoir un colombophile.
Il ne vous reste plus qu'à parcourir tous les cas de 19683, en construisant une chaîne pour chaque cas et en évaluant l'expression. L'évaluation de l'expression est une tâche simple. L'itération est simple (il suffit d'utiliser une valeur incrémentée, vous pouvez lire l'état du premier emplacement par (i% 3), ce qui vous donne "aucun opérateur" "+" ou "*", l'état du second emplacement est (i/3)% 3, l'état du troisième emplacement est (i/9)% 3 et ainsi de suite.)
Même avec un code d'analyse brut, les processeurs sont rapides. L'option de force brute commence à devenir laide après environ 20 chiffres, et vous devriez changer pour être plus intelligent.
L'approche « plus intelligent » (en utilisant la programmation dynamique) est essentiellement ceci:
Pour chaque sous-chaîne de la chaîne d'origine, comprendre toutes les valeurs possibles qu'il peut créer. (Par exemple dans votre premier exemple "12" peut devenir 1 + 2 = 3 ou 1 * 2 = 2)
Il peut y avoir beaucoup de combinaisons différentes, mais beaucoup d'entre elles seront des doublons. (De même, vous devez ignorer toutes les combinaisons supérieures à la cible). Ainsi, lorsque vous ajoutez un "+" ou un "*", vous pouvez l'envisager comme combinant deux sous-chaînes de la chaîne. (et puisque vous avez les valeurs possibles pour chaque sous-chaîne, vous pouvez voir si une telle combinaison est possible)
Ces valeurs peuvent être générées de manière similaire: essayez de diviser la sous-chaîne de toutes les manières possibles, et combinez les différentes valeurs dans chaque moitié de la sous-chaîne. Le nombre total de "states", alors, est quelque chose comme | S |^2 * target - pour votre exemple, c'est pire que la méthode brute-force. Mais si vous aviez une chaîne de 1000 et une cible de 5000, le problème serait résolu avec la programmation dynamique.
Google Code Jam avait une version étendue de ce problème l'année dernière (en Round 1C), appelé Ugly Numbers. Vous pouvez visiter ce lien et cliquer sur "Analyse du concours" pour certaines approches de ce problème, lorsqu'il est étendu à un grand nombre de chiffres.
S'il s'agit de la position du programmateur de jeu, n'utilisez pas l'approche par force brute. Je l'ai fait mais j'ai échoué il y a quelques années. Plus tard, quelqu'un de l'intérieur de cette approche de programmation dynamique est celui qui obtient le travail.
+1 pour estimer le basculement entre la force brute et l'intelligence. – RBerteig