Grade 11 · liceuRead in English
Algoritmi pentru clasa a xi-aGrade 11
Algoritmii de clasa a xi-a, capitol cu capitol. Citești ideea, rulezi codul pe exemple și vezi ce ai învățat.
- 62algoritmi
- 7capitole
- 1clasă
62 de algoritmi
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…