RebecaBud: Pagină nouă: == Enunt == Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T. == Cerinţa == Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1],...

2024-06-03T17:12:25Z

Pagină nouă: == Enunt == Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T. == Cerinţa == Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1],...

New page

== Enunt ==
Fie șirul Fibonacci, dat prin F[1] = 1, F[2] = 1 și relația de recurență F[k] = F[k-1] + F[k-2], k ≥ 3 . Se consideră un număr natural N și un șir A[1], A[2],...,A[N] de N numere naturale distincte. Se consideră de asemenea și un număr natural T.
== Cerinţa ==
Să se scrie un program care determină o valoare D ce reprezintă numărul termenilor din șirul Fibonacci F[1], F[2] ,..., F[T] care sunt divizibili cu cel puțin unul dintre numerele A[1], A[2],...,A[N].
== Date de intrare ==
Fișierul de intrare fibodiv.in conţine pe prima linie numerele N și T separate printr-un spațiu, iar pe a doua linie N numere naturale, A[1], A[2],...,A[N], separate prin câte un spațiu.
== Date de ieșire ==
Fișierul de ieșire fibodiv.out va conţine pe prima linie numărul natural D,cu semnificația de mai sus.
== Restricţii şi precizări ==
* '''1 ≤ N ≤ 15'''
* '''2 ≤ T ≤ 1018'''
* '''2 ≤ A[i] ≤ 50, 1 ≤ i ≤ N'''
== Exemplul 1 ==
; fibodiv.in

3 20
3 6 10
; fibodiv.out

6
== Explicație ==
N = 3; T = 20; A1 = 3, A2 = 6, A3 = 10. Primii 20 de termeni ai șirului Fibonacci sunt: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. Printre aceștia se găsesc 6 termeni divizibili cu cel puțin unul dintre numerele 3, 6, 10 și anume: 3, 21, 144, 610, 987, 6765.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def fibonacci_sequence(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i - 1] + fib[i - 2])
return fib

def count_divisible_terms(fib_sequence, divisors):
count = 0
for term in fib_sequence:
for divisor in divisors:
if term % divisor == 0:
count += 1
break
return count

def main():
with open("fibodiv.in", "r") as fin:
N, T = map(int, fin.readline().split())
divisors = list(map(int, fin.readline().split()))

fib_sequence = fibonacci_sequence(T)
count = count_divisible_terms(fib_sequence, divisors)

with open("fibodiv.out", "w") as fout:
fout.write(str(count) + "\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

2053 - Fibo Div - Revision history