[C++]Trovare quanti e quali numeri di fibonacci sono presenti in un vettore di interi

[Skull260287]

Salve, siccome mi sto scervelllando abbastanza, vorrei chiedervi come affrontereste questo problema per scrivere un algoritmo funzionante ed efficiente, grazie mille per la partecipazione al mio esaurimento :master:

Fornire una funzione ricorsiva tale che assegnata una lista ordinata di numeri interi dica quanti e quali dei numeri in essa contenuti sono numeri di Fibonacci.
Es.
L1=[1,3,7,11,13, 19, 21, 33, 34]
I numeri di Fibonacci presenti nella lista sono 6 (1, 3, 13, 21, 34)

[Skull260287]

Nessuno mi può aiutare?

[MacApp]

io incomincerei con lo scrivere una funzione del tipo "bool IsFibonacci (const int)", che dato un numero stabilisca se appartiene alla serie di Fibonacci o no.

[Skull260287]

Originariamente inviato da MacApp
io incomincerei con lo scrivere una funzione del tipo "bool IsFibonacci (const int)", che dato un numero stabilisca se appartiene alla serie di Fibonacci o no.

Quest l'ho pensato anche io, ma come implementarlo al meglio per efficienza e memoria utilizzata?

[MacApp]

Originariamente inviato da Skull260287
Quest l'ho pensato anche io, ma come implementarlo al meglio per efficienza e memoria utilizzata?

Prima lo realizzi in modo che produca risultati corretti, poi, se necessario, lo ottimizzi.

[Skull260287]

Io ho scritto questo codice, lo do in pasto a voi, fatemi sapere cosa ne pensate, cosa cambiereste e perchè, grazie mille.

#include <cstdlib>
#include <iostream>


using namespace std;

void inserisci(int,int,int v[]);
int fib(int v[],int &,int &,int,int,int,int);
int confrfibo(int v[],int,int&,int,int,int,int);


int main(){
    
    int n,k=0,j=1,fibo=0,somma=0,i=0;
    bool diverso=false;
    cout<<"Inserisci il numero di elementi del vettore";
    cin>>n;
    n=8;
    //int v[n-1];
    //inserisci(0,n-1,v);
    int v[9]={0,1,3,8,11,13,21,34,701408733};
    system("cls");
    for(int i=0;i<9;i++) cout<<v[i]<<" ";
    cout<<"\n\n";
    while(i<9 && !diverso){
              if(v[i]==0) {
              cout<<v[i]<<" ";
              i++;
              somma++;
              }
              else  diverso=true;
    }
    fib(v,k,j,fibo,k,n,somma);
    
    
    system("pause");
    return 0;

}

void inserisci(int k, int n, int v[]){
        if(k>n) return;
        else{
             cout<<"inserisci un valore: ";
             cin>>v[k];
             return inserisci(k+1,n,v);
             }
}

int fib(int v[],int &n,int &m,int fibo,int i,int riemp,int somma){
     
     fibo=n+m;
     
     if(fibo>v[i]){
                   confrfibo(v,m,somma,i,riemp,n,m);
                   }
     else {              
     n=m;
     m=fibo;
     return fib(v,n,m,fibo,i,riemp,somma);
     }
}

int confrfibo(int v[],int fibo, int &somma,int i, int riemp,int n, int m){

    if(v[i]==fibo){
                   cout<<v[i]<<" ";
                   if(i<riemp)
                   return fib(v,n,m,fibo,i+1,riemp,somma+1);
                   else cout<<"\nI numeri i fibonacci presenti nel vettore assegnato sono: "<<somma+1<<"."<<endl;
                   }
    else if((n+m)>v[i]){
                         if(i<riemp)
                         return fib(v,n,m,fibo,i+1,riemp,somma);
                         else cout<<"\nI numeri i fibonacci presenti nel vettore assegnato sono: "<<somma<<"."<<endl;
                         }
    
    else return fib(v,n,m,fibo,i,riemp,somma);
    
}

[LordSaga640]

Francamento sono troppo stanco per poter leggere altro codice per oggi.

Vedo le scritte che si muovo @.@

La soluzione che ho pensato prende per ipotesi che:
- Il vettore che hai è gia ordinato
- La serie di fibonacci cresce in modo esponenziale

La soluzione ottimizza l'uso della memoria e penso anche della complessità dell'algoritmo che è O(n) (complessità lineare) dove n sono gli elementi dell'array che hai.

pseudo codice

int fa=1;   #primo numero di fibonacci
int fb=1;    #secondo fib
int lista[]=(1,2,3,4,5,6,7,10,11,[...]);
int i=0; #indice da controllare

while(i<elementi_dell'array) {

   Se lista[i]=fa {
           scrivi lista[i] è un numero di fibonacci
    } altrimenti se lista[i]<fa { //Se l'elemento corrente è inferiore del numero di fibonacci
          i++;  // andiamo avanti
    } altrimenti se lista[i]>fa {
       /*
       Rimaniamo fermi nell'indice dell'array ma generiamo il successivo numero di fibonacci.
       */
          temp=fb;
        fb=fa;
        fa+=temp;
     }
}

Per tanti elementi dell'array la complessità diventa quasi lineare. Considera che fibonacci(40)=102334155

Se hai un elemento nell'array, l'algoritmo prima di terminare genererà il numero di fibonacci maggiore o uguale all'elemento nell'array. Quindi per valori di N bassi non è proprio linera. Lo diventa con N molto grandi, tipo se hai un array di 1000000 di elementi dovrebbe essere molto efficente.


Ero stanco e mi sono scordato che devi farlo ricorsivo.

Perchè farlo ricorsivo? sprechi tempo di CPU e memoria. Cmq, la ver. ricorsiva dell'algoritmo che ti ho illustrato è simile. Se ci pensi...
buona notte^^