Una relación de recurrencia es una ecuación que define recursivamente una secuencia o array multidimensional de valores, una vez que se dan uno o más términos iniciales; cada término adicional de la secuencia o array se define como una función de los términos anteriores. A continuación se muestran los pasos necesarios para resolver una ecuación de recurrencia utilizando el método de reducción de polinomios:
- Forme una ecuación característica para la ecuación de recurrencia dada.
- Resuelva la ecuación característica y encuentre las raíces de la ecuación característica.
- Simplifica la solución con coeficientes desconocidos.
- Resuelva la ecuación con respecto a las condiciones iniciales para obtener una solución específica.
Ejemplo:
Considere la siguiente ecuación de recurrencia de segundo orden:
T(n) = a1T(n-1) + a2T(n-2)
Para resolver esta ecuación, formúlela en una ecuación característica.
Reordenemos la ecuación de la siguiente manera:
T(n) - a1T(n-1) - a2T(n-2) = 0
Sea, T(n) = x n
Ahora podemos decir que T(n-1) = x n-1 y T(n-2)=x n-2
Ahora la ecuación será:
xn + a1xn-1 + a2xn-2 = 0
Después de dividir toda la ecuación por x n-2 [ya que x no es igual a 0 ] obtenemos:
x2 + a1x + a2 = 0
Tenemos nuestra ecuación característica como x 2 +a 1 x+a 2 =0
Ahora, encuentre las raíces de esta ecuación.
Pueden existir tres casos al encontrar las raíces de la ecuación característica y esos son:
Caso 1: Las raíces de la ecuación característica son reales y distintas
Si hay un número r de raíces distintas para la ecuación característica, entonces se puede decir que son posibles un número r de soluciones fundamentales. Se puede tomar cualquier combinación lineal de raíces para obtener la solución general de una ecuación de recurrencia lineal.
Si r 1 , r 2 , r 3 ……, r k son las raíces de la ecuación característica entonces la solución general de la ecuación de recurrencia será:
tn = c1r1n + c2r2n + c3r3n +...........+ ckrkn
Caso 2: Las raíces de la ecuación característica son reales pero no distintas
Consideremos que las raíces de las ecuaciones características no son distintas y que las raíces r están en la multiplicidad de m. En este caso, la solución de la ecuación característica será:
r1 = rn r2 = nrn r3 = n2rn ......... rm = nm-1rn
Por lo tanto, incluya todas las soluciones para obtener una solución general de la ecuación de recurrencia dada.
Caso 3: Las raíces de la ecuación característica son distintas pero no reales
Si las raíces de la ecuación característica son complejas, encuentre el par conjugado de raíces.
Si r 1 y r 2 son las dos raíces de una ecuación característica, y están en pares conjugados entre sí, se puede expresar como:
r1 = reix r2 = re-ix
La solución general será:
tn = rn(c1cos nx + c2sin nx)
Ejemplo:
Resolvamos la relación de recurrencia dada:
T(n) = 7*T(n-1) - 12*T(n-2)
Sea T(n) = x n
Ahora podemos decir que T(n-1) = x n-1 y T(n-2)=x n-2
Y dividiendo toda la ecuación por x n-2 , obtenemos:
x2 - 7*x + 12 = 0
A continuación se muestra la implementación para resolver la ecuación cuadrática dada:
C++
// C++ program to find roots
// of a quadratic equation
#include<bits/stdc++.h>
using namespace std;
class Quadratic{
public:
// Prints roots of quadratic
// equation ax * 2 + bx + x
void findRoots(int a, int b, int c)
{
// If a is 0, then equation is not
// quadratic, but linear
if (a == 0)
{
cout << "Invalid";
return;
}
int d = b * b - 4 * a * c;
float sqrt_val = sqrt(abs(d));
// Real Roots
if (d > 0)
{
cout << "Roots are real and different" << endl;
cout << fixed << std::setprecision(1)
<< float((-b + sqrt_val) / (2 * a)) << endl;
cout << fixed << std::setprecision(1)
<< float((-b - sqrt_val) / (2 * a)) << endl;
}
// Imaginary Roots
else
{
cout << "Roots are complex" << endl;
cout << fixed << std::setprecision(1)
<< float(b / (2.0 * a)) << " + i"
<< sqrt_val << endl;
cout << fixed << std::setprecision(1)
<< float(b / (2.0 * a)) << " - i"
<< sqrt_val << endl;
}
}
};
// Driver code
int main()
{
Quadratic obj;
// Given value of coefficients
int a = 1, b = -7, c = 12;
obj.findRoots(a, b, c);
}
// This code is contributed by SURENDRA_GANGWAR
Java
// Java program to find roots
// of a quadratic equation
import java.io.*;
import static java.lang.Math.*;
class Quadratic {
// Prints roots of quadratic
// equation ax * 2 + bx + x
void findRoots(int a, int b, int c)
{
// If a is 0, then equation is not
// quadratic, but linear
if (a == 0) {
System.out.println("Invalid");
return;
}
int d = b * b - 4 * a * c;
double sqrt_val = sqrt(abs(d));
// Real Roots
if (d > 0) {
System.out.println(
"Roots are real"
+ " and different \n");
System.out.println(
(double)(-b + sqrt_val)
/ (2 * a)
+ "\n"
+ (double)(-b - sqrt_val)
/ (2 * a));
}
// Imaginary Roots
else {
System.out.println(
"Roots are complex \n");
System.out.println(
-(double)b / (2 * a)
+ " + i"
+ sqrt_val + "\n"
+ -(double)b / (2 * a)
+ " - i" + sqrt_val);
}
}
// Driver code
public static void main(String args[])
{
Quadratic obj = new Quadratic();
// Given value of coefficients
int a = 1, b = -7, c = 12;
obj.findRoots(a, b, c);
}
}
Python3
# Python3 program to find roots
# of a quadratic equation
from math import sqrt
# Prints roots of quadratic
# equation ax * 2 + bx + x
def findRoots(a, b, c):
# If a is 0, then equation is not
# quadratic, but linear
if (a == 0):
print("Invalid")
return
d = b * b - 4 * a * c
sqrt_val = sqrt(abs(d))
# Real Roots
if (d > 0):
print("Roots are real and different")
print((-b + sqrt_val) / (2 * a))
print((-b - sqrt_val) / (2 * a))
# Imaginary Roots
else:
print("Roots are complex \n")
print(-b / (2 * a), " + i",
sqrt_val, "\n",
-b / (2 * a), " - i",
sqrt_val)
# Driver code
if __name__ == '__main__':
# Given value of coefficients
a = 1
b = -7
c = 12
findRoots(a, b, c)
# This code is contributed by mohit kumar 29
C#
// C# program to find roots
// of a quadratic equation
using System;
class Quadratic{
// Prints roots of quadratic
// equation ax * 2 + bx + x
void findRoots(int a,
int b, int c)
{
// If a is 0, then equation
// is not quadratic, but linear
if (a == 0)
{
Console.WriteLine("Invalid");
return;
}
int d = b * b - 4 *
a * c;
double sqrt_val =
Math.Sqrt(Math.Abs(d));
// Real Roots
if (d > 0)
{
Console.WriteLine("Roots are real" +
" and different \n");
Console.WriteLine((double)
(-b + sqrt_val) /
(2 * a) + "\n" +
(double)
(-b - sqrt_val) /
(2 * a));
}
// Imaginary Roots
else
{
Console.WriteLine("Roots are complex \n");
Console.WriteLine(-(double)b / (2 * a) +
" + i" + sqrt_val +
"\n" + -(double)b /
(2 * a) + " - i" +
sqrt_val);
}
}
// Driver code
public static void Main(String []args)
{
Quadratic obj = new Quadratic();
// Given value of coefficients
int a = 1, b = -7, c = 12;
obj.findRoots(a, b, c);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program to find roots
// of a quadratic equation
// Prints roots of quadratic
// equation ax * 2 + bx + x
function findRoots(a, b, c)
{
// If a is 0, then equation is not
// quadratic, but linear
if (a == 0) {
document.write("Invalid");
return;
}
let d = b * b - 4 * a * c;
let sqrt_val = Math.sqrt(Math.abs(d));
// Real Roots
if (d > 0) {
document.write(
"Roots are real"
+ " and different <br>");
document.write(
(-b + sqrt_val)
/ (2 * a)
+ "<br>"
+ (-b - sqrt_val)
/ (2 * a));
}
// Imaginary Roots
else {
document.write(
"Roots are complex <bR>");
document.write(
-b / (2 * a)
+ " + i"
+ sqrt_val + "<br>"
+ -b / (2 * a)
+ " - i" + sqrt_val);
}
}
// Driver code
// Given value of coefficients
let a = 1, b = -7, c = 12;
findRoots(a, b, c);
// This code is contributed by unknown2108
</script>
Roots are real and different 4.0 3.0
Complejidad de Tiempo: O(√N)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitnandi01234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA