Entrada: str = «235813»
Salida: verdadero
Explicación: una de las secuencias posibles es: 2 , 3 , 5 , 8 , 13
donde 3 = 1 + 2 , 5 = 3 + 2 , 8 = 5 + 3 y 13 = 8 + 5 .Entrada: str = “199100199”
Salida: verdadero
Explicación: una de las secuencias posibles es: 1, 99, 100, 199
donde 100 = 99 + 1, 199 = 100 + 99 da la secuencia aditiva.Entrada: str = “12345678”
Salida: falso
Explicación: No es posible tal secuencia
Enfoque: El enfoque recursivo se analiza en el Conjunto 1 de este artículo.
Enfoque de retroceso: el problema anterior se puede resolver utilizando el retroceso de la siguiente manera.
- Uno de los requisitos básicos de acuerdo con el enunciado del problema es verificar si la string dada sigue la propiedad de la secuencia aditiva, es decir, cada número de la secuencia es la suma de los dos números anteriores y esta propiedad se cumple para todos los números de la secuencia.
- Por lo tanto, no hay restricciones sobre cómo elegir los dos primeros números de la secuencia (ya que se necesitan exactamente dos números para verificar la propiedad de la secuencia aditiva).
- Por lo tanto, intente todas las formas posibles de generar los dos primeros números de la serie y, a partir del tercer número, tenga una comparación, es decir, para mantener la propiedad de secuencia aditiva, el siguiente número de la serie debe ser la suma de los dos números anteriores.
- Entonces, si en algún momento el número generado hasta el momento excede la suma de los dos números anteriores , ya no es necesario continuar porque este número nunca será parte de una secuencia aditiva . En ese caso, retroceda e intente con el resto de las combinaciones.
- Si el número generado hasta ahora es la suma de los dos números anteriores , recurra a la string restante usando los dos números anteriores como referencia y si llega al final de la string y la longitud de la secuencia aditiva (tamaño del vector) es mayor o igual a 3, entonces la string dada tenía una secuencia aditiva.
- En el momento en que se encuentra una secuencia aditiva, marca una variable booleana global como verdadera (para indicar que hemos encontrado una solución y evitar verificar el resto de las combinaciones).
A continuación se muestra la implementación de lo anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Variable to store the result
bool res;
// Function to check the additive sequence
void check_additive(string s,
vector<long long>& v,
long st)
{
// If the end is reached and vector
// consists of more than 2 numbers then
// one of the possible solution is found
if (st == s.length() and v.size() > 2) {
// Mark the res as true to indicate
// the solution is found and
// to avoid for trying
// the rest of the combinations
res = true;
return;
}
long long a, b, c = 0;
if (v.size() >= 2) {
// Store the previous two numbers
// of the sequence to check the
// additive sequence property
// for the next number
b = v[v.size() - 1];
a = v[v.size() - 2];
}
for (long i = st; i < s.length(); i++) {
// Generate the number
c = c * 10 + (s[i] - '0');
// Try all the possible ways
// to generate the first two numbers
// i.e. if vector consists of
// less than two numbers and
// no solution is found yet
if (v.size() < 2 and !res) {
v.push_back(c);
check_additive(s, v, i + 1);
// Pop the value to try for the
// other combination
v.pop_back();
}
// If the number generated so far
// is greater than the sum of
// previous two numbers in
// the sequence then it cannot be
// a part of additive sequence
// hence no need to proceed further
else if (c > (a + b) and !res)
return;
// If the number generated so far
// is equal to the sum of
// previous two numbers then
// it can be a part of additive
// sequence; push it into vector
// and check for remaining string
else if (c == a + b and !res) {
// Store it in the vector
v.push_back(c);
// Recur for remaining string
check_additive(s, v, i + 1);
// If unable to find solution
// pop it and try for
// other combination
v.pop_back();
}
}
return;
}
// Function to check if additive sequence
bool isAdditiveSequence(string str)
{
// In order to form additive sequence
// the length of the string
// must be atleast three
if (str.length() <= 2)
return false;
vector<long long> v;
res = false;
check_additive(str, v, 0);
return res;
}
// Driver code
int main()
{
string str = "199100199";
bool ans = isAdditiveSequence(str);
if (ans)
cout << "true";
else
cout << "false";
return 0;
}
Java
// Java code to implement the approach
import java.util.ArrayList;
class GFG {
// Variable to store the result
static boolean res;
// Function to check the additive sequence
static void check_additive(String s,
ArrayList<Integer> v,
int st)
{
// If the end is reached and vector
// consists of more than 2 numbers then
// one of the possible solution is found
if (st == s.length() && v.size() > 2) {
// Mark the res as true to indicate
// the solution is found and
// to avoid for trying
// the rest of the combinations
res = true;
return;
}
int a = 0, b = 0, c = 0;
if (v.size() >= 2) {
// Store the previous two numbers
// of the sequence to check the
// additive sequence property
// for the next number
b = v.get(v.size() - 1);
a = v.get(v.size() - 2);
}
for (int i = st; i < s.length(); i++) {
// Generate the number
c = c * 10 + (s.charAt(i) - '0');
// Try all the possible ways
// to generate the first two numbers
// i.e. if vector consists of
// less than two numbers and
// no solution is found yet
if (v.size() < 2 && !res) {
v.add(c);
check_additive(s, v, i + 1);
// Pop the value to try for the
// other combination
v.remove(v.size() - 1);
}
// If the number generated so far
// is greater than the sum of
// previous two numbers in
// the sequence then it cannot be
// a part of additive sequence
// hence no need to proceed further
else if (c > (a + b) && !res)
return;
// If the number generated so far
// is equal to the sum of
// previous two numbers then
// it can be a part of additive
// sequence; push it into vector
// and check for remaining String
else if (c == a + b && !res) {
// Store it in the vector
v.add(c);
// Recur for remaining String
check_additive(s, v, i + 1);
// If unable to find solution
// pop it and try for
// other combination
v.remove(v.size() - 1);
}
}
return;
}
// Function to check if additive sequence
static boolean isAdditiveSequence(String str)
{
// In order to form additive sequence
// the length of the String
// must be atleast three
if (str.length() <= 2)
return false;
ArrayList<Integer> v = new ArrayList<Integer>();
res = false;
check_additive(str, v, 0);
return res;
}
// Driver code
public static void main(String args[]) {
String str = "199100199";
boolean ans = isAdditiveSequence(str);
if (ans)
System.out.println("true");
else
System.out.println("false");
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python3 code to implement the approach
# Variable to store the result
res = 0
v = []
# Function to check the additive sequence
def check_additive(s, st):
global res
global v
# If the end is reached and vector
# consists of more than 2 numbers then
# one of the possible solution is found
if (st == len(s) and len(v) > 2):
# Mark the res as true to indicate
# the solution is found and
# to avoid for trying
# the rest of the combinations
res = True
return
a, b, c = 0, 0, 0
if (len(v) >= 2):
# Store the previous two numbers
# of the sequence to check the
# additive sequence property
# for the next number
b = v[len(v) - 1]
a = v[len(v) - 2]
for i in range(st, len(s)):
# Generate the number
c = c * 10 + (ord(s[i]) - ord('0'))
# Try all the possible ways
# to generate the first two numbers
# i.e. if vector consists of
# less than two numbers and
# no solution is found yet
if (len(v) < 2 and (not res)):
v.append(c)
check_additive(s, i + 1)
# Pop the value to try for the
# other combination
v.pop()
# If the number generated so far
# is greater than the sum of
# previous two numbers in
# the sequence then it cannot be
# a part of additive sequence
# hence no need to proceed further
elif (c > (a + b) and not res):
return
# If the number generated so far
# is equal to the sum of
# previous two numbers then
# it can be a part of additive
# sequence; push it into vector
# and check for remaining string
elif (c == a + b and not res):
# Store it in the vector
v.append(c)
# Recur for remaining string
check_additive(s, i + 1)
# If unable to find solution
# pop it and try for
# other combination
v.pop()
return
# Function to check if additive sequence
def isAdditiveSequence(str):
global res
# In order to form additive sequence
# the length of the string
# must be atleast three
if (len(str) <= 2):
return False
res = False
check_additive(str, 0)
return res
# Driver code
if __name__ == "__main__":
str = "199100199"
ans = isAdditiveSequence(str)
if (ans):
print("true")
else:
print("false")
# This code is contributed by rakeshsahni
C#
// C# program of the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Variable to store the result
static bool res;
// Function to check the Additive sequence
static void check_Additive(string s,
List<int> v,
int st)
{
// If the end is reached and vector
// consists of more than 2 numbers then
// one of the possible solution is found
if (st == s.Length && v.Count > 2) {
// Mark the res as true to indicate
// the solution is found and
// to avoid for trying
// the rest of the combinations
res = true;
return;
}
int a = 0, b = 0, c = 0;
if (v.Count >= 2) {
// Store the previous two numbers
// of the sequence to check the
// Additive sequence property
// for the next number
b = v[v.Count - 1];
a = v[v.Count - 2];
}
for (int i = st; i < s.Length; i++) {
// Generate the number
c = c * 10 + (s[i] - '0');
// Try all the possible ways
// to generate the first two numbers
// i.e. if vector consists of
// less than two numbers and
// no solution is found yet
if (v.Count < 2 && !res) {
v.Add(c);
check_Additive(s, v, i + 1);
// Pop the value to try for the
// other combination
v.Remove(v.Count - 1);
}
// If the number generated so far
// is greater than the sum of
// previous two numbers in
// the sequence then it cannot be
// a part of Additive sequence
// hence no need to proceed further
else if (c > (a + b) && !res)
return;
// If the number generated so far
// is equal to the sum of
// previous two numbers then
// it can be a part of Additive
// sequence; push it into vector
// and check for remaining String
else if (c == a + b && !res) {
// Store it in the vector
v.Add(c);
// Recur for remaining String
check_Additive(s, v, i + 1);
// If unable to find solution
// pop it and try for
// other combination
v.Remove(v.Count - 1);
}
}
return;
}
// Function to check if Additive sequence
static bool isAdditiveSequence(string str)
{
// In order to form Additive sequence
// the length of the String
// must be atleast three
if (str.Length <= 2)
return false;
List<int> v = new List<int>();
res = true;
check_Additive(str, v, 0);
return res;
}
// Driver Code
public static void Main()
{
string str = "199100199";
bool ans = isAdditiveSequence(str);
if (ans)
Console.Write("true");
else
Console.Write("false");
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// JavaScript code for the above approach
// Variable to store the result
let res;
// Function to check the additive sequence
function check_additive(s,
v,
st) {
// If the end is reached and vector
// consists of more than 2 numbers then
// one of the possible solution is found
if (st == s.length && v.length > 2) {
// Mark the res as true to indicate
// the solution is found and
// to avoid for trying
// the rest of the combinations
res = true;
return;
}
let a, b, c = 0;
if (v.length >= 2) {
// Store the previous two numbers
// of the sequence to check the
// additive sequence property
// for the next number
b = v[v.length - 1];
a = v[v.length - 2];
}
for (let i = st; i < s.length; i++) {
// Generate the number
c = c * 10 + (s[i].charCodeAt(0) - '0'.charCodeAt(0));
// Try all the possible ways
// to generate the first two numbers
// i.e. if vector consists of
// less than two numbers and
// no solution is found yet
if (v.length < 2 && res == false) {
v.push(c);
check_additive(s, v, i + 1);
// Pop the value to try for the
// other combination
v.pop();
}
// If the number generated so far
// is greater than the sum of
// previous two numbers in
// the sequence then it cannot be
// a part of additive sequence
// hence no need to proceed further
else if (c > (a + b) && res == false)
return;
// If the number generated so far
// is equal to the sum of
// previous two numbers then
// it can be a part of additive
// sequence; push it into vector
// and check for remaining string
else if (c == a + b && res == false) {
// Store it in the vector
v.push(c);
// Recur for remaining string
check_additive(s, v, i + 1);
// If unable to find solution
// pop it and try for
// other combination
v.pop();
}
}
return;
}
// Function to check if additive sequence
function isAdditiveSequence(str)
{
// In order to form additive sequence
// the length of the string
// must be atleast three
if (str.length <= 2)
return false;
let v = [];
res = false;
check_additive(str, v, 0);
return res;
}
// Driver code
let str = "199100199";
let ans = isAdditiveSequence(str);
if (ans)
document.write("true");
else
document.write("false");
// This code is contributed by Potta Lokesh
</script>
Producción
true
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por anveshkarra1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA