Clasa a XII-a · 9 algoritmiRead in English

Matematică pentru programareMath for programming

Toți algoritmii din capitolul „Matematică pentru programare”, din programa de liceu: ideea explicată, complexitatea, exemple și cod C++ pe care îl poți modifica și rula chiar aici.

Fă-ți cont gratuit Vezi toți algoritmii

9algoritmi
6capitole
1clasă

Matematică pentru programare

Math for programming · 9 algoritmi

Ciur cu cel mai mic divizor prim și factorizare rapidăSmallest-prime-factor sieve and fast factorizationO variantă a ciurului lui Eratostene: în loc să marcăm doar „compus”, reținem în dp[x]…O(log n)
Combinări modulo un număr primCombinations modulo a primeCalculăm C(n, k) mod P, cu P = 1 000 000 007 (prim) și n ≤ 10^6. Avem C(n, k) = n! / (k!…O(log n)
Algoritmul lui Euclid extinsExtended Euclidean algorithmPe lângă d = cmmdc(a, b), găsim numere întregi x și y cu a * x + b * y = d. Dacă b = 0,…O(log n)
Exponențierea modularăModular exponentiationCalculăm a^n mod m pentru n de până la 10^18. Folosim aceeași idee ca la exponențierea…O(log n)
Exponențierea rapidăFast exponentiationCalculăm a^n cu aproximativ log2(n) înmulțiri în loc de n. Ideea: a^n = (a^2)^(n/2) dacă…O(log n)
Numărul și suma divizorilor din descompunerea în factori primiNumber and sum of divisors from the prime factorizationDacă n = p1^e1 * p2^e2 * ... * pk^ek, un divizor alege pentru fiecare prim un exponent…O(√n)
Numărul multiplilor lui k dintr-un intervalNumber of multiples of k in a rangeCâte numere din [a, b] se divid cu k? Numerele din [1, x] divizibile cu k sunt k, 2k,…O(log n)
Suma unei progresii aritmetice: formulă vs. buclăSum of an arithmetic progression: formula vs. loopProgresia are primul termen a, rația r și n termeni: a, a + r, ..., a + (n-1) * r. Bucla…O(1)
Triunghiul lui Pascal (combinări)Pascal's triangle (combinations)Combinările C(i, j) — numărul de submulțimi cu j elemente ale unei mulțimi cu i elemente…O(n²)