Dado un número N y un dígito D, tenemos que formar una expresión o ecuación que contenga solo D y esa expresión se evalúe como N. Los operadores permitidos en una expresión son +, -, * y / . Encuentre la expresión de longitud mínima que satisfaga la condición anterior y D solo puede aparecer en la expresión como máximo 10 veces (límite). Por lo tanto, limite los valores de N (aunque el valor del límite depende de qué tan lejos quiera llegar, pero un valor grande del límite puede llevar más tiempo para el enfoque a continuación). Recuerde, puede haber más de una expresión mínima de D que se evalúe como N, pero la longitud de esa expresión será mínima. Ejemplos:
Input : N = 7, D = 3 Output : 3/3+ 3 + 3 Explanation : 3/3 = 1, and 1+3+3 = 7 This is the minimum expression. Input : N = 7, D = 4 Output : (4+4+4)/4 + 4 Explanation : (4+4+4) = 12, and 12/4 = 3 and 3+4 = 7 Also this is the minimum expression. Although you may find another expression but that expression can have only five 4's Input : N = 200, D = 9 Output : Expression not found! Explanation : Not possible within 10 digits.
El enfoque que utilizamos es Backtracking . Comenzamos con el Dígito D dado y comenzamos a multiplicar, sumar, restar y dividir si es posible. Este proceso se realiza hasta que encontramos el total como N o llegamos al final y retrocedemos para iniciar otro camino. Para encontrar la expresión mínima, encontramos el nivel mínimo del árbol recursivo. Y luego aplique nuestro algoritmo de retroceso. Digamos N = 7, D = 3 
El enfoque anterior es exponencial. En cada nivel recursimos de 4 maneras más (como máximo). Entonces, podemos decir que la complejidad temporal del método es 
donde n es el número de niveles en el árbol recursivo (o podemos decir el número de veces que queremos que D aparezca como máximo en la expresión, que en nuestro caso es 10) . Nota: Usamos el enfoque anterior dos veces. Primero para encontrar el nivel mínimo y luego para encontrar la expresión que es posible en ese nivel. Entonces, tenemos dos pases en este enfoque. Podemos obtener la expresión de una sola vez, pero tendrás que rascarte la cabeza para eso.
C++
// CPP Program to generate minimum expression containing
// only given digit D that evaluates to number N.
#include <climits>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
// limit of Digits in the expression
#define LIMIT 10
using namespace std;
// map that store if a number is seen or not
map<int, int> seen;
// stack for storing operators
stack<char> operators;
int minimum = LIMIT;
// function to find minimum levels in the recursive tree
void minLevel(int total, int N, int D, int level) {
// if total is equal to given N
if (total == N) {
// store if level is minimum
minimum = min(minimum, level);
return;
}
// if the last level is reached
if (level == minimum)
return;
// if total can be divided by D.
// recurse by dividing the total by D
if (total % D == 0)
minLevel(total / D, N, D, level + 1);
// recurse for total + D
minLevel(total + D, N, D, level + 1);
// if total - D is greater than 0
if (total - D > 0)
// recurse for total - D
minLevel(total - D, N, D, level + 1);
// recurse for total multiply D
minLevel(total * D, N, D, level + 1);
}
// function to generate the minimum expression
bool generate(int total, int N, int D, int level) {
// if total is equal to N
if (total == N)
return true;
// if the last level is reached
if (level == minimum)
return false;
// if total is seen at level greater than current level
// or if we haven't seen total before. Mark the total
// as seen at current level
if (seen.find(total) == seen.end() ||
seen.find(total)->second >= level) {
seen[total] = level;
int divide = INT_MAX;
// if total is divisible by D
if (total % D == 0) {
divide = total / D;
// if divide isn't seen before
// mark it as seen
if (seen.find(divide) == seen.end())
seen[divide] = level + 1;
}
int addition = total + D;
// if addition isn't seen before
// mark it as seen
if (seen.find(addition) == seen.end())
seen[addition] = level + 1;
int subtraction = INT_MAX;
// if D can be subtracted from total
if (total - D > 0) {
subtraction = total - D;
// if subtraction isn't seen before
// mark it as seen
if (seen.find(subtraction) == seen.end())
seen[subtraction] = level + 1;
}
int multiply = total * D;
// if multiply isn't seen before
// mark it as seen
if (seen.find(multiply) == seen.end())
seen[multiply] = level + 1;
// recurse by dividing the total if possible
if (divide != INT_MAX)
if (generate(divide, N, D, level + 1)) {
// store the operator.
operators.push('/');
return true;
}
// recurse by adding D to total
if (generate(addition, N, D, level + 1)) {
// store the operator.
operators.push('+');
return true;
}
// recurse by subtracting D from total
if (subtraction != INT_MAX)
if (generate(subtraction, N, D, level + 1)) {
// store the operator.
operators.push('-');
return true;
}
// recurse by multiplying D by total
if (generate(multiply, N, D, level + 1)) {
// store the operator.
operators.push('*');
return true;
}
}
// expression is not found yet
return false;
}
// function to print the expression
void printExpression(int N, int D) {
// find minimum level
minLevel(D, N, D, 1);
// generate expression if possible
if (generate(D, N, D, 1)) {
// stringstream for converting to D to string
ostringstream num;
num << D;
string expression;
// if stack is not empty
if (!operators.empty()) {
// concatenate D and operator at top of stack
expression = num.str() + operators.top();
operators.pop();
}
// until stack is empty
// concatenate the operator with parenthesis for precedence
while (!operators.empty()) {
if (operators.top() == '/' || operators.top() == '*')
expression = "(" + expression + num.str() + ")" + operators.top();
else
expression = expression + num.str() + operators.top();
operators.pop();
}
expression = expression + num.str();
// print the expression
cout << "Expression: " << expression << endl;
}
// not possible within 10 digits.
else
cout << "Expression not found!" << endl;
}
// Driver's Code
int main() {
int N = 7, D = 4;
// print the Expression if possible
printExpression(N, D);
// print expression for N =100, D =7
minimum = LIMIT;
printExpression(100, 7);
// print expression for N =200, D =9
minimum = LIMIT;
printExpression(200, 9);
return 0;
}
Java
// Java Program to generate minimum expression containing
// only given digit D that evaluates to number N.
import java.util.HashMap;
import java.util.Stack;
public class SingleDigit {
// limit of Digits in the expression
static int LIMIT = 10;
// map that store if a number is seen or not
static HashMap<Integer, Integer> seen
= new HashMap<Integer, Integer>();
// stack for storing operators
static Stack<Character> operators
= new Stack<Character>();
static int minimum = LIMIT;
// function to find minimum levels in the recursive tree
static void minLevel(int total, int N, int D, int level)
{
// if total is equal to given N
if (total == N) {
// store if level is minimum
minimum = Math.min(minimum, level);
return;
}
// if the last level is reached
if (level == minimum)
return;
// if total can be divided by D.
// recurse by dividing the total by D
if (total % D == 0)
minLevel(total / D, N, D, level + 1);
// recurse for total + D
minLevel(total + D, N, D, level + 1);
// if total - D is greater than 0
if (total - D > 0)
// recurse for total - D
minLevel(total - D, N, D, level + 1);
// recurse for total multiply D
minLevel(total * D, N, D, level + 1);
}
// function to generate the minimum expression
static boolean generate(int total, int N, int D,
int level)
{
// if total is equal to N
if (total == N)
return true;
// if the last level is reached
if (level == minimum)
return false;
// if total is seen at level greater than current
// level or if we haven't seen total before. Mark
// the total as seen at current level
if ((seen.containsKey(total)
&& seen.get(total) >= level)
|| !seen.containsKey(total)) {
seen.put(total, level);
int divide = Integer.MAX_VALUE;
// if total is divisible by D
if (total % D == 0) {
divide = total / D;
// if divide isn't seen before
// mark it as seen
if (seen.containsKey(divide))
seen.put(divide, level + 1);
}
int addition = total + D;
// if addition isn't seen before
// mark it as seen
if (seen.containsKey(addition))
seen.put(addition, level + 1);
int subtraction = Integer.MAX_VALUE;
// if D can be subtracted from total
if (total - D > 0) {
subtraction = total - D;
// if subtraction isn't seen before
// mark it as seen
if (seen.containsKey(subtraction))
seen.put(subtraction, level + 1);
}
int multiply = total * D;
// if multiply isn't seen before
// mark it as seen
if (seen.containsKey(multiply))
seen.put(multiply, level + 1);
;
// recurse by dividing the total if possible
if (divide != Integer.MAX_VALUE)
if (generate(divide, N, D, level + 1)) {
// store the operator.
operators.push('/');
return true;
}
// recurse by adding D to total
if (generate(addition, N, D, level + 1)) {
// store the operator.
operators.push('+');
return true;
}
// recurse by subtracting D from total
if (subtraction != Integer.MAX_VALUE)
if (generate(subtraction, N, D,
level + 1)) {
// store the operator.
operators.push('-');
return true;
}
// recurse by multiplying D by total
if (generate(multiply, N, D, level + 1)) {
// store the operator.
operators.push('*');
return true;
}
}
// expression is not found yet
return false;
}
// function to print the expression
static void printExpression(int N, int D)
{
// find minimum level
minLevel(D, N, D, 1);
// generate expression if possible
if (generate(D, N, D, 1)) {
String expression = "";
// if stack is not empty
if (!operators.empty()) {
// concatenate D and operator at top of
// stack
expression = Integer.toString(D)
+ operators.peek();
operators.pop();
}
// until stack is empty
// concatenate the operator with parenthesis for
// precedence
while (!operators.empty()) {
if (operators.peek() == '/'
|| operators.peek() == '*')
expression = "(" + expression
+ Integer.toString(D) + ")"
+ operators.peek();
else
expression = expression
+ Integer.toString(D)
+ operators.peek();
operators.pop();
}
expression = expression + Integer.toString(D);
// print the expression
System.out.println("Expression: " + expression);
}
// not possible within 10 digits.
else
System.out.println("Expression not found!");
}
// Driver's Code
public static void main(String[] args)
{
int N = 7, D = 4;
// print the Expression if possible
printExpression(N, D);
// print expression for N =100, D =7
minimum = LIMIT;
printExpression(100, 7);
// print expression for N =200, D =9
minimum = LIMIT;
printExpression(200, 9);
}
}
// This code is contributed by Lovely Jain
Python3
# Python3 program to generate minimum expression containing
# only the given digit D that evaluates to number N.
LIMIT = 10
# to restrict the maximum number of times
# the number D can be used to obtain N
minimum = LIMIT
# to store the value of intermediate D
# and the D of operands used to get that intermediate D, ie
# seen[intermediateNumber] = numberOfOperandsUsed
seen = {}
# stack to store the operators used to print the expression
operators = []
# function to obtain minimum D of operands in recursive tree
def minLevel(total, N, D, level):
global minimum
# if total is equal to given N
if total == N:
# store if D of operands is minimum
minimum = min(minimum, level)
return
# if the last level (limit) is reached
if level == minimum:
return
# if total can be divided by D, recurse
# by dividing the total by D
if total % D == 0:
minLevel(total / D, N, D, level + 1)
# recurse for total + D
minLevel(total + D, N, D, level + 1)
# if total - D is greater than 0, recurse for total - D
if total - D > 0:
minLevel(total - D, N, D, level + 1)
# recurse for total * D
minLevel(total * D, N, D, level + 1)
# function to generate the minimum expression
def generate(total, N, D, level):
# if total is equal to N
if total == N:
return True
# if the last level is reached
if level == minimum:
return False
# if the total is not already seen or if
# the total is seen with more level
# then mark total as seen with current level
if seen.get(total) is None or seen.get(total) >= level:
seen[total] = level
divide = -1
# if total is divisible by D
if total % D == 0:
divide = total / D
# if the number (divide) is not seen, mark as seen
if seen.get(divide) is None:
seen[divide] = level + 1
addition = total + D
# if the number (addition) is not seen, mark as seen
if seen.get(addition) is None:
seen[addition] = level + 1
subtraction = -1
# if D can be subtracted from total
if total - D > 0:
subtraction = total - D
# if the number (subtraction) is not seen, mark as seen
if seen.get(subtraction) is None:
seen[subtraction] = level + 1
multiplication = total * D
# if the number (multiplication) is not seen, mark as seen
if seen.get(multiplication) is None:
seen[multiplication] = level + 1
# recurse by dividing the total if possible and store the operator
if divide != -1 and generate(divide, N, D, level + 1):
operators.append('/')
return True
# recurse by adding D to total and store the operator
if generate(addition, N, D, level + 1):
operators.append('+')
return True
# recurse by subtracting D from total
# if possible and store the operator
if subtraction != -1 and generate(subtraction, N, D, level + 1):
operators.append('-')
return True
# recurse by multiplying D by total and store the operator
if generate(multiplication, N, D, level + 1):
operators.append('*')
return True
# expression is not found yet
return False
# function to print the expression
def printExpression(N, D):
# find the minimum number of operands
minLevel(D, N, D, 1)
# generate expression if possible
if generate(D, N, D, 1):
expression = ''
# if stack is not empty, concatenate D and
# operator popped from stack
if len(operators) > 0:
expression = str(D) + operators.pop()
# until stack is empty, concatenate the
# operator popped with parenthesis for precedence
while len(operators) > 0:
popped = operators.pop()
if popped == '/' or popped == '*':
expression = '(' + expression + str(D) + ')' + popped
else:
expression = expression + str(D) + popped
expression = expression + str(D)
print("Expression: " + expression)
# not possible within 10 digits.
else:
print("Expression not found!")
# Driver's code
if __name__ == '__main__':
# N = 7, D = 4
minimum = LIMIT
printExpression(7, 4)
minimum = LIMIT
printExpression(100, 7)
minimum = LIMIT
printExpression(200, 9)
# This code is contributed by thecodingpanda
Producción:
Expression: (4+4+4)/4+4 Expression: (((7+7)*7)*7+7+7)/7 Expression not found!
Publicación traducida automáticamente
Artículo escrito por shubham_rana_77 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA