Dados tres números enteros N , A y B , la tarea es encontrar si N puede representarse como la suma de A y B.
Ejemplos:
Entrada: N = 11, A = 2, B = 3
Salida: Sí
2 + 2 + 2 + 2 + 3 = 11Entrada: N = 8, A = 3, B = 7
Salida: No
Enfoque: una solución eficiente es llamar a una función recursiva que comience con cero (porque el cero siempre es posible). Si la llamada a la función es fun(x) , entonces llama recursivamente a fun(x + a) y fun(x + b) (porque si x es posible, entonces x + a y x + b también son posibles). Vuelve fuera de la función si x > n .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find if number N can
// be represented as sum of a's and b's
#include <bits/stdc++.h>
using namespace std;
// Function to find if number N can
// be represented as sum of a's and b's
void checkIfPossibleRec(int x, int a, int b,
bool isPossible[], int n)
{
// base condition
if (x > n)
return;
// if x is already visited
if (isPossible[x])
return;
// set x as possible
isPossible[x] = true;
// recursive call
checkIfPossibleRec(x + a, a, b, isPossible, n);
checkIfPossibleRec(x + b, a, b, isPossible, n);
}
bool checkPossible(int n, int a, int b)
{
bool isPossible[n + 1] = { false };
checkIfPossibleRec(0, a, b, isPossible, n);
return isPossible[n];
}
// Driver program
int main()
{
int a = 3, b = 7, n = 8;
if (checkPossible(a, b, n))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java program to find if number N can
// be represented as sum of a's and b's
import java.util.*;
class solution
{
// Function to find if number N can
// be represented as sum of a's and b's
static void checkIfPossibleRec(int x, int a, int b,
boolean isPossible[], int n)
{
// base condition
if (x > n)
return;
// if x is already visited
if (isPossible[x])
return;
// set x as possible
isPossible[x] = true;
// recursive call
checkIfPossibleRec(x + a, a, b, isPossible, n);
checkIfPossibleRec(x + b, a, b, isPossible, n);
}
static boolean checkPossible(int n, int a, int b)
{
boolean isPossible[]=new boolean[n + 1];
for(int i=0;i<=n;i++)
isPossible[i]=false;
checkIfPossibleRec(0, a, b, isPossible, n);
return isPossible[n];
}
// Driver program
public static void main(String args[])
{
int a = 3, b = 7, n = 8;
if (checkPossible(a, b, n))
System.out.print("Yes");
else
System.out.print( "No");
}
}
//contributed by Arnab Kundu
Python3
# Python3 program to find if number N can
# be represented as sum of a's and b's
# Function to find if number N can
# be represented as sum of a's and b's
def checkIfPossibleRec(x, a, b, isPossible, n):
# base condition
if x > n:
return
# If x is already visited
if isPossible[x]:
return
# Set x as possible
isPossible[x] = True
# Recursive call
checkIfPossibleRec(x + a, a, b, isPossible, n)
checkIfPossibleRec(x + b, a, b, isPossible, n)
def checkPossible(n, a, b):
isPossible = [False] * (n + 1)
checkIfPossibleRec(0, a, b, isPossible, n)
return isPossible[n]
# Driver Code
if __name__ == "__main__":
a, b, n = 3, 7, 8
if checkPossible(a, b, n):
print("Yes")
else:
print("No")
# This code is contributed by Rituraj Jain
C#
// C# program to find if number N can
// be represented as sum of a's and b's
using System;
class GFG
{
// Function to find if number N can
// be represented as sum of a's and b's
static void checkIfPossibleRec(int x, int a, int b,
bool []isPossible, int n)
{
// base condition
if (x > n)
return;
// if x is already visited
if (isPossible[x])
return;
// set x as possible
isPossible[x] = true;
// recursive call
checkIfPossibleRec(x + a, a, b, isPossible, n);
checkIfPossibleRec(x + b, a, b, isPossible, n);
}
static bool checkPossible(int n, int a, int b)
{
bool []isPossible = new bool[n + 1];
for(int i = 0; i <= n; i++)
isPossible[i] = false;
checkIfPossibleRec(0, a, b, isPossible, n);
return isPossible[n];
}
// Driver Code
static public void Main ()
{
int a = 3, b = 7, n = 8;
if (checkPossible(a, b, n))
Console.WriteLine("Yes");
else
Console.WriteLine( "No");
}
}
// This code is contributed by Sach_Code
PHP
<?php
// PHP program to find if number N can
// be represented as sum of a's and b's
// Function to find if number N can
// be represented as sum of a's and b's
function checkIfPossibleRec($x, $a, $b,
$isPossible, $n)
{
// base condition
if ($x > $n)
return;
// if x is already visited
if ($isPossible == true)
return;
// set x as possible
$isPossible[$x] = true;
// recursive call
checkIfPossibleRec($x + $a, $a, $b,
$isPossible, $n);
checkIfPossibleRec($x + $b, $a, $b,
$isPossible, $n);
}
function checkPossible($n, $a, $b)
{
$isPossible[$n + 1] = array(false);
checkIfPossibleRec(0, $a, $b, $isPossible, $n);
return $isPossible;
}
// Driver Code
$a = 3;
$b = 7;
$n = 8;
if (checkPossible($a, $b, $n))
echo "No";
else
echo "Yes";
// This code is contributed by Sach_Code
?>
Javascript
<script>
// Javascript program to find if number N can
// be represented as sum of a's and b's
// Function to find if number N can
// be represented as sum of a's and b's
function checkIfPossibleRec(x, a, b, isPossible, n)
{
// Base condition
if (x > n)
return;
// If x is already visited
if (isPossible[x])
return;
// Set x as possible
isPossible[x] = true;
// Recursive call
checkIfPossibleRec(x + a, a, b, isPossible, n);
checkIfPossibleRec(x + b, a, b, isPossible, n);
}
function checkPossible(n, a, b)
{
var isPossible = Array(n + 1).fill(false);
checkIfPossibleRec(0, a, b, isPossible, n);
return isPossible[n];
}
// Driver code
var a = 3, b = 7, n = 8;
if (checkPossible(a, b, n))
document.write("Yes");
else
document.write("No");
// This code is contributed by todaysgaurav
</script>
Producción:
No
Complejidad de tiempo: O(2^n), complejidad de tiempo de función recursiva
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño (n+1) se usa para hacer una array booleana
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA