Dada una string numérica S que representa un número grande, la tarea es formar una secuencia de Fibonacci de al menos 3 de longitud a partir de la string dada. Si tal división no es posible, imprima -1.
Ejemplos:
Entrada: S = “5712”
Salida: 5 7 12
Explicación:
Dado que 5 + 7 = 12, las divisiones {5}, {7}, {12} forman una secuencia de Fibonacci.Entrada: S = “11235813″
Salida: 1 1 2 3 5 8 13
Planteamiento:
Para resolver el problema, la idea es usar Backtracking para encontrar una secuencia que siga las condiciones de la Secuencia de Fibonacci .
Siga los pasos a continuación para resolver el problema:
- Inicialice un vector seq[] para almacenar la secuencia de Fibonacci .
- Inicializa una variable pos que apunta al índice actual de la string S , inicialmente 0 .
- Iterar sobre los índices [pos, longitud – 1] :
- Agregue el número S[pos: i] a la secuencia de Fibonacci seq si la longitud de seq es menor que 2 o si el número actual es igual a la suma de los dos últimos números de seq . Repita para el índice i + 1 y proceda.
- Si el último número agregado S[pos: i] no forma una secuencia de Fibonacci y devuelve falso después de la recursión, elimínelo de la secuencia .
- De lo contrario, finalice el ciclo y devuelva verdadero a medida que se forma la secuencia de Fibonacci.
- Si pos excede la longitud de S , entonces:
- Si la longitud de la secuencia seq es mayor o igual a 3 , entonces se encuentra una secuencia de Fibonacci, por lo tanto, devuelve true .
- De lo contrario, la secuencia de Fibonacci no es posible y, por lo tanto, devuelve falso .
- Finalmente, si la longitud de seq es mayor o igual a 3, imprima los números en seq como la secuencia de Fibonacci requerida o, de lo contrario, imprima -1 .
A continuación se muestra la ilustración de la estructura recursiva donde solo se extiende una rama para obtener el resultado:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
#define LL long long
// Function that returns true if
// Fibonacci sequence is found
bool splitIntoFibonacciHelper(int pos,
string S,
vector<int>& seq)
{
// Base condition:
// If pos is equal to length of S
// and seq length is greater than 3
if (pos == S.length()
and (seq.size() >= 3)) {
// Return true
return true;
}
// Stores current number
LL num = 0;
for (int i = pos; i < S.length(); i++) {
// Add current digit to num
num = num * 10 + (S[i] - '0');
// Avoid integer overflow
if (num > INT_MAX)
break;
// Avoid leading zeros
if (S[pos] == '0' and i > pos)
break;
// If current number is greater
// than last two number of seq
if (seq.size() > 2
and (num > ((LL)seq.back()
+ (LL)seq[seq.size()
- 2])))
break;
// If seq length is less
// 2 or current number is
// is equal to the last
// two of the seq
if (seq.size() < 2
or (num == ((LL)seq.back()
+ (LL)seq[seq.size()
- 2]))) {
// Add to the seq
seq.push_back(num);
// Recur for i+1
if (splitIntoFibonacciHelper(i + 1,
S, seq))
return true;
// Remove last added number
seq.pop_back();
}
}
// If no sequence is found
return false;
}
// Function that prints the Fibonacci
// sequence from the split of string S
void splitIntoFibonacci(string S)
{
// Initialize a vector to
// store the sequence
vector<int> seq;
// Call helper function
splitIntoFibonacciHelper(0, S,
seq);
// If sequence length is
// greater than 3
if (seq.size() >= 3) {
// Print the sequence
for (int i : seq)
cout << i << " ";
}
// If no sequence is found
else {
// Print -1
cout << -1;
}
}
// Driver Code
int main()
{
// Given String
string S = "11235813";
// Function Call
splitIntoFibonacci(S);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function that returns true if
// Fibonacci sequence is found
static boolean splitIntoFibonacciHelper(int pos,
String S,
ArrayList<Long> seq)
{
// Base condition:
// If pos is equal to length of S
// and seq length is greater than 3
if (pos == S.length() && (seq.size() >= 3))
{
// Return true
return true;
}
// Stores current number
long num = 0;
for(int i = pos; i < S.length(); i++)
{
// Add current digit to num
num = num * 10 + (S.charAt(i) - '0');
// Avoid integer overflow
if (num > Integer.MAX_VALUE)
break;
// Avoid leading zeros
if (S.charAt(pos) == '0' && i > pos)
break;
// If current number is greater
// than last two number of seq
if (seq.size() > 2 &&
(num > ((long)seq.get(seq.size() - 1) +
(long)seq.get(seq.size() - 2))))
break;
// If seq length is less
// 2 or current number is
// is equal to the last
// two of the seq
if (seq.size() < 2 ||
(num == ((long)seq.get(seq.size() - 1) +
(long)seq.get(seq.size() - 2))))
{
// Add to the seq
seq.add(num);
// Recur for i+1
if (splitIntoFibonacciHelper(i + 1,
S, seq))
return true;
// Remove last added number
seq.remove(seq.size() - 1);
}
}
// If no sequence is found
return false;
}
// Function that prints the Fibonacci
// sequence from the split of string S
static void splitIntoFibonacci(String S)
{
// Initialize a vector to
// store the sequence
ArrayList<Long> seq = new ArrayList<>();
// Call helper function
splitIntoFibonacciHelper(0, S, seq);
// If sequence length is
// greater than 3
if (seq.size() >= 3)
{
// Print the sequence
for (int i = 0; i < seq.size(); i++)
System.out.print(seq.get(i) + " ");
}
// If no sequence is found
else
{
// Print -1
System.out.print("-1");
}
}
// Driver code
public static void main(String[] args)
{
// Given String
String S = "11235813";
// Function Call
splitIntoFibonacci(S);
}
}
// This code is contributed by offbeat
Python3
# Python3 program of the above approach
import sys
# Function that returns true if
# Fibonacci sequence is found
def splitIntoFibonacciHelper(pos, S, seq):
# Base condition:
# If pos is equal to length of S
# and seq length is greater than 3
if (pos == len(S) and (len(seq) >= 3)):
# Return true
return True
# Stores current number
num = 0
for i in range(pos, len(S)):
# Add current digit to num
num = num * 10 + (ord(S[i]) - ord('0'))
# Avoid integer overflow
if (num > sys.maxsize):
break
# Avoid leading zeros
if (ord(S[pos]) == ord('0') and i > pos):
break
# If current number is greater
# than last two number of seq
if (len(seq) > 2 and
(num > (seq[-1] +
seq[len(seq) - 2]))):
break
# If seq length is less
# 2 or current number is
# is equal to the last
# two of the seq
if (len(seq) < 2 or
(num == (seq[-1] +
seq[len(seq) - 2]))):
# Add to the seq
seq.append(num)
# Recur for i+1
if (splitIntoFibonacciHelper(
i + 1, S, seq)):
return True
# Remove last added number
seq.pop()
# If no sequence is found
return False
# Function that prints the Fibonacci
# sequence from the split of string S
def splitIntoFibonacci(S):
# Initialize a vector to
# store the sequence
seq = []
# Call helper function
splitIntoFibonacciHelper(0, S, seq)
# If sequence length is
# greater than 3
if (len(seq) >= 3):
# Print the sequence
for i in seq:
print(i, end = ' ')
# If no sequence is found
else:
# Print -1
print(-1, end = '')
# Driver Code
if __name__=='__main__':
# Given String
S = "11235813"
# Function Call
splitIntoFibonacci(S)
# This code is contributed by pratham76
C#
// C# program of the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function that returns true if
// Fibonacci sequence is found
static bool splitIntoFibonacciHelper(int pos,
string S,
ArrayList seq)
{
// Base condition:
// If pos is equal to length of S
// and seq length is greater than 3
if (pos == S.Length && (seq.Count >= 3))
{
// Return true
return true;
}
// Stores current number
long num = 0;
for(int i = pos; i < S.Length; i++)
{
// Add current digit to num
num = num * 10 + (S[i] - '0');
// Avoid integer overflow
if (num > Int64.MaxValue)
break;
// Avoid leading zeros
if (S[pos] == '0' && i > pos)
break;
// If current number is greater
// than last two number of seq
if (seq.Count> 2 &&
(num > ((long)seq[seq.Count - 1] +
(long)seq[seq.Count - 2])))
break;
// If seq length is less
// 2 or current number is
// is equal to the last
// two of the seq
if (seq.Count < 2 ||
(num == ((long)seq[seq.Count - 1] +
(long)seq[seq.Count - 2])))
{
// Add to the seq
seq.Add(num);
// Recur for i+1
if (splitIntoFibonacciHelper(i + 1,
S, seq))
return true;
// Remove last added number
seq.Remove(seq.Count - 1);
}
}
// If no sequence is found
return false;
}
// Function that prints the Fibonacci
// sequence from the split of string S
static void splitIntoFibonacci(string S)
{
// Initialize a vector to
// store the sequence
ArrayList seq = new ArrayList();
// Call helper function
splitIntoFibonacciHelper(0, S, seq);
// If sequence length is
// greater than 3
if (seq.Count >= 3)
{
// Print the sequence
for(int i = 0; i < seq.Count; i++)
Console.Write(seq[i] + " ");
}
// If no sequence is found
else
{
// Print -1
Console.Write("-1");
}
}
// Driver Code
public static void Main(string[] args)
{
// Given String
string S = "11235813";
// Function call
splitIntoFibonacci(S);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program of the above approach
// Function that returns true if
// Fibonacci sequence is found
function splitIntoFibonacciHelper(pos, S, seq)
{
// Base condition:
// If pos is equal to length of S
// and seq length is greater than 3
if (pos == S.length && (seq.length >= 3))
{
// Return true
return true;
}
// Stores current number
let num = 0;
for(let i = pos; i < S.length; i++)
{
// Add current digit to num
num = num * 10 + (S[i] - '0');
// Avoid integer overflow
if (num > Number.MAX_VALUE)
break;
// Avoid leading zeros
if (S[pos] == '0' && i > pos)
break;
// If current number is greater
// than last two number of seq
if (seq.length> 2 &&
(num > (seq[seq.length - 1] +
seq[seq.length - 2])))
break;
// If seq length is less
// 2 or current number is
// is equal to the last
// two of the seq
if (seq.length < 2 ||
(num == (seq[seq.length - 1] +
seq[seq.length - 2])))
{
// Add to the seq
seq.push(num);
// Recur for i+1
if (splitIntoFibonacciHelper(i + 1, S, seq))
return true;
// Remove last added number
seq.pop();
}
}
// If no sequence is found
return false;
}
// Function that prints the Fibonacci
// sequence from the split of string S
function splitIntoFibonacci(S)
{
// Initialize a vector to
// store the sequence
let seq = [];
// Call helper function
splitIntoFibonacciHelper(0, S, seq);
// If sequence length is
// greater than 3
if (seq.length >= 3)
{
// Print the sequence
for(let i = 0; i < seq.length; i++)
document.write(seq[i] + " ");
}
// If no sequence is found
else
{
// Print -1
document.write("-1");
}
}
// Given String
let S = "11235813";
// Function call
splitIntoFibonacci(S);
// This code is contributed by suresh07.
</script>
Producción:
1 1 2 3 5 8 13
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Publicación traducida automáticamente
Artículo escrito por red_devil09 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA