0

He estado tratando de resolver este ejercicio en OmegaUp pero me sigue marcando TLE (tiempo limite excedido), o sea que necesito hacerlo mas rápido, ojala puedan ayudarme.

Descripción

Como ya sabemos la sucesión de fibonacci esta compuesta por los números: 1, 1, 2, 3, 5, 8, 13, 21, 34. . . Sabiendo esto tu tarea es dado un numero N debes encontrar la posición que ocupa en la sucesión de fibonacci.

Entrada

Un numero N solamente

Salida

Un único entero que indique en que posición se encuentra el numero en la sucesión. Si el numero no se encuentra en la sucesión imprimir un -1

introducir la descripción de la imagen aquí

Aquí esta el código que tengo hasta ahora, la verdad ya no tengo idea de como hacer que se ejecute mas rapido :c

#include <stdio.h>
#include <math.h>
int main(){
    int posicion=-1,actual=0,temporal,siguiente=1;
    float N;
    scanf("%f", &N);
    if(N<pow(2,64)){
        for (int i = 0; actual <= N; i++) {
            temporal=actual;
            actual=siguiente;
            siguiente=temporal+siguiente;
            if(actual==N){
                posicion=i+1;
                actual++;
            }
        }
        printf("%d", posicion);
    }
}
3
  • No necesitas verificar que N<pow(2,64). Yo lo quitaría.
    – Mateo
    Commented el 10 oct. 2022 a las 3:24
  • Podría servirte testear si el número forma parte de la secuencia antes de hacer todo eso, especialmente si es uno grande. Así lo descartas de una. Se dice que un número forma parte si 5*n*n + 4 o 5*n*n - 4 es un cuadrado perfecto. geeksforgeeks.org/check-number-fibonacci-number stackoverflow.com/q/2432669 También podrías investigar, por ejemplo aquí
    – Mateo
    Commented el 10 oct. 2022 a las 4:04
  • Una forma de ganar mucha velocidad en este tipo de problemas basados en secuencias es mapear los primeros resultados. Así, si te piden uno de esos valores ya lo conoces de antemano y no tardas nada en dar la solución. En caso de que te pidan un valor superior, empezarías a calcular desde el último de los valores conocidos y eso que ya tienes adelantado
    – eferion
    Commented el 10 oct. 2022 a las 8:19

1 respuesta 1

-1

Para evitar el TLE puse un arreglo con los numeros de fibonacci, al inicio se obtienen y solo busco si esta en el arreglo y guarda la pos.

    int main() { 
   __int128 arr[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 
                      1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 
                      196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 
                      9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 
                      267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 
                      4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 
                      86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 
                      956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 
                      10610209857723, 17167680177565, 27777890035288, 44945570212853, 
                      72723460248141, 117669030460994, 190392490709135, 308061521170129, 
                      498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 
                      3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 
                      23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 
                      160500643816367088, 259695496911122585, 420196140727489673, 
                      679891637638612258, 1100087778366101931, 1779979416004714189, 
                      2880067194370816120, 4660046610375530309, 7540113804746346429, 
                      12200160415121876738}; 
 
   __int128 N; 
   N = read128(); 
   int pos = -1; 
 
   // Obtener el tamaño del arreglo 
   int size = sizeof(arr) / sizeof(arr[0]); 
 
   for (int i = 0; i < size; i++) { 
      if (arr[i] <= N) { 
         if (arr[i] == N) { 
            pos = i + 1;  // Posiscion inicia en 1
            break; 
         } 
      } else { 
         break; 
      } 
   } 
 
   print128(pos); 
   cout << endl; 
   return 0; 
} 

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.