Algoritmi elementariRead in English
266 de algoritmi elementari în C++, explicați și rulabili
Toată materia de informatică de liceu (clasele 9–12), de la cifrele unui număr la grafuri și programare dinamică. Citești ideea, modifici codul, îl rulezi pe un compilator adevărat și îți urmărești progresul cu un cont gratuit.
- 266algoritmi
- 27capitole
- 4clase
266 de algoritmi
Clasa a IX-aGrade 9
0%0%
Cifrele unui număr
Digits of a number · 15 algoritmi
- Numărul de apariții ale cifrei kNumber of occurrences of digit kParcurgem cifrele lui n și numărăm câte sunt egale cu k. Cu do-while, pentru n = 0 și k…
- Cel mai mare număr format cu cifrele lui nLargest number formed from the digits of nNumărăm de câte ori apare fiecare cifră, într-un vector de frecvență cu 10 poziții…
- Cifra de controlCheck digit (digital root)Cifra de control se obține înlocuind numărul cu suma cifrelor lui, în mod repetat, până…
- Cifra maximă și cifra minimăLargest and smallest digitPornim cu maximul 0 (cea mai mică cifră posibilă) și minimul 9 (cea mai mare cifră…
- Verificarea cifrelor distincteChecking for distinct digitsVerifică dacă toate cifrele lui n sunt diferite. Ținem minte ce cifre am văzut deja…
- Afișarea cifrelor în ordinea din numărPrinting the digits in their order in the numberCu n % 10 cifrele ies de la dreapta la stânga. Ca să le afișăm de la stânga la dreapta,…
- Dublarea cifrelor impareDoubling the odd digitsFiecare cifră impară a lui n apare de două ori în rezultat. Construim rezultatul de la…
- Eliminarea cifrelor pareRemoving the even digitsConstruim un număr nou din cifrele impare ale lui n, păstrând ordinea lor. Cifrele vin…
- Înlocuirea unei cifre cu altaReplacing one digit with anotherÎnlocuiește în n fiecare apariție a cifrei x cu cifra y. Reconstruim numărul de la…
- Număr palindromPalindrome numberUn număr este palindrom dacă se citește la fel de la stânga la dreapta și de la dreapta…
- Numărul de cifre ale unui numărNumber of digits of a numberNumără cifrele lui n tăind la fiecare pas ultima cifră (n / 10) până când numărul devine…
- Oglinditul unui numărReverse of a numberConstruiește numărul format din cifrele lui n scrise în ordine inversă. La fiecare pas…
- Prima cifră a unui numărFirst digit of a numberPrima cifră (cea din stânga) rămâne după ce tăiem toate celelalte cifre: împărțim la 10…
- Produsul cifrelor unui numărProduct of the digits of a numberÎnmulțește cifrele lui n. Produsul pornește de la 1 (elementul neutru al înmulțirii), nu…
- Suma cifrelor unui numărSum of the digits of a numberAdună cifrele lui n. Ultima cifră se obține cu n % 10, apoi este eliminată cu n / 10.…
0%
Divizibilitate și numere prime
Divisibility and prime numbers · 17 algoritmi
- Cmmdc prin împărțiri repetate (algoritmul lui Euclid)GCD by repeated division (Euclid's algorithm)Cel mai mare divizor comun nu se schimbă dacă înlocuim perechea (a, b) cu (b, a % b).…
- Cmmdc prin scăderi repetateGCD by repeated subtractionScădem numărul mai mic din cel mai mare până când devin egale; valoarea comună este…
- Cel mai mic multiplu comunLeast common multipleSe folosește relația cmmdc(a, b) * cmmmc(a, b) = a * b. Calculăm cmmdc-ul cu algoritmul…
- Descompunerea în factori primiPrime factorizationÎncercăm factorii d = 2, 3, 4, ... și împărțim n la d de câte ori se poate, numărând de…
- Divizorii primi ai unui numărPrime divisors of a numberEste descompunerea în factori primi, din care afișăm doar factorii, fără exponenți.…
- Divizorii proprii ai unui numărProper divisors of a numberDivizorii proprii sunt divizorii diferiți de 1 și de n. Folosim aceleași două treceri ca…
- Divizorii unui numărDivisors of a numberDivizorii vin în perechi: dacă d divide n, atunci și n / d divide n, iar unul dintre ei…
- Indicatorul lui EulerEuler's totient functionφ(n) este numărul valorilor din 1..n prime cu n. Dacă p1, p2, ... sunt divizorii primi…
- Număr perfectPerfect numberUn număr este perfect dacă este egal cu suma divizorilor săi mai mici decât el (6 = 1 +…
- Numărul divizorilorNumber of divisorsPentru fiecare d cu d * d <= n care divide n numărăm doi divizori, d și n / d, cu…
- Perechi de numere prime gemenePairs of twin primesDouă numere prime sunt gemene dacă diferența lor este 2 (de exemplu 11 și 13). Afișăm…
- Numere prime între eleCoprime numbersDouă numere sunt prime între ele dacă singurul lor divizor comun este 1, adică cmmdc(a,…
- Primele n numere primeThe first n prime numbersLuăm pe rând candidații 2, 3, 4, ... și îi testăm cu testul de primalitate până la √x.…
- Simplificarea unei fracțiiSimplifying a fractionO fracție a / b devine ireductibilă dacă împărțim numărătorul și numitorul la cmmdc(a,…
- Suma divizorilorSum of divisorsAdunăm divizorii în perechi (d și n / d) pentru d * d <= n; când n este pătrat perfect,…
- Test de primalitatePrimality testUn număr este prim dacă are exact doi divizori: 1 și el însuși (deci 0 și 1 nu sunt…
- Ultima cifră a lui x la puterea yLast digit of x to the power yUltima cifră a unui produs depinde doar de ultimele cifre ale factorilor. Ultimele cifre…
0%
Șiruri de numere citite pe rând
Number sequences read one at a time · 13 algoritmi
- Cea mai lungă secvență de elemente egaleLongest run of equal elementsO secvență înseamnă elemente aflate pe poziții consecutive. lung este lungimea secvenței…
- Cel mai mare termen Fibonacci cel mult egal cu nLargest Fibonacci term not greater than nGenerăm termenii șirului lui Fibonacci (1, 1, 2, 3, 5, ...) cât timp următorul termen nu…
- Cele mai mari două valoriThe two largest valuesȚinem minte cea mai mare valoare (max1) și a doua (max2). Dacă numărul nou depășește…
- Citirea unui șir terminat cu 0Reading a sequence terminated by 0Nu știm dinainte câte numere urmează: citim până la primul 0, care doar marchează…
- Cmmdc-ul mai multor numereGCD of several numberscmmdc(a, b, c) = cmmdc(cmmdc(a, b), c). Păstrăm în rez cmmdc-ul numerelor citite până…
- Al n-lea termen al șirului lui FibonacciThe n-th term of the Fibonacci sequenceȘirul lui Fibonacci începe cu 1, 1 și fiecare termen este suma celor doi dinaintea lui:…
- Maximul și minimul unui șirMaximum and minimum of a sequenceSe citesc n și apoi n numere întregi. Maximul și minimul pornesc de la primul număr…
- Numărarea elementelor cu o proprietateCounting elements with a propertySe citesc n și n numere naturale. Numărăm câte dintre ele sunt pare și câte au ultima…
- Numărul de schimbări de semnNumber of sign changesSe citesc n numere nenule. O schimbare de semn are loc între doi termeni consecutivi de…
- Perechi de termeni consecutivi cu o proprietatePairs of consecutive terms with a propertyNumărăm perechile de termeni aflați unul după altul care au aceeași paritate. Un șir de…
- Verificarea unei progresii aritmeticeChecking an arithmetic progressionUn șir este progresie aritmetică dacă diferența dintre doi termeni consecutivi este…
- Verificarea unui șir crescătorChecking a non-decreasing sequenceȘirul este crescător dacă fiecare număr este cel puțin egal cu cel dinaintea lui.…
- Suma și media aritmeticăSum and arithmetic meanSe citesc n și n numere întregi; se afișează suma și media lor aritmetică, cu două…
0%
Baze de numerație
Number bases · 6 algoritmi
- Conversia din baza 10 în baza bConverting from base 10 to base bÎmpărțim repetat n la b; resturile sunt cifrele în baza b, dar obținute de la ultima…
- Conversia în baza 10 cu puterile bazeiConverting to base 10 using powers of the baseVarianta pentru b <= 10, când numărul se poate citi ca întreg: cifrele lui se extrag de…
- Conversia din baza b în baza 10Converting from base b to base 10Numărul în baza b se citește ca text (poate conține A..F), apoi se aplică schema lui…
- Conversia între două baze oarecareConverting between any two basesTrecem prin baza 10: întâi transformăm numărul din baza b1 în baza 10 (schema lui…
- Numărul de biți 1 din scrierea în baza 2Number of 1 bits in binaryCifrele în baza 2 se obțin la fel ca cifrele în baza 10, doar că împărțim la 2: ultima…
- Verificarea unei puteri a lui 2Checking for a power of 2O putere a lui 2 are în baza 2 un singur bit de 1 (de exemplu 64 = 1000000). Scăzând 1,…
0%
Tablouri unidimensionale (vectori)
One-dimensional arrays (vectors) · 11 algoritmi
- Citirea și afișarea unui vectorReading and printing an arrayUn vector păstrează mai multe valori de același tip, accesate prin indice. Declarăm…
- Eliminarea elementelor pareRemoving the even elementsÎn loc să ștergem elementele pare unul câte unul (fiecare ștergere mută tot restul…
- Inserarea unei valori după fiecare element parInserting a value after every even elementParcurgem vectorul de la sfârșit spre început. Când v[i] este par, mutăm elementele de…
- Inserarea unui element pe o pozițieInserting an element at a positionCa să punem val pe poziția poz, facem loc: mutăm elementele v[poz..n] cu o poziție la…
- Inversarea unui vectorReversing an arrayInterschimbăm primul element cu ultimul, al doilea cu penultimul și așa mai departe:…
- Maximul și pozițiile pe care apareThe maximum and the positions where it appearsSpre deosebire de un șir citit pe rând, un vector poate fi parcurs de mai multe ori: la…
- Permutarea circulară la dreaptaCircular shift to the rightFiecare element se mută cu o poziție la dreapta, iar ultimul ajunge pe prima poziție.…
- Permutarea circulară la stângaCircular shift to the leftFiecare element se mută cu o poziție la stânga, iar primul ajunge pe ultima poziție.…
- Ștergerea elementului de pe o pozițieDeleting the element at a positionCa să ștergem elementul de pe poziția poz, mutăm elementele de după el cu o poziție la…
- Suma elementelor de pe pozițiile pare și impareSum of the elements on even and odd positionsAtenție la diferența dintre poziție (indicele i) și valoare (v[i]). Paritatea se…
- Verificarea unui vector simetricChecking a symmetric arrayUn vector este simetric (palindrom) dacă v[i] = v[n - i + 1] pentru orice i. Comparăm…
0%
Sortare și căutare
Sorting and searching · 10 algoritmi
- Căutarea binarăBinary searchFuncționează doar pe un vector sortat crescător. Comparăm x cu elementul din mijlocul…
- Căutarea secvențialăLinear searchVerificăm elementele pe rând, de la primul, până găsim valoarea x sau terminăm vectorul.…
- Interclasarea a doi vectori sortațiMerging two sorted arraysDin doi vectori sortați crescător construim un al treilea, tot sortat. Comparăm…
- Prima poziție cu valoare mai mare sau egală cu xFirst position with a value greater than or equal to xVarianta de căutare binară care nu se oprește la prima potrivire: într-un vector sortat…
- Sortarea cu std::sortSorting with std::sortBiblioteca <algorithm> are funcția sort, care ordonează în O(n log n). Primește…
- Sortarea după două criteriiSorting by two criteriaOrdonăm numerele crescător după ultima cifră, iar numerele cu aceeași ultimă cifră…
- Sortarea prin inserțieInsertion sortCa la aranjarea cărților de joc în mână: primele i - 1 elemente sunt deja sortate, iar…
- Sortarea prin metoda bulelorBubble sortParcurgem vectorul și interschimbăm oricare două elemente vecine aflate în ordine…
- Sortarea prin numărareCounting sortCând valorile sunt numere naturale mici (aici 0..10000), nu comparăm elemente: numărăm…
- Sortarea prin selecțieSelection sortPentru fiecare poziție i, de la 1 la n - 1, căutăm minimul din v[i..n] și îl aducem pe…
0%
Frecvență, sume parțiale și ciurul lui Eratostene
Frequency arrays, prefix sums and the Sieve of Eratosthenes · 10 algoritmi
- Cifrele comune a două numereCommon digits of two numbersMarcăm în doi vectori de 10 poziții ce cifre apar în fiecare număr (aparA[c], aparB[c]).…
- Ciurul lui EratosteneSieve of EratosthenesGăsește toate numerele prime până la n. Pornim cu toate numerele nemarcate; pentru…
- Elementul majoritarMajority elementElementul majoritar apare de mai mult de n / 2 ori. Algoritmul prin vot (Boyer-Moore)…
- Numărul lipsă dintr-o permutareThe missing number in a permutationSe dau n și n - 1 numere distincte din mulțimea {1, 2, ..., n}; unul singur lipsește.…
- Secvența de lungime k cu suma maximăSubarray of length k with the maximum sumFereastra glisantă: calculăm suma primelor k elemente, apoi mutăm fereastra cu câte o…
- Secvența de sumă maximă (algoritmul lui Kadane)Maximum subarray sum (Kadane's algorithm)Parcurgem vectorul și păstrăm suma secvenței curente, care se termină la poziția i. Dacă…
- Sume parțialePrefix sumss[i] = v[1] + v[2] + ... + v[i], cu s[0] = 0, se calculează într-o singură trecere: s[i]…
- Valorile distincte și frecvențele lorDistinct values and their frequenciesDupă ce am construit vectorul de frecvență, valorile distincte sunt indicii val cu…
- Marcarea intervalelor cu vectorul de diferențeMarking ranges with a difference arrayAvem n poziții, inițial 0, și m operații „adună 1 pe pozițiile a..b”. În loc să…
- Vectorul de frecvențăFrequency arrayPentru valori naturale mici (aici 0..1000), frecv[x] reține de câte ori a apărut…
0%
Fișiere text
Text files · 5 algoritmi
- Citirea până la sfârșitul fișieruluiReading until the end of the fileFișierul date.in conține numere întregi, dar nu știm câte. Expresia fin >> x întoarce…
- Numărarea valorilor dintr-un fișierCounting the values in a fileFișierul date.in conține pe prima linie un număr natural k, iar pe următoarele linii un…
- Prelucrarea unui fișier pe liniiProcessing a file line by linegetline(fin, linie) citește un rând întreg, cu tot cu spații, până la '\n'. Bucla while…
- Scrierea formatată într-un fișierFormatted writing to a fileSe citește n din date.in și se scriu în date.out numerele de la 1 la n, câte cinci pe un…
- Suma numerelor de pe fiecare linieSum of the numbers on each lineFiecare linie din date.in conține câteva numere întregi, în număr necunoscut. Citim…
Clasa a X-aGrade 10
0%0%
Subprograme (funcții)
Subprograms (functions) · 11 algoritmi
- Funcție cmmdc și cmmmcGCD and LCM functionsFuncția cmmdc(a, b) aplică algoritmul lui Euclid prin împărțiri: cât timp b nu este 0,…
- Funcție de primalitatePrimality functionScriem o singură dată funcția estePrim(x), care întoarce true dacă x este prim, și o…
- Funcție cu vector ca parametru (maximul)Function with an array parameter (the maximum)Un vector se transmite unei funcții împreună cu numărul de elemente: int maxim(int v[],…
- Funcție care întoarce oglinditulFunction returning the reverse of a numberFuncția oglindit(x) construiește numărul cu cifrele lui x în ordine inversă și îl…
- Funcție pentru suma cifrelorFunction for the sum of digitsFuncția sumaCifre(x) primește numărul prin valoare (lucrează pe o copie, deci x-ul din…
- Interschimbare prin referințăSwapping by referenceComparăm două funcții care încearcă să schimbe între ele valorile a două variabile.…
- Minim și maxim întoarse prin referințăMinimum and maximum returned by referenceO funcție poate întoarce cu return o singură valoare. Când avem nevoie de mai multe…
- Numere prieteneAmicable numbersDouă numere a și b sunt prietene dacă suma divizorilor proprii ai lui a (divizorii mai…
- Numere superprimeSuper-prime numbersUn număr este superprim dacă toate prefixele lui sunt numere prime. De exemplu 239 este…
- Palindroame dintr-un intervalPalindromes in a rangeProblemă rezolvată prin descompunere în funcții mici: oglindit(x) întoarce răsturnatul…
- Variabile globale și variabile localeGlobal and local variablesO variabilă globală (declarată în afara funcțiilor) se vede din tot programul, pornește…
0%
Tablouri bidimensionale (matrice)
Two-dimensional arrays (matrices) · 15 algoritmi
- Bordarea matriceiBordering a matrixA borda o matrice înseamnă a-i adăuga o linie și/sau o coloană nouă pe margine. Aici…
- Citirea și afișarea unei matriceReading and printing a matrixO matrice cu n linii și m coloane se declară ca int a[101][101] și se parcurge cu două…
- Diagonala principală și diagonala secundarăMain diagonal and secondary diagonalÎntr-o matrice pătratică n x n, indexată de la 1, elementele de pe diagonala principală…
- Linia cu suma maximăRow with the maximum sumCalculăm suma fiecărei linii și o comparăm cu cea mai mare sumă găsită până acum. Pornim…
- Generarea matricei în serpentinăGenerating a serpentine (zigzag) matrixCompletăm matricea cu numerele 1, 2, ..., n * m „în zigzag”: liniile impare de la stânga…
- Verificarea matricei simetriceChecking a symmetric matrixO matrice pătratică este simetrică față de diagonala principală dacă a[i][j] == a[j][i]…
- Parcurgerea în spiralăSpiral traversalȚinem patru margini: sus, jos, stanga, dreapta. La fiecare tură parcurgem linia de sus…
- Produsul a două matriceProduct of two matricesProdusul se poate face doar dacă numărul de coloane al lui A este egal cu numărul de…
- Punct șaSaddle pointUn punct șa este un element care este minim pe linia lui și maxim pe coloana lui. Pentru…
- Rotirea unei matrice cu 90 de gradeRotating a matrix by 90 degreesLa rotirea în sensul acelor de ceasornic, prima coloană citită de jos în sus devine…
- Ștergerea unei linii și a unei coloaneDeleting a row and a columnCa la vectori, ștergerea înseamnă mutarea elementelor peste cel șters. Pentru linia k,…
- Suma pe linii și pe coloaneRow sums and column sumsPentru suma liniei i ținem i fix și plimbăm j de la 1 la m. Pentru suma coloanei j facem…
- Generarea tablei de șahGenerating a chessboardPe o tablă de șah, culoarea pătratului depinde doar de paritatea sumei i + j: pătratele…
- Transpusa unei matriceTranspose of a matrixTranspusa matricei a (n linii, m coloane) are m linii și n coloane: linia i a transpusei…
- Cele patru zone ale matricei pătraticeThe four zones of a square matrixCele două diagonale împart o matrice pătratică în patru zone (fără elementele de pe…
0%
Șiruri de caractere
Character strings · 16 algoritmi
- Cel mai lung cuvântThe longest wordÎmpărțim fraza în cuvinte cu strtok și păstrăm cuvântul cu lungimea cea mai mare într-un…
- Cifrul lui CezarCaesar cipherFiecare literă se înlocuiește cu litera aflată la k poziții mai departe în alfabet,…
- Cuvintele palindrom dintr-o frazăPalindrome words in a sentenceCombinăm două lucruri învățate: strtok împarte fraza în cuvinte, iar funcția…
- Eliminarea vocalelorRemoving the vowelsȘtergem vocalele chiar în șirul inițial, cu doi indici: i citește fiecare caracter, k…
- Extragerea numerelor dintr-un textExtracting the numbers from a textParcurgem textul; când întâlnim o cifră, construim numărul ca la clasa a IX-a (nr = nr *…
- Frecvența literelorLetter frequencyNumărăm de câte ori apare fiecare literă, fără să facem diferența între literele mari și…
- Împărțirea în cuvinte cu strtokSplitting into words with strtokstrtok(s, separatori) întoarce primul cuvânt din s; apelurile următoare se fac cu NULL…
- Înlocuirea unui cuvânt cu altulReplacing one word with anotherSe citesc un text și două cuvinte, vechi și nou (fiecare pe câte un rând). Construim…
- Transformarea în majuscule și minusculeConverting to uppercase and lowercaseÎn tabelul ASCII literele mari 'A'..'Z' și cele mici 'a'..'z' sunt la distanță…
- Numărarea cuvintelorCounting the wordsFără strtok: un cuvânt începe acolo unde un caracter diferit de spațiu urmează după un…
- Numărarea vocalelorCounting the vowelsPentru fiecare caracter verificăm dacă apare în șirul "aeiouAEIOU" cu funcția strchr:…
- Operații cu std::stringOperations with std::stringClasa string din <string> își gestionează singură memoria: se atribuie cu =, se lipește…
- Parcurgerea unui șir și lungimea luiWalking a string and its lengthUn șir de caractere în stil C este un vector de char terminat cu caracterul nul '\0'.…
- Sortarea alfabetică a cuvintelorSorting words alphabeticallySeparăm fraza în cuvinte cu strtok și le copiem într-o matrice de caractere cuv[100][31]…
- Verificarea unui șir palindromChecking a palindrome stringÎntâi păstrăm doar literele, transformate în minuscule (așa „Ele fac cafele” devine…
- Verificarea anagramelorChecking anagramsDouă cuvinte sunt anagrame dacă au aceleași litere, de același număr de ori, în altă…
0%
Tipul struct
The struct type · 5 algoritmi
- Compararea datelor calendaristiceComparing calendar datesO dată calendaristică are trei câmpuri: zi, luna, an. Două date se compară întâi după…
- Adunarea duratelor (ore, minute, secunde)Adding durations (hours, minutes, seconds)O durată se ține într-o structură cu trei câmpuri. Ca să adunăm ușor, transformăm durata…
- Elevi sortați după medie și numeStudents sorted by average and nameTipul struct grupează sub un singur nume date de tipuri diferite: struct Elev { char…
- Operații cu fracțiiOperations with fractionsO fracție are două câmpuri, numărătorul a și numitorul b, deci o reprezentăm cu struct…
- Puncte în planPoints in the planeUn punct are coordonatele x și y: struct Punct { int x, y; }. Distanța dintre două…
0%
Recursivitate
Recursion · 12 algoritmi
- Afișarea cifrelor în ordine, recursivPrinting the digits in order, recursivelyContează unde punem afișarea față de autoapel. În inOrdine afișăm DUPĂ autoapel: întâi…
- Cmmdc recursivRecursive GCDAlgoritmul lui Euclid scris recursiv: cmmdc(a, 0) = a, iar cmmdc(a, b) = cmmdc(b, a %…
- Conversia în baza 2, recursivConverting to base 2, recursivelyLa conversia prin împărțiri repetate la 2, resturile se obțin în ordine inversă față de…
- Factorial recursivRecursive factorialDefiniția matematică este deja recursivă: 0! = 1 și n! = n * (n - 1)!. Funcția are o…
- Fibonacci recursivRecursive FibonacciȘirul lui Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). Transcrierea…
- Funcția AckermannThe Ackermann functionFuncția Ackermann are două argumente: A(0, n) = n + 1; A(m, 0) = A(m - 1, 1); A(m, n) =…
- Funcția Manna-PnueliThe Manna-Pnueli functionFuncția este definită astfel: f(x) = x - 1 dacă x >= 12, altfel f(x) = f(f(x + 2)).…
- Inversarea unui șir de caractere, recursivReversing a string, recursivelyFuncția inverseaza(s, i) se ocupă de caracterele de la poziția i până la final. Dacă…
- Numărul de apariții într-un vector, recursivNumber of occurrences in an array, recursivelyNumărul aparițiilor lui x printre primele n elemente este numărul aparițiilor printre…
- Palindrom recursivRecursive palindrome checkUn cuvânt este palindrom dacă primul și ultimul caracter sunt egale și ce rămâne între…
- Puterea unui număr, recursivPower of a number, recursivelyVarianta directă folosește a^n = a * a^(n - 1) și face n apeluri. Varianta rapidă…
- Suma cifrelor, recursivSum of digits, recursivelySuma cifrelor lui n este ultima cifră (n % 10) plus suma cifrelor numărului rămas după…
0%
Divide et impera
Divide and conquer · 8 algoritmi
- Căutare binară recursivăRecursive binary searchVectorul este sortat crescător. Comparăm x cu elementul din mijloc: dacă sunt egale am…
- Cmmdc-ul elementelor unui vector prin divide et imperaGCD of an array's elements with divide and conquerCmmdc-ul unei porțiuni este cmmdc-ul dintre cmmdc-ul jumătății stângi și cmmdc-ul…
- Maximul unui vector prin divide et imperaMaximum of an array with divide and conquerCele trei etape ale metodei: împărțim porțiunea [st, dr] în două jumătăți, la mijlocul m…
- Numărul elementelor pare prin divide et imperaCounting the even elements with divide and conquerAcelași tipar ca la sumă: rezultatul pentru porțiunea [st, dr] este suma rezultatelor…
- Sortarea prin interclasare (Merge Sort)Merge sortÎmpărțim vectorul în două jumătăți, sortăm recursiv fiecare jumătate, apoi le…
- Sortarea rapidă (Quick Sort)Quick sortAlegem un pivot (aici elementul din mijloc) și rearanjăm porțiunea astfel încât în…
- Suma elementelor prin divide et imperaSum of the elements with divide and conquerSuma porțiunii [st, dr] este suma jumătății stângi [st, m] plus suma jumătății drepte [m…
- Turnurile din HanoiTowers of HanoiAvem n discuri pe tija A, în ordine descrescătoare a mărimii, și vrem să le mutăm pe…
Clasa a XI-aGrade 11
0%0%
Metoda backtracking
Backtracking · 12 algoritmi
- Generarea aranjamentelorGenerating arrangements (k-permutations)Afișează, în ordine lexicografică, toate aranjamentele de n elemente luate câte k:…
- Colorarea hărțilorMap coloringO hartă are n țări numerotate de la 1, iar m perechi (a, b) spun că țările a și b sunt…
- Generarea combinărilorGenerating combinationsAfișează toate submulțimile cu k elemente ale mulțimii {1, ..., n} (combinări de n luate…
- Drumuri într-un labirintPaths in a mazeLabirintul este o matrice n × m cu 0 (liber) și 1 (zid). Pornim din colțul stânga-sus…
- Problema celor n dameThe n-queens problemAșezăm n dame pe o tablă n × n astfel încât să nu se atace (nicio pereche pe aceeași…
- Generarea parantezărilor corecteGenerating balanced parenthesesAfișează, în ordine lexicografică ('(' înaintea lui ')'), toate șirurile corecte formate…
- Partițiile unui număr naturalPartitions of a natural numberAfișează toate modurile de a scrie n ca sumă de numere naturale nenule, fără să conteze…
- Permutări cu vecini de parități diferitePermutations with neighbours of alternating parityAfișează permutările mulțimii {1, ..., n} în care oricare două elemente vecine au…
- Generarea permutărilorGenerating permutationsAfișează, în ordine lexicografică, toate permutările mulțimii {1, 2, ..., n}. Soluția se…
- Plata unei sume cu monede datePaying a sum with given coinsAvem n tipuri de monede, cu valorile v[1..n], din fiecare câte vrem. Afișăm toate…
- Produsul cartezianCartesian productSe dau n mulțimi; mulțimea i este {1, 2, ..., a[i]}. Se afișează toate elementele…
- Generarea submulțimilorGenerating subsetsAfișează toate submulțimile nevide ale mulțimii {1, ..., n}, în ordine lexicografică.…
0%
Metoda greedy
The greedy method · 6 algoritmi
- Acoperirea unui segment cu număr minim de intervaleCovering a segment with the minimum number of intervalsVrem să acoperim segmentul [A, B] folosind cât mai puține dintre cele n intervale date…
- Planificarea spectacolelorScheduling shows (activity selection)Într-o sală se pot ține n spectacole; spectacolul i începe la ora s[i] și se termină la…
- Plata unei sume cu număr minim de bancnotePaying a sum with the minimum number of banknotesSe dau n valori de bancnote (din fiecare avem oricâte) și o sumă S. Strategia greedy:…
- Problema rucsacului (varianta fracționară)The knapsack problem (fractional version)Un rucsac suportă cel mult G kilograme. Avem n obiecte; obiectul i are greutatea g[i] și…
- Suma maximă cu k elementeMaximum sum with k elementsDintr-un șir de n numere întregi alegem exact k elemente (pe poziții diferite) cu suma…
- Minimizarea timpului mediu de așteptareMinimizing the average waiting timeLa un ghișeu așteaptă n clienți; servirea clientului i durează t[i] minute. Timpul de…
0%
Programare dinamică
Dynamic programming · 10 algoritmi
- Cel mai lung subșir comunLongest common subsequenceSe dau două cuvinte a și b. Căutăm cel mai lung șir de litere care apare ca subșir…
- Distanța de editareEdit distanceCâte operații sunt necesare, minim, ca să transformăm cuvântul a în cuvântul b? O…
- Drum de sumă maximă în matriceMaximum-sum path in a matrixÎntr-o matrice n × m pornim din colțul (1, 1) și ajungem în (n, m) mergând doar la…
- Numărul de drumuri într-o grilă cu obstacoleNumber of paths in a grid with obstaclesO grilă n × m are celule libere (0) și obstacole (1). Câte drumuri duc din (1, 1) în (n,…
- Numărul minim de monedeMinimum number of coinsAvem n tipuri de monede (din fiecare oricâte) și vrem să plătim exact suma S cu cât mai…
- Numărul partițiilor unui numărNumber of partitions of a numberÎn câte moduri se poate scrie n ca sumă de numere naturale nenule, fără să conteze…
- Problema rucsacului (varianta discretă)The knapsack problem (0/1 version)Un rucsac suportă cel mult G kilograme; avem n obiecte cu greutățile g[i] și valorile…
- Subșirul strict crescător de lungime maximăLongest strictly increasing subsequenceDintr-un șir de n numere alegem un subșir (elemente în ordinea din șir, nu neapărat…
- Suma maximă în triunghiul de numereMaximum sum in a number triangleUn triunghi are n linii; linia i conține i numere. Pornim din vârf și la fiecare pas…
- Numărul de moduri de a urca o scarăNumber of ways to climb a staircaseO scară are n trepte; la fiecare pas urcăm fie o treaptă, fie două. În câte moduri putem…
0%
Alocare dinamică: liste, stive, cozi
Dynamic allocation: lists, stacks, queues · 10 algoritmi
- Coada implementată cu o listă înlănțuităQueue implemented with a linked listCoada se ține ca o listă simplu înlănțuită cu doi pointeri: prim (de unde se scoate) și…
- Coada implementată cu un vectorQueue implemented with an arrayCoada este o structură de tip FIFO (primul intrat, primul ieșit): se adaugă la sfârșit…
- Evaluarea unei expresii în formă poloneză postfixatăEvaluating an expression in postfix (reverse Polish) notationÎn forma postfixată operatorul se scrie după operanzi: (3 + 4) * 2 devine 3 4 + 2 *, iar…
- Inserarea într-o listă ordonatăInserting into a sorted listCitim n numere și le inserăm pe rând într-o listă simplu înlănțuită păstrată mereu în…
- Lista dublu înlănțuităDoubly linked listÎntr-o listă dublu înlănțuită fiecare nod reține atât adresa nodului următor (urm), cât…
- Lista simplu înlănțuită: creare, afișare, adăugareSingly linked list: create, print, addFiecare element al listei este un nod alocat dinamic (cu new), care reține o valoare…
- Ștergerea nodurilor dintr-o listă simplu înlănțuităDeleting nodes from a singly linked listSe creează o listă din n valori, apoi se șterg toate nodurile care conțin valoarea x.…
- Stiva implementată cu o listă înlănțuităStack implemented with a linked listVârful stivei este primul nod al unei liste simplu înlănțuite. push creează un nod nou…
- Stiva implementată cu un vectorStack implemented with an arrayStiva este o structură de tip LIFO (ultimul intrat, primul ieșit): se adaugă și se…
- Verificarea parantezelor cu o stivăChecking brackets with a stackUn șir format din paranteze ( ) [ ] { } este corect dacă fiecare paranteză deschisă se…
0%
Grafuri neorientate
Undirected graphs · 10 algoritmi
- Componentele conexeConnected componentsUn graf este conex dacă între oricare două noduri există un lanț. O componentă conexă…
- Detectarea unui cicluDetecting a cycleUn ciclu este un lanț simplu în care primul nod coincide cu ultimul. Facem o parcurgere…
- Lanțul de lungime minimă între două noduri (BFS)Shortest path between two nodes (BFS)Lungimea unui lanț este numărul de muchii. Parcurgerea în lățime pornită din x descoperă…
- Verificarea unui graf bipartitChecking a bipartite graphUn graf este bipartit dacă nodurile lui se pot împărți în două mulțimi A și B astfel…
- Listele de adiacențăAdjacency listsPentru fiecare nod reținem doar lista vecinilor lui. Muchia [x, y] se adaugă de două…
- Matricea de adiacență și gradele nodurilorAdjacency matrix and node degreesUn graf neorientat cu n noduri și m muchii se poate memora într-o matrice a cu n linii…
- Noduri izolate și graful completIsolated nodes and the complete graphUn nod izolat are gradul 0. Un graf este complet dacă oricare două noduri distincte sunt…
- Parcurgerea în adâncime (DFS)Depth-first search (DFS)Parcurgerea în adâncime merge cât de departe se poate: din nodul curent trece în primul…
- Parcurgerea în lățime (BFS)Breadth-first search (BFS)Parcurgerea în lățime vizitează nodurile „pe straturi”: întâi nodul de start, apoi toți…
- Verificarea unui lanțChecking a path (chain)O succesiune de noduri x1, x2, ..., xk este lanț dacă oricare două noduri consecutive…
0%
Grafuri orientate și drumuri minime
Directed graphs and shortest paths · 6 algoritmi
- Componentele tare conexeStrongly connected componentsUn graf orientat este tare conex dacă pentru oricare două noduri x și y există drum de…
- Drumuri minime de la un nod (algoritmul lui Dijkstra)Shortest paths from one node (Dijkstra's algorithm)Se cere costul minim al drumului de la nodul s la fiecare alt nod, când toate costurile…
- Gradele interne și externeIn-degrees and out-degreesÎntr-un graf orientat muchiile au sens și se numesc arce: arcul (x, y) pleacă din x și…
- Matricea drumurilor (algoritmul Roy-Warshall)Reachability matrix (Roy-Warshall algorithm)Matricea drumurilor are d[i][j] = 1 dacă există un drum (de lungime cel puțin 1) de la i…
- Drumuri minime între toate perechile de noduri (Roy-Floyd)Shortest paths between all pairs of nodes (Roy-Floyd)Fiecare arc (x, y) are un cost c ≥ 0. Matricea costurilor d pornește cu d[i][i] = 0,…
- Sortarea topologicăTopological sortArcul (x, y) înseamnă „x trebuie făcut înaintea lui y”. O sortare topologică este o…
0%
Arbori
Trees · 8 algoritmi
- Arborele parțial de cost minim (algoritmul lui Kruskal)Minimum spanning tree (Kruskal's algorithm)Kruskal construiește arborele parțial de cost minim pornind de la n arbori cu câte un…
- Arborele parțial de cost minim (algoritmul lui Prim)Minimum spanning tree (Prim's algorithm)Într-un graf neorientat conex cu costuri pe muchii căutăm un arbore parțial (n - 1…
- Arbore binar de căutare: inserare, căutare, afișare sortatăBinary search tree: insert, search, sorted printÎntr-un arbore binar de căutare, pentru fiecare nod, toate valorile din subarborele…
- Fiii, descendenții și ascendenții unui nodChildren, descendants and ancestors of a nodeArborele este dat prin vectorul de tați (t[rădăcină] = 0). Fiii lui x sunt nodurile i cu…
- Diametrul unui arboreDiameter of a treeDiametrul unui arbore este lungimea (numărul de muchii) celui mai lung lanț dintre două…
- Parcurgerile unui arbore binarTraversals of a binary treeÎntr-un arbore binar fiecare nod are cel mult doi fii: unul stâng și unul drept. Îl…
- Vectorul de tați: rădăcină, frunze, niveluri, înălțimeParent array: root, leaves, levels, heightUn arbore cu rădăcină se poate memora prin vectorul de tați: t[i] este tatăl nodului i,…
- Verificarea că un graf este arboreChecking whether a graph is a treeUn arbore este un graf neorientat conex și fără cicluri. Pentru un graf cu n noduri…
Clasa a XII-aGrade 12
0%0%
Numere mari
Big numbers · 9 algoritmi
- Adunarea a două numere mariAdding two big numbersAdunăm ca pe hârtie, de la unități spre stânga. La rangul i calculăm s = a[i] + b[i] +…
- Citirea și afișarea unui număr mareReading and printing a big numberUn număr cu zeci sau sute de cifre nu încape în long long, așa că îl citim ca șir de…
- Compararea a două numere mariComparing two big numbersFără zerouri nesemnificative, numărul cu mai multe cifre este mai mare. Dacă au același…
- Factorialul unui număr mareFactorial as a big numberDeja 21! depășește long long, dar n! = 1 * 2 * ... * n se poate construi înmulțind…
- Termenul n din șirul lui Fibonacci (număr mare)The n-th Fibonacci term (big number)Șirul este F(1) = F(2) = 1 și F(i) = F(i - 1) + F(i - 2). Termenii cresc exponențial…
- Împărțirea unui număr mare la un număr micDividing a big number by a small numberSpre deosebire de adunare, împărțirea începe de la cifra cea mai semnificativă, exact ca…
- Înmulțirea a două numere mariMultiplying two big numbersCifra a[i] (rangul 10^i) înmulțită cu cifra b[j] (rangul 10^j) contribuie la rangul…
- Înmulțirea unui număr mare cu un număr micMultiplying a big number by a small numberNumărul mic k (cel mult 10^9) încape într-un int, deci nu trebuie despărțit în cifre.…
- Scăderea a două numere mariSubtracting two big numbersCalculăm A - B. Dacă A < B, calculăm B - A și punem semnul minus în față. Scădem de la…
0%
Algoritmi pe grile: Lee și fill
Grid algorithms: Lee and flood fill · 6 algoritmi
- Fill — cea mai mare zonăFlood fill: the largest regionAceeași matrice de 0 și 1, dar acum vrem numărul de celule al celei mai mari zone de 1…
- Fill — numărul de zoneFlood fill: the number of regionsMatricea are n linii și m coloane, cu 1 pentru teren și 0 pentru apă. O zonă este un…
- Insule în 8 direcțiiIslands in 8 directionsCa la numărarea zonelor, dar două celule de uscat (1) aparțin aceleiași insule dacă se…
- Lee cu mai multe surseLee with multiple sourcesGrila conține 0 (liber), 1 (zid) și 2 (sursă, de exemplu o fântână). Pentru fiecare…
- Lee — drumul minim într-o grilăLee: the shortest path in a gridGrila are n linii și m coloane: 0 = liber, 1 = obstacol. Ne putem deplasa sus, jos,…
- Lee cu reconstituirea drumuluiLee with path reconstructionDupă ce Lee a completat matricea de distanțe, drumul se reface de la final spre start:…
0%
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]…
- 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!…
- 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,…
- 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…
- 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ă…
- 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…
- 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,…
- 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…
- 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…
0%
Tehnici avansate: doi pointeri, căutare binară pe răspuns, stive monotone
Advanced techniques: two pointers, binary search on the answer, monotonic stacks · 7 algoritmi
- Căutare binară pe răspunsBinary search on the answerAvem n capitole cu a[i] pagini, în ordine, și k corectori. Fiecare corector primește o…
- Doi pointeri — perechi cu suma x într-un vector sortatTwo pointers: pairs with sum x in a sorted arrayVectorul are n valori distincte, în ordine strict crescătoare. Vrem perechile de poziții…
- Element majoritar (Boyer-Moore)Majority element (Boyer-Moore)Elementul majoritar apare de mai mult de n / 2 ori. Algoritmul de vot ține un candidat…
- Fereastra glisantă — cea mai lungă secvență cu suma ≤ SSliding window: the longest subarray with sum ≤ SToate numerele sunt strict pozitive. Ținem o fereastră [st, dr] și suma ei. Extindem…
- Stiva monotonă — următorul element mai mareMonotonic stack: the next greater elementPentru fiecare a[i] căutăm prima valoare strict mai mare aflată în dreapta lui (sau -1).…
- Generarea submulțimilor cu măști de bițiGenerating subsets with bitmasksO submulțime a lui {a[0], ..., a[n-1]} se poate codifica printr-un număr masca între 0…
- Sume parțiale pe matrice2D prefix sumss[i][j] = suma elementelor din dreptunghiul cu colțurile (1, 1) și (i, j). Se calculează…
0%
Structuri de date și STL
Data structures and the STL · 9 algoritmi
- deque — minimul pe ferestre de lungime kdeque: sliding window minimum of length kPentru fiecare secvență de k elemente consecutive vrem minimul. Ținem într-un deque…
- queue — eliminarea din cercqueue: elimination in a circle (Josephus)n copii, numerotați de la 1 la n, stau în cerc. Se numără din k în k, iar copilul la…
- pair — reuniunea intervalelorpair: union of intervalspair<int, int> grupează două valori (first, second) și se compară lexicografic: întâi…
- stack — verificarea parantezelorstack: checking bracketsUn șir cu paranteze (), [] și {} este corect dacă fiecare paranteză închisă se…
- priority_queue — cele mai mari k valoripriority_queue: the k largest valuespriority_queue este un heap: top() dă elementul „cel mai important”, iar push și pop…
- set și map — frecvența cuvintelorset and map: word frequencyCitim cuvinte (litere mici) până la sfârșitul datelor. Un set<string> păstrează fiecare…
- Sortare cu comparatorSorting with a comparatorsort(început, sfârșit, cmp) ordonează după regula noastră: cmp(x, y) întoarce true dacă…
- Păduri de mulțimi disjuncte (union-find)Disjoint-set forests (union-find)Avem n elemente, fiecare inițial în propria mulțime. Operația 1 x y unește mulțimile lui…
- Containerul vector din STLThe STL vector containervector<int> este un tablou care își gestionează singur memoria: push_back adaugă la…
0%
Recapitulare pentru bacalaureat
Baccalaureate exam review · 10 algoritmi
- Fișier — cel mai mare și cel mai mic număr format din cifre dateFile: the largest and smallest number formed from given digitsCerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 cifre separate…
- Fișier — perechi de numere cu aceeași sumă a cifrelorFile: pairs of numbers with the same digit sumCerința (tip subiectul III.3): fișierul date.in conține pe prima linie n (2 ≤ n ≤ 10^6),…
- Fișier — cea mai lungă secvență de termeni cu aceeași paritateFile: the longest run of terms with the same parityCerința (tip subiectul III.3): fișierul date.in conține un șir de cel mult 10^6 numere…
- Fișier — valorile comune a două șiruri ordonateFile: the common values of two sorted sequencesCerința (tip subiectul III.3): fișierul date.in conține pe prima linie n și m (1 ≤ n, m…
- Fișier — valorile care apar o singură datăFile: the values that appear exactly onceCerința (tip subiectul III.3): fișierul date.in conține cel mult 10^6 numere naturale de…
- Matrice — contururi concentriceMatrix: concentric bordersCerința (tip subiectul III.2): se citește n (2 ≤ n ≤ 20). Construiți în memorie o…
- Subprogram — numărul format din cifrele pareSubprogram: the number formed from the even digitsCerința (tip subiectul III.1): subprogramul pare are un parametru n (0 ≤ n ≤ 10^9) și…
- Subprogram — câte numere dintr-un interval au un număr impar de divizoriSubprogram: how many numbers in a range have an odd number of divisorsCerința (tip subiectul III.1): subprogramul impare are parametrii a și b (1 ≤ a ≤ b ≤…
- Subprogram — eliminarea elementelor cu k cifre dintr-un tablouSubprogram: removing the elements with k digits from an arrayCerința (tip subiectul III.1): subprogramul elimina are parametrii v (un tablou cu n…
- Text — inversarea cuvintelor de lungime parăText: reversing the words of even lengthCerința (tip subiectul III.2): se citește un text de cel mult 100 de caractere, format…