2969 - Cauta Fibo

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

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",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. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

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

Exemple

Exemplul 1

cautafibo.in

5 10 89 1 7 9 8 1 6 55 19 13 55

ecran

Datele sunt introduse corect.

cautafibo.out

8

Exemplul 2

cautafibo.in

1 3 5 8 13 21 34 55 89 144

ecran

Datele sunt introduse corect.

cautafibo.out

10

Exemplul 3

cautafibo.in

-5 2 7 9 11 13 15

ecran

Datele nu corespund restricțiilor impuse.

cautafibo.out

Rezolvare

# 2969 - Cauta Fibo 
import sys


def este_valid(fisier_intrare):
    try:
        with open(fisier_intrare, 'r') as f:
            for line in f:
                nums = line.strip().split()
                for num in nums:
                    if not num.isnumeric() or int(num) < 1 or len(num) > 10:
                        print("Datele nu corespund restricțiilor impuse.")
                        sys.exit(0)
        print("Datele sunt introduse corect.")
        return True
    except:
        sys.exit(0)


def rezolva(fisier_intrare):
    with open(fisier_intrare, 'r') as f, open('cautafibo.out', 'w') as g:
        a = [1, 1]
        while a[-1] <= 10000000001:
            a.append(a[-1] + a[-2])
        cnt = 0
        for line in f:
            nums = line.strip().split()
            for num in nums:
                x = int(num)
                poz = -1
                st, dr = 0, len(a) - 1
                while st <= dr:
                    m = (st + dr) // 2
                    if x <= a[m]:
                        poz = m
                        dr = m - 1
                    else:
                        st = m + 1
                if a[poz] == x:
                    cnt += 1
        g.write(str(cnt))


if __name__ == '__main__':
    fisier_intrare = 'cautafibo.in'
    este_valid(fisier_intrare)
    rezolva(fisier_intrare)

Explicatie

Funcția este_valid(fisier_intrare) primește ca parametru calea către un fișier de intrare și verifică dacă datele din fișier respectă restricțiile impuse. Mai precis, citind fiecare linie din fișier, verifică dacă fiecare număr este numeric, are o lungime maximă de 10 caractere și este mai mare sau egal cu 1. Dacă datele din fișier sunt valide, funcția returnează True, altfel returnează False. În plus, funcția afișează mesajul "Datele sunt introduse corect." sau "Datele nu corespund restricțiilor impuse." în funcție de validitatea datelor.

Funcția rezolva(fisier_intrare) primește ca parametru calea către un fișier de intrare și citește datele din fișier, găsind numărul de numere din fișier care sunt în șirul lui Fibonacci. Pentru a face acest lucru, inițializează șirul lui Fibonacci până la 10000000001, apoi pentru fiecare număr din fișier, folosește o căutare binară în șirul lui Fibonacci pentru a determina dacă acesta se află în șir. Dacă se află, numărul de numere găsite este incrementat. La final, funcția scrie numărul de numere găsite în fișierul "cautafibo.out".

Blocul if __name__ == '__main__': este folosit pentru a verifica dacă scriptul este rulat ca fișier principal. În cazul în care este rulat ca fișier principal, acesta va apela funcțiile este_valid(fisier_intrare) și rezolva(fisier_intrare) cu fișierul de intrare specificat în codul sursă. Dacă datele sunt valide, funcția rezolva(fisier_intrare) va fi apelată pentru a procesa datele și a scrie rezultatul în fișierul "cautafibo.out". Dacă datele nu sunt valide, programul se va încheia cu sys.exit(0) și nu va ajunge la apelarea funcției rezolva(fisier_intrare)