👤
a fost răspuns

#2969 cautafibo
Clasa a 9-a Probleme diverse Probleme diverse cautafibo
Etichete: Cautare binară Fibonacci


Enunț
Soluții


Cerința
Se citesc pe rând numere naturale nenule. Să se determine câte din numerele citite sunt termeni ai șirului lui Fibonacci.

Date de intrare
Fișierul de intrare cautafibo.in conține numere naturale nenule, separate prin spații.

Date de ieșire
Fișierul de ieșire cautafibo.out va conține o singură valoare, reprezentând numărul termenilor Fibonacci care se regăsesc în fișierul de intrare.

Restricții și precizări
numerele din fișierul de intrare vor avea cel mult 10 cifre
fișierul de intrare va conține cel mult 100.000 de numere naturale nenule



Exemplu
cautafibo.in

5 10 89 1 7 9 8 1 6 55 19 13 55
cautafibo.out

8
Explicație
Numerele Fibonacci din fișierul de intrare sunt: 5 89 1 8 1 55 13 55

Răspuns :

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("cautafibo.in");

ofstream g("cautafibo.out");

unsigned long long num, i, contor, v[51];

int div_imp (int p, int q)

{

   int mij;

   if (q<p)

       return 0;

   else

       {

           mij=(p+q)/2;

           if(v[mij]==num)

               return 1;

           else

               if(num<v[mij])

                   return div_imp (p, mij-1);

               else

                   return div_imp (mij+1,q);

       }

}

int main()

{

   v[0]=1; v[1]=1;

   for (i=2; i<=50; ++i)

   {

       v[i]=v[i-1]+v[i-2];

   }

   while (f >> num)

   {

       if (div_imp(0,50)) ++contor;

   }

   g << contor;

}

Explicație:

am creat vectorul cu numere fibo, si pren cautare binara verific daca numarul din fisier este in vector

CINEVAFARANUMEWIX

#include <fstream>

using namespace std;

unsigned long long int vec[60];

int cb(unsigned long long int x){

int st=0,dr=59;

while(st<=dr){

int mid = (st+dr)/2;

if(vec[mid] < x)

st = mid+1;

else if (vec[mid] > x)

dr = mid + 1;

else return mid;

}

return -1;

}

int main(){

unsigned long long int x;

ifstream fin("cautafibo.in");

ofatream fout("cautafibo.out");

int cnt = 0;

unsigned long long int f1 = 1, f2 = 1, f3=0;

v[0]=1;

for(int i = 1; f3 < 10000000000ULL; i++){

f3 = f1 + f2;

f1 = f2;

f2 = f3;

vec[i]=f3;

}

while((fin>>x)){

int ind = cb(x);

if(ind !=-1)

cnt++;

}

fout << cnt;

fout.close();

}

Vă mulțumim că ați ales să vizitați platforma noastră dedicată Informatică. Sperăm că informațiile disponibile v-au fost utile. Dacă aveți întrebări suplimentare sau aveți nevoie de sprijin, nu ezitați să ne contactați. Vă așteptăm cu drag și data viitoare! Nu uitați să adăugați site-ul nostru la favorite pentru acces rapid.


Wix Learning: Alte intrebari