Comment représenter un nombre avec des nombres donnés en utilisant des opérations arithmétiques?

Question

Ceci est un interview question. "Etant donné un tableau de nombres et un autre nombre, déterminer si le tableau de nombres peut être manipulé en utilisant des techniques mathématiques standard pour égaler l'autre nombre donné.Par exemple donné 5 et 10, pouvez-vous faire 50? 5 * 10 = 50, donc oui ". (Supposons seulement des opérations arithmétiques pour la simplicité).

Je proposerais d'utiliser une recherche en force brute (avec une branche et une borne). Est-ce que ça fait du sens ?

Answer 1

Programmation dans Haskell, Chapitre 11: Le problème du compte à rebours

Answer 2

La force brute semble être une façon valable d'aborder cela. Mais la force brute est une recherche non informée ... elle ne fait pas de suppositions éclairées sur le chemin à suivre lorsque vous atteignez une branche dans l'arbre de recherche.

Ce que vous voudrez peut-être examiner, c'est s'il y a heuristic functions qui peut vous aider à faire votre recherche informé. Une fonction heuristique se penche sur un état et donne une estimation de la distance qui vous sépare du but. Si vous pouvez trouver une fonction heuristique valide, vous pouvez appliquer un algorithme tel que A*.

Soyez averti: cela ne semble pas être un problème facile pour définir une heuristique.

Answer 3

Je pense que cela a du sens.

Vous pouvez profiter de la symétrie entre la multiplication pour tailler davantage votre arborescence. a * b = b * a.

Answer 4

Je demande

• -ce que les Numbers entiers?
• Existe-t-il une limite supérieure à l'échelle des nombres?
• Quels sont les standard mathematical techniques?
  • seulement simple arithmétique?
  • racines, puissances?
  • réciproques?
  • fonctions trigonométriques?

etc

Answer 5

Une autre façon de résoudre ce serait à l'aide genetic algorithms. Votre population commencerait comme des opérateurs aléatoires insérés entre les éléments de votre tableau.

Soit S soit le numéro que vous devez obtenir. Votre fonction de remise en forme peut être |S - Value(E[i])|, où Value(E[i]) est la valeur après avoir évalué l'expression i -th dans votre population. Votre opérateur de mutation pourrait simplement changer un opérateur à un autre, et votre fonction de croisement pourrait combiner les opérateurs de la gauche d'une expression avec ceux de la droite d'une autre expression. Peut-être que vous pouvez trouver des fonctions plus sophistiquées qui fonctionnent mieux, les algorithmes génétiques nécessitent un peu de conjecture pour de meilleurs résultats.Je n'ai aucune idée de comment cela se comparerait à la force brute, mais c'est une solution différente et je pense que cela vous fera ressortir dans une interview, puisque tout le monde sera capable de voir la solution de force brute.

Si vous avez seulement besoin d'une solution assez bonne (quelque chose qui n'est pas exactement S, mais assez proche), alors ceci devrait certainement être plus rapide que la force brute. Dans les quelques algorithmes génétiques que j'ai implémentés, j'ai remarqué qu'ils abordaient rapidement une solution proche de l'optimum, mais plutôt lente et parfois même bloquée si vous voulez la solution optimale.

Answer 6

Une première question très importante est: Est-ce que des opérations unaires sont autorisées? Autrement dit, puis-je changer x en -x, 1/x, x !, ou sqrt (x) "gratuitement"?

Si oui, une recherche ramifiée naïve ne se terminera pas, car il n'y a pas de limite a priori sur le nombre d'utilisations des opérations unaires. Sinon, une recherche naïve peut très bien fonctionner.

Voici une stratégie amusante, sinon efficace: demander ou produire une grammaire BNF pour l'arithmétique utilisée. Pirater dans une règle comme

< unité> :: = 5 | 10

puis d'utiliser cette grammaire pour développer toutes les expressions possibles obtenues en utilisant, disons, moins de 20 règles grammaticales. Evaluez-les tous. Cela sera garanti d'être borné, et générera toutes les expressions "pas trop complexes" valides dans la langue.