Encuentre la raíz de la función no decreciente dada entre A y B

Posted on by Rudeus Greyrat

Dados tres números a , b y c que forman una función monótonamente creciente  f(x) de la forma a*x 2 + b*x + c y dos números A y B , la tarea es encontrar la raíz de la función, es decir, encontrar el valor de x tales que  f(x) = 0 donde A ≤ x ≤ B.
 

Ejemplos:

Entrada: a = 2, b = -3, c = -2, A = 0, B = 3 
Salida: 2.0000 
Explicación: 
f(x) = 2x^2 – 3x – 2 poniendo el valor de x = 2.000 
Obtenemos f (2,000) = 2(2,000)^2 – 3(2,000) – 2 = 0
Entrada: a = 2, b = -3, c = -2, A = -2, B = 1 
Salida: Sin solución

Enfoque: A continuación se muestra la representación gráfica de cualquier función f(x) :

Del gráfico anterior tenemos,

  1. Siempre que f(A)*f(B) ≤ 0 , significa que la gráfica de la función cortará el eje x en algún lugar dentro de ese rango y significa que en algún lugar hay un punto que hace que el valor de la función sea 0 y luego el gráfico procede a ser el eje y negativo .
  2. Si f(A)*f(B) > 0 , significa que en este rango [A, B] los valores y de f(A) y f(B) permanecen positivos en todo momento, por lo que nunca cortan el eje x .

Por lo tanto, a partir de la observación anterior, la idea es utilizar la búsqueda binaria para resolver este problema. Usando el rango dado de [A, B] como límite inferior y superior para la raíz de la ecuación, se puede encontrar x aplicando la búsqueda binaria en este rango. A continuación se muestran los pasos:

  1. Encuentre el medio (digamos medio ) del rango [A, B] .
  2. Si f(mid)*f(A) ≤ 0 es verdadero, entonces el espacio de búsqueda se reduce a [A, mid] , porque el corte en el eje x se ha producido en este segmento.
  3. De lo contrario, el espacio de búsqueda se reduce a [mid, B]
  4. El valor mínimo posible para root es cuando el valor alto se vuelve más pequeño que EPS (el valor más pequeño ~10 -6 ) + valor de límite inferior, es decir, fabs (alto – bajo) > EPS .
  5. Imprime el valor de la raíz.

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;
#define eps 1e-6
 
// Given function
double func(double a, double b,
            double c, double x)
{
    return a * x * x + b * x + c;
}
 
// Function to find the root of the
// given non-decreasing Function
double findRoot(double a, double b,
                double c, double low,
                double high)
{
    double x;
 
    // To get the minimum possible
    // answer for the root
    while (fabs(high - low) > eps) {
 
        // Find mid
        x = (low + high) / 2;
 
        // Search in [low, x]
        if (func(a, b, c, low)
                * func(a, b, c, x)
            <= 0) {
            high = x;
        }
 
        // Search in [x, high]
        else {
            low = x;
        }
    }
 
    // Return the required answer
    return x;
}
 
// Function to find the roots of the
// given equation within range [a, b]
void solve(double a, double b, double c,
        double A, double B)
{
 
    // If root doesn't exists
    if (func(a, b, c, A)
            * func(a, b, c, B)
        > 0) {
        cout << "No solution";
    }
 
    // Else find the root upto 4
    // decimal places
    else {
        cout << fixed
            << setprecision(4)
            << findRoot(a, b, c,
                        A, B);
    }
}
 
// Driver Code
int main()
{
    // Given range
    double a = 2, b = -3, c = -2,
        A = 0, B = 3;
 
    // Function Call
    solve(a, b, c, A, B);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
     
static final double eps = 1e-6;
 
// Given function
static double func(double a, double b,
                   double c, double x)
{
    return a * x * x + b * x + c;
}
 
// Function to find the root of the
// given non-decreasing Function
static double findRoot(double a, double b,
                       double c, double low,
                       double high)
{
    double x = -1;
     
    // To get the minimum possible
    // answer for the root
    while (Math.abs(high - low) > eps)
    {
         
        // Find mid
        x = (low + high) / 2;
         
        // Search in [low, x]
        if (func(a, b, c, low) *
            func(a, b, c, x) <= 0)
        {
            high = x;
        }
         
        // Search in [x, high]
        else
        {
            low = x;
        }
    }
     
    // Return the required answer
    return x;
}
 
// Function to find the roots of the
// given equation within range [a, b]
static void solve(double a, double b, double c,
                  double A, double B)
{
     
    // If root doesn't exists
    if (func(a, b, c, A) * func(a, b, c, B) > 0)
    {
        System.out.println("No solution");
    }
     
    // Else find the root upto 4
    // decimal places
    else
    {
        System.out.format("%.4f", findRoot(
            a, b, c, A, B));
    }
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given range
    double a = 2, b = -3, c = -2,
           A = 0, B = 3;
            
    // Function call
    solve(a, b, c, A, B);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
import math
eps = 1e-6
 
# Given function
def func(a ,b , c , x):
 
    return a * x * x + b * x + c
 
# Function to find the root of the
# given non-decreasing Function
def findRoot( a, b, c, low, high):
 
    x = -1
     
    # To get the minimum possible
    # answer for the root
    while abs(high - low) > eps:
     
        # Find mid
        x = (low + high) / 2
         
        # Search in [low, x]
        if (func(a, b, c, low) *
            func(a, b, c, x) <= 0):
            high = x
     
        # Search in [x, high]
        else:
            low = x
             
    # Return the required answer
    return x
 
# Function to find the roots of the
# given equation within range [a, b]
def solve(a, b, c, A, B):
 
    # If root doesn't exists
    if (func(a, b, c, A) *
        func(a, b, c, B) > 0):
        print("No solution")
     
    # Else find the root upto 4
    # decimal places
    else:
        print("{:.4f}".format(findRoot(
              a, b, c, A, B)))
     
# Driver code
if __name__ == '__main__':
 
    # Given range
    a = 2
    b = -3
    c = -2
    A = 0
    B = 3
             
    # Function call
    solve(a, b, c, A, B)
 
# This code is contributed by jana_sayantan

C#

// C# program for the above approach
using System;
 
class GFG{
     
static readonly double eps = 1e-6;
 
// Given function
static double func(double a, double b,
                   double c, double x)
{
    return a * x * x + b * x + c;
}
 
// Function to find the root of the
// given non-decreasing Function
static double findRoot(double a, double b,
                       double c, double low,
                       double high)
{
    double x = -1;
     
    // To get the minimum possible
    // answer for the root
    while (Math.Abs(high - low) > eps)
    {
         
        // Find mid
        x = (low + high) / 2;
         
        // Search in [low, x]
        if (func(a, b, c, low) *
            func(a, b, c, x) <= 0)
        {
            high = x;
        }
         
        // Search in [x, high]
        else
        {
            low = x;
        }
    }
     
    // Return the required answer
    return x;
}
 
// Function to find the roots of the
// given equation within range [a, b]
static void solve(double a, double b, double c,
                  double A, double B)
{
     
    // If root doesn't exists
    if (func(a, b, c, A) * func(a, b, c, B) > 0)
    {
        Console.WriteLine("No solution");
    }
     
    // Else find the root upto 4
    // decimal places
    else
    {
        Console.Write("{0:F4}", findRoot(
            a, b, c, A, B));
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given range
    double a = 2, b = -3, c = -2,
           A = 0, B = 3;
             
    // Function call
    solve(a, b, c, A, B);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
  
let eps = 1e-6;
   
// Given function
function func(a, b,
                   c, x)
{
    return a * x * x + b * x + c;
}
   
// Function to find the root of the
// given non-decreasing Function
function findRoot(a, b,
                       c, low,
                        high)
{
    let x = -1;
       
    // To get the minimum possible
    // answer for the root
    while (Math.abs(high - low) > eps)
    {
           
        // Find mid
        x = (low + high) / 2;
           
        // Search in [low, x]
        if (func(a, b, c, low) *
            func(a, b, c, x) <= 0)
        {
            high = x;
        }
           
        // Search in [x, high]
        else
        {
            low = x;
        }
    }
       
    // Return the required answer
    return x;
}
   
// Function to find the roots of the
// given equation within range [a, b]
function solve(a, b, c, A, B)
{
       
    // If root doesn't exists
    if (func(a, b, c, A) * func(a, b, c, B) > 0)
    {
        document.write("No solution");
    }
       
    // Else find the root upto 4
    // decimal places
    else
    {
        document.write(findRoot(
            a, b, c, A, B));
    }
}
 
// Driver Code
 
      // Given range
    let a = 2, b = -3, c = -2,
           A = 0, B = 3;
              
    // Function call
    solve(a, b, c, A, B);
      
</script>
Producción: 

2.0000

Complejidad de tiempo: O(log(B – A)) 
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por VikasVishwakarma1 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 *