Ordene los números dados en una expresión matemática usando operadores [+, -, *, /] y paréntesis para obtener el valor 24

Dada una array arr[] que consta de 4 enteros cada uno entre [1-9] , la tarea es comprobar si es posible obtener el número 24 colocando los operadores + , , / y * entre los números o agrupándolos utilizando paréntesis. Si es posible, imprima » Posible «, de lo contrario imprima » No posible». 

Ejemplos:

Entrada: arr[] = {3, 6, 8, 2}
Salida: Posible
explicación: 
Una forma posible de obtener 24 es 3 × 6 + 8 – 2 = 24.

Entrada: arr[] = {7, 2, 10, 6}
Salida: Posible
explicación:
Una forma posible de obtener 24 es (7 × 2–10) x 6 = 24.

Enfoque: La idea más simple para resolver este problema se basa en retroceder . Siga los pasos a continuación para resolver el problema:

  • Cree una función, digamos isNumber24Possible(arr[]) y aplique las cuatro operaciones entre cada elemento consecutivo y llame recursivamente a la función digamos isNumber24PossibleUtil(op1, op2, op3) que realiza todas las operaciones posibles en 3 números.
  • La función isNumber24PossibleUtil(op1, op2, op3) aplica las cuatro operaciones entre cada elemento consecutivo y llama a la función sobrecargada isNumber24PossibleUtil(op1, op2) que aplica la operación en 2 números.
  • La función isNumber24PossibleUtil(op1, op2) se usa para verificar si los dos números dados pueden reducirse a 24 usando cualquiera de las 4 operaciones, es decir , + , , / y * . Pruebe todas las operaciones entre los números, si alguno de ellos da como resultado 24 , devuelva verdadero ; de lo contrario, devuelva falso .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Division operation might loose some
// precision consider 0.001 as tolerance.
#define TOLERANCE 0.001
 
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
bool isNumber24PossibleUtil(double op1, double op2)
{
    // Check if any of the operation result to 24
    if (abs(op1 + op2 - 24.0) < TOLERANCE
        || abs(op1 - op2 - 24.0) < TOLERANCE
        || abs(op1 * op2 - 24.0) < TOLERANCE
        || op2 && abs(op1 / op2 - 24.0) < TOLERANCE)
        return true;
    return false;
}
 
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
bool isNumber24PossibleUtil(double op1, double op2, double op3)
{
    // Applying operation between two operands reduces
    // the count of operands to two
    if (isNumber24PossibleUtil(op1 + op2, op3)
        || isNumber24PossibleUtil(op1 - op2, op3)
        || isNumber24PossibleUtil(op1 * op2, op3)
        || op2 && isNumber24PossibleUtil(op1 / op2, op3))
        return true;
    if (isNumber24PossibleUtil(op1, op2 + op3)
        || isNumber24PossibleUtil(op1, op2 - op3)
        || isNumber24PossibleUtil(op1, op2 * op3)
        || op3 && isNumber24PossibleUtil(op1, op2 / op3))
        return true;
    return false;
}
 
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
bool isNumber24Possible(int arr[])
{
    // Apply every operation between first two operands
    if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2], arr[3])
        || isNumber24PossibleUtil(arr[0] - arr[1], arr[2], arr[3])
        || isNumber24PossibleUtil(arr[0] * arr[1], arr[2], arr[3])
        || arr[1] && isNumber24PossibleUtil(arr[0] / arr[1], arr[2], arr[3]))
        return true;
    // Between second and third operands
    if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3])
        || isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3])
        || isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3])
        || arr[2] && isNumber24PossibleUtil(arr[0], arr[1] / arr[2], arr[3]))
        return true;
    // Between third and fourth operands
    if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3])
        || isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3])
        || isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3])
        || arr[3] && isNumber24PossibleUtil(arr[0], arr[1], arr[2] / arr[3]))
        return true;
 
    return false;
}
 
// Driver Code
int main()
{
    // Given Input
    int arr[] = { 3, 6, 8, 2 };
 
    // Function Call
    if (isNumber24Possible(arr)) {
        cout << "Possible" << endl;
    }
    else {
        cout << "Not Possible" << endl;
    }
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Division operation might loose some
// precision consider 0.001 as tolerance.
static double TOLERANCE = 0.001;
 
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
static boolean isNumber24PossibleUtil(double op1,
                                      double op2)
{
     
    // Check if any of the operation result to 24
    if (Math.abs(op1 + op2 - 24.0) < TOLERANCE ||
        Math.abs(op1 - op2 - 24.0) < TOLERANCE ||
        Math.abs(op1 * op2 - 24.0) < TOLERANCE ||
        op2 != 0 && Math.abs(op1 / op2 - 24.0) < TOLERANCE)
        return true;
    return false;
}
 
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
static boolean isNumber24PossibleUtil(double op1, double op2,
                                      double op3)
{
     
    // Applying operation between two operands reduces
    // the count of operands to two
    if (isNumber24PossibleUtil(op1 + op2, op3) ||
        isNumber24PossibleUtil(op1 - op2, op3) ||
        isNumber24PossibleUtil(op1 * op2, op3) ||
        op2 != 0 && isNumber24PossibleUtil(op1 / op2, op3))
        return true;
    if (isNumber24PossibleUtil(op1, op2 + op3) ||
        isNumber24PossibleUtil(op1, op2 - op3) ||
        isNumber24PossibleUtil(op1, op2 * op3) ||
        op3 != 0 && isNumber24PossibleUtil(op1, op2 / op3))
        return true;
         
    return false;
}
 
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
static boolean isNumber24Possible(int arr[])
{
     
    // Apply every operation between first two operands
    if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0] - arr[1], arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0] * arr[1], arr[2], arr[3]) ||
        arr[1] != 0 && isNumber24PossibleUtil(arr[0] / arr[1], arr[2],
                                              arr[3]))
        return true;
    // Between second and third operands
    if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) ||
        arr[2] != 0 && isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
                                              arr[3]))
        return true;
         
    // Between third and fourth operands
    if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) ||
        arr[3] != 0 && isNumber24PossibleUtil(arr[0], arr[1],
                                              arr[2] / arr[3]))
        return true;
 
    return false;
}
   
// Driver Code
public static void main(String[] args)
{
     
    // Given Input
    int arr[] = { 3, 6, 8, 2 };
     
    // Function Call
    if (isNumber24Possible(arr))
    {
        System.out.print("Possible");
    }
    else
    {
        System.out.print("Not Possible");
    }
}
}
 
// This code is contributed by code_hunt

Python3

# Python3 program for the above approach
 
# Division operation might loose some
# precision consider 0.001 as tolerance.
TOLERANCE = 0.001
 
# This function is used to check whether
# given two number can reduce to 24 using
# any of the 4 operations
def isNumber24PossibleUtill(op1, op2):
     
    # Check if any of the operation result to 24
    if (abs(op1 + op2 - 24.0) < TOLERANCE or
        abs(op1 - op2 - 24.0) < TOLERANCE or
        abs(op1 * op2 - 24.0) < TOLERANCE or
        op2 and abs(op1 / op2 - 24.0) < TOLERANCE):
        return True
         
    return False
 
# Function which applies all the possible operations
# in between all the parameters and call the function
# which check if given number can result in 24 or not
def isNumber24PossibleUtil(op1, op2, op3):
     
    # Applying operation between two operands reduces
    # the count of operands to two
    if ((isNumber24PossibleUtill(op1 + op2, op3)) or
        (isNumber24PossibleUtill(op1 - op2, op3)) or
        (isNumber24PossibleUtill(op1 * op2, op3)) or
        (op2 and isNumber24PossibleUtill(op1 / op2, op3))):
        return True
         
    if (isNumber24PossibleUtill(op1, op2 + op3) or
        isNumber24PossibleUtill(op1, op2 - op3) or
        isNumber24PossibleUtill(op1, op2 * op3) or
        op3 and isNumber24PossibleUtill(op1, op2 / op3)):
        return True
         
    return False
 
# Function takes given array as arr parameter
# and apply all possible operation in every
# consecutive elements and check if the remaining
# 3 parameters can be used for obtaining 24 or not
def isNumber24Possible(arr):
     
    # Apply every operation between first two operands
    if (isNumber24PossibleUtil(arr[0] + arr[1],
                               arr[2], arr[3]) or
        isNumber24PossibleUtil(arr[0] - arr[1],
                               arr[2], arr[3]) or
        isNumber24PossibleUtil(arr[0] * arr[1],
                               arr[2], arr[3]) or
                               arr[1] and
        isNumber24PossibleUtil(arr[0] / arr[1],
                               arr[2], arr[3])):
        return True
         
    # Between second and third operands
    if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) or
        isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) or
        isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) or
        arr[2] and isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
                                          arr[3])):
        return True
         
    # Between third and fourth operands
    if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) or
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) or
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) or
        arr[3] and isNumber24PossibleUtil(arr[0], arr[1],
                                          arr[2] / arr[3])):
        return True
 
    return False
 
# Driver Code
 
# Given Input
arr = [ 3, 6, 8, 2 ]
 
# Function Call
if (isNumber24Possible(arr)):
    print("Possible")
else:
    print("Not Possible")
 
# This code is contributed by sanjoy_62

C#

using System;
 
public class GFG {
 
    static double TOLERANCE = 0.001;
 
    // This function is used to check whether
    // given two number can reduce to 24 using
    // any of the 4 operations
    static bool isNumber24PossibleUtil(double op1,
                                          double op2)
    {
 
        // Check if any of the operation result to 24
        if (Math.Abs(op1 + op2 - 24.0) < TOLERANCE
            || Math.Abs(op1 - op2 - 24.0) < TOLERANCE
            || Math.Abs(op1 * op2 - 24.0) < TOLERANCE
            || op2 != 0
                   && Math.Abs(op1 / op2 - 24.0)
                          < TOLERANCE)
            return true;
        return false;
    }
 
    // Function which applies all the possible operations
    // in between all the parameters and call the function
    // which check if given number can result in 24 or not
    static bool isNumber24PossibleUtil(double op1,
                                          double op2,
                                          double op3)
    {
 
        // Applying operation between two operands reduces
        // the count of operands to two
        if (isNumber24PossibleUtil(op1 + op2, op3)
            || isNumber24PossibleUtil(op1 - op2, op3)
            || isNumber24PossibleUtil(op1 * op2, op3)
            || op2 != 0
                   && isNumber24PossibleUtil(op1 / op2,
                                             op3))
            return true;
        if (isNumber24PossibleUtil(op1, op2 + op3)
            || isNumber24PossibleUtil(op1, op2 - op3)
            || isNumber24PossibleUtil(op1, op2 * op3)
            || op3 != 0
                   && isNumber24PossibleUtil(op1,
                                             op2 / op3))
            return true;
 
        return false;
    }
 
    // Function takes given array as arr parameter
    // and apply all possible operation in every
    // consecutive elements and check if the remaining
    // 3 parameters can be used for obtaining 24 or not
    static bool isNumber24Possible(int[] arr)
    {
 
        // Apply every operation between first two operands
        if (isNumber24PossibleUtil(arr[0] + arr[1], arr[2],
                                   arr[3])
            || isNumber24PossibleUtil(arr[0] - arr[1],
                                      arr[2], arr[3])
            || isNumber24PossibleUtil(arr[0] * arr[1],
                                      arr[2], arr[3])
            || arr[1] != 0
                   && isNumber24PossibleUtil(
                       arr[0] / arr[1], arr[2], arr[3]))
            return true;
        // Between second and third operands
        if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2],
                                   arr[3])
            || isNumber24PossibleUtil(
                arr[0], arr[1] - arr[2], arr[3])
            || isNumber24PossibleUtil(
                arr[0], arr[1] * arr[2], arr[3])
            || arr[2] != 0
                   && isNumber24PossibleUtil(
                       arr[0], arr[1] / arr[2], arr[3]))
            return true;
 
        // Between third and fourth operands
        if (isNumber24PossibleUtil(arr[0], arr[1],
                                   arr[2] + arr[3])
            || isNumber24PossibleUtil(arr[0], arr[1],
                                      arr[2] - arr[3])
            || isNumber24PossibleUtil(arr[0], arr[1],
                                      arr[2] * arr[3])
            || arr[3] != 0
                   && isNumber24PossibleUtil(
                       arr[0], arr[1], arr[2] / arr[3]))
            return true;
 
        return false;
    }
    static public void Main()
    {
        int[] arr = { 3, 6, 8, 2 };
 
        // Function Call
        if (isNumber24Possible(arr)) {
            Console.WriteLine("Possible");
        }
        else {
            Console.WriteLine("Not Possible");
        }
    }
}
 
// This code is contributed by maddler.

Javascript

<script>
 
// JavaScript program to implement above approach
 
// Division operation might loose some
// precision consider 0.001 as tolerance.
const TOLERANCE = 0.001
 
// This function is used to check whether
// given two number can reduce to 24 using
// any of the 4 operations
function isNumber24PossibleUtill(op1, op2){
     
    // Check if any of the operation result to 24
    if (Math.abs(op1 + op2 - 24.0) < TOLERANCE ||
        Math.abs(op1 - op2 - 24.0) < TOLERANCE ||
        Math.abs(op1 * op2 - 24.0) < TOLERANCE ||
        op2 && Math.abs(op1 / op2 - 24.0) < TOLERANCE)
        return true
         
    return false
}
 
// Function which applies all the possible operations
// in between all the parameters and call the function
// which check if given number can result in 24 or not
function isNumber24PossibleUtil(op1, op2, op3){
     
    // Applying operation between two operands reduces
    // the count of operands to two
    if ((isNumber24PossibleUtill(op1 + op2, op3)) ||
        (isNumber24PossibleUtill(op1 - op2, op3)) ||
        (isNumber24PossibleUtill(op1 * op2, op3)) ||
        (op2 && isNumber24PossibleUtill(op1 / op2, op3)))
        return true
         
    if (isNumber24PossibleUtill(op1, op2 + op3) ||
        isNumber24PossibleUtill(op1, op2 - op3) ||
        isNumber24PossibleUtill(op1, op2 * op3) ||
        op3 && isNumber24PossibleUtill(op1, op2 / op3))
        return true
         
    return false
}
 
// Function takes given array as arr parameter
// and apply all possible operation in every
// consecutive elements and check if the remaining
// 3 parameters can be used for obtaining 24 or not
function isNumber24Possible(arr){
     
    // Apply every operation between first two operands
    if (isNumber24PossibleUtil(arr[0] + arr[1],
                            arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0] - arr[1],
                            arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0] * arr[1],
                            arr[2], arr[3]) ||
                            arr[1] &&
        isNumber24PossibleUtil(arr[0] / arr[1],
                            arr[2], arr[3]))
        return true
         
    // Between second and third operands
    if (isNumber24PossibleUtil(arr[0], arr[1] + arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1] - arr[2], arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1] * arr[2], arr[3]) ||
        arr[2] && isNumber24PossibleUtil(arr[0], arr[1] / arr[2],
                                        arr[3]))
        return true
         
    // Between third and fourth operands
    if (isNumber24PossibleUtil(arr[0], arr[1], arr[2] + arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] - arr[3]) ||
        isNumber24PossibleUtil(arr[0], arr[1], arr[2] * arr[3]) ||
        arr[3] && isNumber24PossibleUtil(arr[0], arr[1],
                                        arr[2] / arr[3]))
        return true
 
    return false
}
 
// Driver Code
 
// Given Input
let arr = [ 3, 6, 8, 2 ]
 
// Function Call
if (isNumber24Possible(arr))
    document.write("Possible","</br>")
else
    document.write("Not Possible","</br>")
 
// This code is contributed by shinjanpatra
 
</script>
Producción

Possible

Complejidad temporal: O(4 2 × 4!)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por ganesh227 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *