Dada una función polinomial f(x) = 1+ a1*x + a2*(x^2) + … an(x^n). Encuentre el valor Sgn de estas funciones, cuando se da x y todos los coeficientes también.
If value of polynomial greater than 0 Sign = 1 Else If value of polynomial less than 0 Sign = -1 Else if value of polynomial is 0 Sign = 0
Ejemplos:
Input: poly[] = [1, 2, 3]
x = 1
Output: 1
Explanation: f(1) = 6 which is > 0
hence 1.
Input: poly[] = [1, -1, 2, 3]
x = -2
Output: -1
Explanation: f(-2)=-11 which is less
than 0, hence -1.
Un enfoque ingenuo será calcular cada potencia de x y luego sumarla a la respuesta multiplicándola por su coeficiente. Calcular el poder de x tomará O(n) tiempo y para n coeficientes. Por lo tanto, tomando la complejidad total a O (n * n), ya que necesitaremos bucles anidados para atravesar n * n veces.
Un enfoque eficiente es utilizar el método de Horner . Evaluamos el valor del polinomio usando el método de Horner. Luego devolvemos el valor según el signo del valor.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find sign value of a
// polynomial
#include <iostream>
using namespace std;
// returns value of poly[0]x(n-1) + poly[1]x(n-2)
// + .. + poly[n-1]
int horner(int poly[], int n, int x)
{
int result = poly[0]; // Initialize result
// Evaluate value of polynomial
// using Horner's method
for (int i=1; i<n; i++)
result = result*x + poly[i];
return result;
}
// Returns sign value of polynomial
int findSign(int poly[], int n, int x)
{
int result = horner(poly, n, x);
if (result > 0)
return 1;
else if (result < 0)
return -1;
return 0;
}
// Driver program to test above function.
int main()
{
// Let us evaluate value of 2x3 - 6x2
// + 2x - 1 for x = 3
int poly[] = {2, -6, 2, -1};
int x = 3;
int n = sizeof(poly)/sizeof(poly[0]);
cout << "Sign of polynomial is "
<< findSign(poly, n, x);
return 0;
}
Java
// Java program to find sign value of a
// polynomial
class GFG
{
// returns value of poly[0]x(n-1) + poly[1]x(n-2)
// + .. + poly[n-1]
static int horner(int poly[], int n, int x)
{
// Initialize result
int result = poly[0];
// Evaluate value of polynomial
// using Horner's method
for (int i = 1; i < n; i++)
result = result * x + poly[i];
return result;
}
// Returns sign value of polynomial
static int findSign(int poly[], int n, int x)
{
int result = horner(poly, n, x);
if (result > 0)
return 1;
else if (result < 0)
return -1;
return 0;
}
// Driver code
public static void main (String[] args)
{
// Let us evaluate value of 2x3 - 6x2
// + 2x - 1 for x = 3
int poly[] = {2, -6, 2, -1};
int x = 3;
int n = poly.length;
System.out.print("Sign of polynomial is "+
findSign(poly, n, x));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find
# sign value of a
# polynomial
# returns value of poly[0]x(n-1) +
# poly[1]x(n-2) + .. + poly[n-1]
def horner( poly, n, x):
# Initialize result
result = poly[0];
# Evaluate value of
# polynomial using
# Horner's method
for i in range(1,n):
result = (result * x +
poly[i]);
return result;
# Returns sign value
# of polynomial
def findSign(poly, n, x):
result = horner(poly, n, x);
if (result > 0):
return 1;
elif (result < 0):
return -1;
return 0;
# Driver Code
# Let us evaluate value
# of 2x3 - 6x2
# + 2x - 1 for x = 3
poly = [2, -6, 2, -1];
x = 3;
n = len(poly);
print("Sign of polynomial is ",
findSign(poly, n, x));
# This code is contributed by mits
C#
// C# program to find sign value of a
// polynomial
using System;
class GFG {
// returns value of poly[0]x(n-1)
// + poly[1]x(n-2) + .. + poly[n-1]
static int horner(int []poly, int n, int x)
{
// Initialize result
int result = poly[0];
// Evaluate value of polynomial
// using Horner's method
for (int i = 1; i < n; i++)
result = result * x + poly[i];
return result;
}
// Returns sign value of polynomial
static int findSign(int []poly, int n, int x)
{
int result = horner(poly, n, x);
if (result > 0)
return 1;
else if (result < 0)
return -1;
return 0;
}
// Driver code
public static void Main ()
{
// Let us evaluate value of 2x3 - 6x2
// + 2x - 1 for x = 3
int []poly = {2, -6, 2, -1};
int x = 3;
int n = poly.Length;
Console.Write("Sign of polynomial is "
+ findSign(poly, n, x));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find
// sign value of a
// polynomial
// returns value of poly[0]x(n-1) +
// poly[1]x(n-2) + .. + poly[n-1]
function horner( $poly, $n, $x)
{
// Initialize result
$result = $poly[0];
// Evaluate value of polynomial
// using Horner's method
for ($i = 1; $i < $n; $i++)
$result = $result * $x + $poly[$i];
return $result;
}
// Returns sign value
// of polynomial
function findSign($poly, $n, $x)
{
$result = horner($poly, $n, $x);
if ($result > 0)
return 1;
else if ($result < 0)
return -1;
return 0;
}
// Driver Code
// Let us evaluate value
// of 2x3 - 6x2
// + 2x - 1 for x = 3
$poly = array(2, -6, 2, -1);
$x = 3;
$n = count($poly);
echo "Sign of polynomial is "
, findSign($poly, $n, $x);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// Javascript program to find sign value of a
// polynomial
// Returns value of poly[0]x(n-1) + poly[1]x(n-2)
// + .. + poly[n-1]
function horner(poly, n, x)
{
// Initialize result
var result = poly[0];
// Evaluate value of polynomial
// using Horner's method
for(var i = 1; i < n; i++)
result = result * x + poly[i];
return result;
}
// Returns sign value of polynomial
function findSign(poly, n, x)
{
var result = horner(poly, n, x);
if (result > 0)
return 1;
else if (result < 0)
return -1;
return 0;
}
// Driver Code
// Let us evaluate value of 2x3 - 6x2
// + 2x - 1 for x = 3
var poly = [ 2, -6, 2, -1 ];
var x = 3;
var n = poly.length;
document.write("Sign of polynomial is "+
findSign(poly, n, x));
// This code is contributed by kirti
</script>
Producción:
Sign of polynomial is 1
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Raja Vikramaditya . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA