Dada una ecuación lineal de n variables, encuentre el número de soluciones enteras no negativas de la misma. Por ejemplo, sea la ecuación dada «x + 2y = 5», las soluciones de esta ecuación son «x = 1, y = 2», «x = 5, y = 0» y «x = 3, y = 1». . Se puede suponer que todos los coeficientes en la ecuación dada son números enteros positivos.
Ejemplo :
Input: coeff[] = {1, 2}, rhs = 5
Output: 3
The equation "x + 2y = 5" has 3 solutions.
(x=3,y=1), (x=1,y=2), (x=5,y=0)
Input: coeff[] = {2, 2, 3}, rhs = 4
Output: 3
The equation "2x + 2y + 3z = 4" has 3 solutions.
(x=0,y=2,z=0), (x=2,y=0,z=0), (x=1,y=1,z=0)
Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.
Podemos resolver este problema recursivamente. La idea es restar el primer coeficiente de rhs y luego recurrir al valor restante de rhs.
If rhs = 0
countSol(coeff, 0, rhs, n-1) = 1
Else
countSol(coeff, 0, rhs, n-1) = ∑countSol(coeff, i, rhs-coeff[i], m-1)
where coeff[i]<=rhs and
i varies from 0 to n-1
A continuación se muestra la implementación recursiva de la solución anterior.
C++
// A naive recursive C++ program to
// find number of non-negative solutions
// for a given linear equation
#include<bits/stdc++.h>
using namespace std;
// Recursive function that returns
// count of solutions for given rhs
// value and coefficients coeff[start..end]
int countSol(int coeff[], int start,
int end, int rhs)
{
// Base case
if (rhs == 0)
return 1;
// Initialize count
// of solutions
int result = 0;
// One by subtract all smaller or
// equal coefficients and recur
for (int i = start; i <= end; i++)
if (coeff[i] <= rhs)
result += countSol(coeff, i, end,
rhs - coeff[i]);
return result;
}
// Driver Code
int main()
{
int coeff[] = {2, 2, 5};
int rhs = 4;
int n = sizeof(coeff) / sizeof(coeff[0]);
cout << countSol(coeff, 0, n - 1, rhs);
return 0;
}
Java
// A naive recursive Java program
// to find number of non-negative
// solutions for a given linear equation
import java.io.*;
class GFG
{
// Recursive function that returns
// count of solutions for given
// rhs value and coefficients coeff[start..end]
static int countSol(int coeff[], int start,
int end, int rhs)
{
// Base case
if (rhs == 0)
return 1;
// Initialize count of solutions
int result = 0;
// One by subtract all smaller or
// equal coefficients and recur
for (int i = start; i <= end; i++)
if (coeff[i] <= rhs)
result += countSol(coeff, i, end,
rhs - coeff[i]);
return result;
}
// Driver Code
public static void main (String[] args)
{
int coeff[] = {2, 2, 5};
int rhs = 4;
int n = coeff.length;
System.out.println (countSol(coeff, 0,
n - 1, rhs));
}
}
// This code is contributed by vt_m.
Python3
# A naive recursive Python program # to find number of non-negative # solutions for a given linear equation # Recursive function that returns # count of solutions for given rhs # value and coefficients coeff[stat...end] def countSol(coeff, start, end, rhs): # Base case if (rhs == 0): return 1 # Initialize count of solutions result = 0 # One by one subtract all smaller or # equal coefficients and recur for i in range(start, end+1): if (coeff[i] <= rhs): result += countSol(coeff, i, end, rhs - coeff[i]) return result # Driver Code coeff = [2, 2, 5] rhs = 4 n = len(coeff) print(countSol(coeff, 0, n - 1, rhs)) # This code is contributed # by Soumen Ghosh
C#
// A naive recursive C# program
// to find number of non-negative
// solutions for a given linear equation
using System;
class GFG
{
// Recursive function that
// returns count of solutions
// for given RHS value and
// coefficients coeff[start..end]
static int countSol(int []coeff, int start,
int end, int rhs)
{
// Base case
if (rhs == 0)
return 1;
// Initialize count of solutions
int result = 0;
// One by subtract all smaller or
// equal coefficients and recur
for (int i = start; i <= end; i++)
if (coeff[i] <= rhs)
result += countSol(coeff, i, end,
rhs - coeff[i]);
return result;
}
// Driver Code
public static void Main ()
{
int []coeff = {2, 2, 5};
int rhs = 4;
int n = coeff.Length;
Console.Write (countSol(coeff, 0,
n - 1, rhs));
}
}
// This Code is contributed
// by nitin mittal.
PHP
<?php
// A naive recursive PHP program to
// find number of non-negative solutions
// for a given linear equation
// Recursive function that returns count
// of solutions for given rhs value and
// coefficients coeff[start..end]
function countSol($coeff, $start, $end, $rhs)
{
// Base case
if ($rhs == 0)
return 1;
// Initialize count of solutions
$result = 0;
// One by subtract all smaller or
// equal coefficients and recur
for ($i = $start; $i <= $end; $i++)
if ($coeff[$i] <= $rhs)
$result += countSol($coeff, $i, $end,
$rhs - $coeff[$i]);
return $result;
}
// Driver Code
$coeff = array (2, 2, 5);
$rhs = 4;
$n = sizeof($coeff);
echo countSol($coeff, 0, $n - 1, $rhs);
// This code is contributed by ajit
?>
Javascript
<script>
// A naive recursive Javascript program
// to find number of non-negative
// solutions for a given linear equation
// Recursive function that
// returns count of solutions
// for given RHS value and
// coefficients coeff[start..end]
function countSol(coeff, start, end, rhs)
{
// Base case
if (rhs == 0)
return 1;
// Initialize count of solutions
let result = 0;
// One by subtract all smaller or
// equal coefficients and recur
for (let i = start; i <= end; i++)
if (coeff[i] <= rhs)
result += countSol(coeff, i, end, rhs - coeff[i]);
return result;
}
let coeff = [2, 2, 5];
let rhs = 4;
let n = coeff.length;
document.write(countSol(coeff, 0, n - 1, rhs));
</script>
Producción :
3
Complejidad del tiempo: O(2^n)
Espacio auxiliar: O(2^n), debido a llamadas recursivas
La complejidad temporal de la solución anterior es exponencial. Podemos resolver este problema en Pseudo Polynomial Time (la complejidad del tiempo depende del valor numérico de entrada) usando Programación Dinámica. La idea es similar a la solución de programación dinámica del problema Subset Sum . A continuación se muestra la implementación basada en la programación dinámica.
C++
// A Dynamic programming based C++
// program to find number of non-negative
// solutions for a given linear equation
#include<bits/stdc++.h>
using namespace std;
// Returns count of solutions for
// given rhs and coefficients coeff[0..n-1]
int countSol(int coeff[], int n, int rhs)
{
// Create and initialize a table
// to store results of subproblems
int dp[rhs + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
// Fill table in bottom up manner
for (int i = 0; i < n; i++)
for (int j = coeff[i]; j <= rhs; j++)
dp[j] += dp[j - coeff[i]];
return dp[rhs];
}
// Driver Code
int main()
{
int coeff[] = {2, 2, 5};
int rhs = 4;
int n = sizeof(coeff) / sizeof(coeff[0]);
cout << countSol(coeff, n, rhs);
return 0;
}
Java
// A Dynamic programming based Java program
// to find number of non-negative solutions
// for a given linear equation
import java.util.Arrays;
class GFG
{
// Returns counr of solutions for given
// rhs and coefficients coeff[0..n-1]
static int countSol(int coeff[],
int n, int rhs)
{
// Create and initialize a table to
// store results of subproblems
int dp[] = new int[rhs + 1];
Arrays.fill(dp, 0);
dp[0] = 1;
// Fill table in bottom up manner
for (int i = 0; i < n; i++)
for (int j = coeff[i]; j <= rhs; j++)
dp[j] += dp[j - coeff[i]];
return dp[rhs];
}
// Driver code
public static void main (String[] args)
{
int coeff[] = {2, 2, 5};
int rhs = 4;
int n = coeff.length;
System.out.print(countSol(coeff, n, rhs));
}
}
// This code is contributed by Anant Agarwal
Python3
# A Dynamic Programming based # Python program to find number # of non-negative solutions for # a given linear equation # Returns count of solutions for given # rhs and coefficients coeff[0...n-1] def countSol(coeff, n, rhs): # Create and initialize a table # to store results of subproblems dp = [0 for i in range(rhs + 1)] dp[0] = 1 # Fill table in bottom up manner for i in range(n): for j in range(coeff[i], rhs + 1): dp[j] += dp[j - coeff[i]] return dp[rhs] # Driver Code coeff = [2, 2, 5] rhs = 4 n = len(coeff) print(countSol(coeff, n, rhs)) # This code is contributed # by Soumen Ghosh
C#
// A Dynamic programming based
// C# program to find number of
// non-negative solutions for a
// given linear equation
using System;
class GFG
{
// Returns counr of solutions
// for given rhs and coefficients
// coeff[0..n-1]
static int countSol(int []coeff,
int n, int rhs)
{
// Create and initialize a
// table to store results
// of subproblems
int []dp = new int[rhs + 1];
// Arrays.fill(dp, 0);
dp[0] = 1;
// Fill table in
// bottom up manner
for (int i = 0; i < n; i++)
for (int j = coeff[i]; j <= rhs; j++)
dp[j] += dp[j - coeff[i]];
return dp[rhs];
}
// Driver code
public static void Main ()
{
int []coeff = {2, 2, 5};
int rhs = 4;
int n = coeff.Length;
Console.Write(countSol(coeff,
n, rhs));
}
}
// This code is contributed
// by shiv_bhakt.
PHP
<?php
// PHP program to find number of
// non-negative solutions for a
// given linear equation
// Returns count of solutions
// for given rhs and coefficients
// coeff[0..n-1]
function countSol($coeff, $n, $rhs)
{
// Create and initialize a table
// to store results of subproblems
$dp = str_repeat ("\0", 256);
$dp[0] = 1;
// Fill table in
// bottom up manner
for ($i = 0; $i < $n; $i++)
for ($j = $coeff[$i];
$j <= $rhs; $j++)
$dp[$j] = $dp[$j] + ($dp[$j -
$coeff[$i]]);
return $dp[$rhs];
}
// Driver Code
$coeff = array(2, 2, 5);
$rhs = 4;
// $n = count($coeff);
$n = sizeof($coeff) / sizeof($coeff[0]);
echo countSol($coeff, $n, $rhs);
// This code is contributed
// by shiv_bhakt.
?>
Javascript
<script>
// A Dynamic programming based
// Javascript program to find number of
// non-negative solutions for a
// given linear equation
// Returns counr of solutions
// for given rhs and coefficients
// coeff[0..n-1]
function countSol(coeff, n, rhs)
{
// Create and initialize a
// table to store results
// of subproblems
let dp = new Array(rhs + 1);
dp.fill(0);
// Arrays.fill(dp, 0);
dp[0] = 1;
// Fill table in
// bottom up manner
for (let i = 0; i < n; i++)
for (let j = coeff[i]; j <= rhs; j++)
dp[j] += dp[j - coeff[i]];
return dp[rhs];
}
let coeff = [2, 2, 5];
let rhs = 4;
let n = coeff.length;
document.write(countSol(coeff, n, rhs));
</script>
Producción :
3
Complejidad de tiempo: O (n * rhs)
Espacio Auxiliar: O(rhs) , por el tamaño de dp utilizado.
Este artículo es una contribución de Ashish Gupta . 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