3344 - Fibonacci2 - Revision history

Oros Ioana Diana at 17:05, 18 May 2024

2024-05-18T17:05:06Z

@@ Line 4: / Line 4: @@
 Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2.
 Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.
-    for i in range(2, n + 1):
+= Date de intrare =
-        fib_i = (fib[i - 1] + fib[i - 2]) % 666013
+Programul citește de la tastatură numărul <code>n</code>.
-    return fib[n]
+= Date de ieșire =
-def verificare_restrictii(n):
+= Restricții și precizări =
-     if 1 <= n <= 2.000.000.000:
          return True
      else:
          return False
 if __name__ == "__main__":
-     n = int(input("Introduceți numărul n: "))
+     main()
 </syntaxhighlight>

Oros Ioana Diana at 17:44, 8 January 2024

2024-01-08T17:44:44Z

← Older revision		Revision as of 17:44, 8 January 2024
Line 10:		Line 10:
	== Restricții și precizări ==		== Restricții și precizări ==
	1 ≤ n ≤ 2.000.000.000		1 ≤ n ≤ 2.000.000.000
	== ~~Exemplu~~ 1 ==		== Exemplul 1 ==
	; Intrare		; Intrare
	: 6		: 6
Line 16:		Line 16:
	: 8		: 8
	<br>		<br>
	== ~~Exemplu~~ 2 ==		== Exemplul 2 ==
	; Intrare		; Intrare
	: 10		: 10
Line 25:		Line 25:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	#3344 - Fibonacci2		#3344 - Fibonacci2
	def ~~multiply~~(~~a, b, MOD~~):		def fibonacci_modulo_n(n):
	~~res~~ = ~~[[0, 0],~~ [0, ~~0]]~~		fib = [0, 1]
	~~for i in range(2):~~
	~~for j in range(2):~~
	~~for k in range(2):~~
	~~res[i][j] += (a[i][k] * b[k][j]) % MOD~~
	~~res[i][j~~] ~~%= MOD~~
	~~return res~~

	~~def power~~(~~matrix~~, ~~exp, MOD~~):		for i in range(2, n + 1):
	~~if exp == 1~~:		fib_i = (fib[i - 1] + fib[i - 2]) % 666013
	~~return matrix~~		fib.append(fib_i)
	~~if exp % 2 == 0:~~
	~~half_pow~~ = ~~power~~(~~matrix, exp //~~ 2~~, MOD~~)
	~~return multiply~~(~~half_pow, half_pow, MOD)~~
	~~else:~~
	~~return multiply(matrix, power(matrix, exp - 1, MOD), MOD~~)

	~~def fibonacci(n, MOD):~~		return fib[n]
	~~base_matrix = [~~[~~1, 1], [1, 0]]~~
	~~result_matrix = power(base_matrix,~~ n ~~- 1, MOD)~~
	~~return result_matrix[0][0~~] ~~% MOD~~

	def ~~main~~():		def verificare_restrictii(n):
	n = ~~int(input("Introduceți n~~: ~~"))~~		if 1 <= n <= 2.000.000.000:
	~~MOD = 666013~~		return True
	~~result = fibonacci(n, MOD)~~		else:
	~~print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")~~		return False

	if __name__ == "__main__":		if __name__ == "__main__":
	~~main~~()		n = int(input("Introduceți numărul n: "))

			result = fibonacci_modulo_n(n)

			print(f"Al {n}-lea termen al șirului Fibonacci modulo 666013 este: {result}")

	</syntaxhighlight>		</syntaxhighlight>

			== Explicatie ==
			Termenii sunt: 1 1 2 3 5 8 13 21 34 55 89 ...

Oros Ioana Diana: Pagină nouă: == Cerința == Șirul lui Fibonacci este definit astfel: Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013. == Date de intrare == Programul citește de la tastatură numărul n. == Date de ieșire == Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013. == Restricții și precizări == 1 ≤ n ≤ 2.000.000.000 == Exemplu 1 == ; Intrare : 6 ; Ieșire...

2023-12-12T18:52:37Z

Pagină nouă: == Cerința == Șirul lui Fibonacci este definit astfel: Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2. Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013. == Date de intrare == Programul citește de la tastatură numărul n. == Date de ieșire == Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013. == Restricții și precizări == 1 ≤ n ≤ 2.000.000.000 == Exemplu 1 == ; Intrare : 6 ; Ieșire...

New page

== Cerința ==
Șirul lui Fibonacci este definit astfel:

Fn={1Fn−1+Fn−2dacă n=1 sau n=2,dacă n>2.
Se dă un număr natural n. Determinați al n-lea termen al șirului, modulo 666013.
== Date de intrare ==
Programul citește de la tastatură numărul n.
== Date de ieșire ==
Programul va afișa pe ecran numărul F, reprezentând al n-lea termen al șirului, modulo 666013.
== Restricții și precizări ==
1 ≤ n ≤ 2.000.000.000
== Exemplu 1 ==
; Intrare
: 6
; Ieșire
: 8
<br>
== Exemplu 2 ==
; Intrare
: 10
; Ieșire
: 55
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#3344 - Fibonacci2
def multiply(a, b, MOD):
res = [[0, 0], [0, 0]]
for i in range(2):
for j in range(2):
for k in range(2):
res[i][j] += (a[i][k] * b[k][j]) % MOD
res[i][j] %= MOD
return res

def power(matrix, exp, MOD):
if exp == 1:
return matrix
if exp % 2 == 0:
half_pow = power(matrix, exp // 2, MOD)
return multiply(half_pow, half_pow, MOD)
else:
return multiply(matrix, power(matrix, exp - 1, MOD), MOD)

def fibonacci(n, MOD):
base_matrix = [[1, 1], [1, 0]]
result_matrix = power(base_matrix, n - 1, MOD)
return result_matrix[0][0] % MOD

def main():
n = int(input("Introduceți n: "))
MOD = 666013
result = fibonacci(n, MOD)
print(f"Al {n}-lea termen al șirului Fibonacci, modulo {MOD}, este: {result}")

if __name__ == "__main__":
main()
</syntaxhighlight>