#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ăspunsuri la întrebare
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
#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();
}