Учитывая набор цифр и операторов, сформируйте данное число, используя наименьшее количество операций - PullRequest
Новая
       37

Учитывая набор цифр и операторов, сформируйте данное число, используя наименьшее количество операций

0 голосов
/ 15 января 2019

Нам задали следующую проблему в тесте, и я не знаю, как к ней подойти:

Учитывая набор чисел и набор операторов, найдите наименьшее число возможных операций для генерации числа.

Например:
Ввод
set of digits: {8, 1, 6, 2, 7}
set of operations: {*, /, -}
number to be generated: 981

Выход
number of operations: 2

Explanation: 981 = 16 * 62 - 11 [ 2 operations: * and - ]

Ограничения:
all numbers to be used as integers
0 <= each number in set of digits <= 9
possible set of operations: { +, -, *, / } [ the division operation will always return an integer ]
0 <= number to be generated <= 999
it is necessary that while performing the operations, any of the calculated values must not exceed 999 or be negative
the precedence of operations will always be from left to right, BODMAS/PEMDAS won't be followed. For example: 16*6+2*11 will be calculated as: ((16*6) + 2) * 11

Любая помощь в подходе к решению будет принята с благодарностью.

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

Не удалось написать много кода, так как я не уверен, как подойти к решению.

Заранее спасибо!

1 Ответ

0 голосов
/ 15 января 2019

Мы можем рассматривать эту проблему как проблему с графом и решать ее с помощью BFS.

Сначала мы пытаемся создать все возможные номера из set of numbers без использования какого-либо оператора, вызываем этот базовый набор. Это может быть легко достигнуто путем разложения каждого числа на цифры и проверки того, что все эти цифры принадлежат set of numbers. 

for (int i = 0; i < 1000; i++){
   if i can be formed by set of numbers {
      add i to base set;
   } 
}

Теперь, начиная с каждого числа в базовом наборе в качестве начальных вершин, мы переходим к следующим вершинам, применяя другой оператор к базовому набору 

Queue q = base set
int[] distance = new int[1000]; 
while q is not empty{
   int number = q.pop();
   for(int i : base set){
      for(operator : set of operators) {
          int next = number operator i
          if next < 1000 && next >= 0 && next not visited {
              mark next as visited;
              distance[next] = 1 + distance[number];
              q.add(next);
          } 

      }
   }

} 
return distance[target];

Каждая вершина будет посещена один раз, поэтому сложность по времени будет O(n ^ 2 * m), при этом n - это максимальное количество вершин (в данном случае 1000), а m - это число операторов

.
...