Из 6 случайных чисел вычисляет случайное трехзначное число?

Question

У меня 4 года опыта работы с PHP и C#, но математика не моя лучшая сторона. I thnik, который мне нужен в этом проекте, использует некоторые математические алгоритмы.

При загрузке страницы мне нужно случайным образом создать 7 номеров, 6 номера, которые я могу использовать, чтобы вычислить заданное число три цифры:

• рандов 1-9
• рэнд 1-9
• рэнд 1 -9
• рэнд 1-9
• рэнд 10-100 // 5 шагов
• рэнд 10-100 // 5 шагов

и дали номер для расчета является 100-999,

Я могу использовать эти операции: +, -, /, *, (,)

Что такое лучший алгоритм для этого? Возможно, мне нужно попробовать все возможные комбинации с этими 6 числами, чтобы вычислить заданное число или самое близкое число вычислений.

пример: скажем, что дано трехзначное число 350, и мне нужно вычислить это число от этого числа: 3,6,9,5 10, 100 так формула для этого: (100 * 3) + (5 * 10) = 350

если невозможно рассчитать точное число, чем рассчитать ближайший.

Вам не нужно полностью решать эту проблему, вы можете представить меня, чтобы решить эту проблему, вставив какое-то псевдо или описав, как это сделать.

Answer 1

У меня нет фактического опыта, который мог бы помочь вам в этом, хотя, поскольку вы просите о каком-то прозрении, я поделюсь своими мыслями о том, как это сделать.

Как я набрал свой ответ, я понял, что на самом деле это knapsack problem, что означает, что вы можете решить его оптимально, используя любой алгоритм, который решает проблему ранца. Я рекомендую использовать dynamic programming, чтобы ваша программа работала быстрее.

Что вам нужно сделать, это построить все числа, которые вы можете сгенерировать, объединив два числа с оператором, так что после этого у вас есть список, содержащий номера, с которых вы начали, и числа, которые вы создали.

Затем вы решаете проблему с рюкзаком, используя цифры в качестве предметов со своим значением в качестве их веса, а количество в качестве веса, которое вы можете хранить максимум.

Единственное, что немного отличается, это то, что у вас есть дополнительное ограничение, в котором говорится, что вы можете использовать только один раз. Поэтому вам нужно добавить в свою реализацию, что если вы добавите комбинацию чисел, вы должны удалить опцию сохранения другой комбинации, построенной с тем же номером.

Answer 2

Вы могли бы перечислить все решения путем создания «Абстрактные синтаксические деревья», бинарные деревья со следующими информация:

• листья являются 6 номеров

• узлы являются операции, для например, узел «+» с листом «7» для левого сына и другой узел для правого сына, который равен «x» с «140» для левого сына и «8» для правого сына, будет представлять (7+ (140 * 8)). Кроме того, на каждом узле вы сохраняете числа, которые вы уже использовали (листья, используемые в дереве), и общее количество.

Предположим, что вы сохранили все построенные деревья в ассоциативной карте TreeSets, но проиндексированы количеством листов, которые вы используете. Например, дерево (7+ (140 * 8)) не будет храниться непосредственно в TreeSets, но в TreeSets [3] (TreeSets [3] содержит несколько деревьев, это также набор).

Вы храните самый близкий счет в BestScore и одно из решений BestScore в BestSolution.

Вы начинаете с создания 6 листов (что делает вас 6 разных деревьев, состоящих только из одного листа). Вы сохраняете более близкое число в Bestscore и соответствующий лист в BestSolution.

Затем на каждом шаге вы пытаетесь построить деревья с i листьями, i от 2 до 6 и сохранить их в TreeSets [i].

Вы берете j от 1 до i-1, вы берете каждое дерево в TreeSets [j] и каждое дерево в TreeSets [ij], вы проверяете, что эти два дерева не используют одни и те же листья (вы не нужно проверить в нижней части дерева, так как вы сохранили листья, используемые в узле), если так вы построите четыре узла «+», «x», «/», «-» с деревом из TreeSets [j ] как левый сын и дерево из TreeSets [ij] и сохраните все четыре из них в TreeSets [i]. При создании узла вы берете общее количество из обоих деревьев и применяете операцию, вы храните общее количество, и вы проверяете, ближе ли он к лучшему (если вы обновляете BestScore и BestSolution с этим новым итогом и с новым узлом). Если общая сумма - это именно то значение, которое вы искали, вы можете остановиться здесь.

Если вы не остановили программу, найдя точное решение, такого решения не будет, и чем ближе в BestSolution в конце.

Примечание: вам не нужно создавать полное дерево каждый раз, просто создайте узел с двумя указателями на других деревьях.

P.S. : Вы можете избежать перечисления всех решений, используя подход динамического программирования, как сказал Глубус. В этом случае на каждом шаге (i) будет заключаться удаление некоторых решений, которые считаются субоптимальными. Но с этой проблемой я не уверен, что это возможно (за исключением, возможно, удалить узлы с общим числом 0).