Articole

Considerăm un graf neorientat ponderat (cu costuri) conex G. Se numește arbore parțial un graf parțial al lui G care este arbore. Se numește arbore parțial de cost minim un arbore parțial pentru care suma costurilor muchiilor este minimă. Dacă graful nu este conex, vorbim despre o pădure parțială de cost minim. Algoritmul lui Kruskal permite determinarea unui arbore parțial de cost mini ... (mai mult)

Operațiile standard de intrare/ieșire se fac cu tastatură și ecranul, dar este posibil să realizăm și citiri din fișiere text, respectiv scrieri în fișiere text. Pentru a realiza operațiile propriu-zise, fișierele sunt asociate cu fluxuri de date, iar operațiile sunt similare cu cele cu tastatura și ecranul. Etapele lucrului cu fișiere text În C++ există mai multe modalități de lucru cu ... (mai mult)

Ridicarea la putere este o operație binecunoscută, formulă uzuală fiind: $$A^n=\prod _{i=1}^{n}A=\underset{\text{de }n\text{ ori}}{\underbrace{A\times A\times \dots \times A}}$$ Un algoritm care implementează această metodă va avea complexitate liniară, $O(n)$: int Putere(int A , int n) { int P = 1 ; for(int i = 1 ; i <= n ; i ++) P = P * A; return P; } Descriere ... (mai mult)

În numeroase probleme de informatică se cere determinarea restului împărțirii unui anumit număr (de regulă rezultat ale unui calcul) la o valoare dată, N. De cele mai multe ori numărul nu poate fi determinat direct, valoarea sa fiind prea mare. În aceste situații intervine aritmetica modulară, în care restul cerut se determină facând operații cu resturi la împărțirea cu N a unor rezultate ... (mai mult)

Algoritmul lui Euclid pentru determinarea celui mai mare divizor comun a două numere naturale are următoarea consecință: pentru două numere naturale nenule $a$, $b$ există numerele întregi $x$, $y$ astfel încât $a\cdot x+b\cdot y=d$, unde $d=(a,b)$ este cel mai mare divizor comun al lui $a$ și $b$. Algoritmul lui Euclid Algoritmul lui Euclid se bazează pe următoar ... (mai mult)

Analiza combinatorică este un domeniu al matematicii care studiază modalitățile de numărare ale elementelor mulțimilor finite, precum și de alegere și aranjare a lor. Numeroase concepte specifice acestui domeniu intervin și în probleme de algoritmică. Produsul cartezian Fie $n\in \mathbb{N}$ și mulțimile $A_1$, $A_2$., …, $A_n$. Produsul cartezian \( A_1 \times A_2 \times … ... (mai mult)

Secvențele escape au fost folosite inițial în limbajele C/C++; în prezent sunt folosite în numeroase alte limbaje, precum Java, C# sau PHP. Ele sunt succesiuni de caractere care cu alt înțeles decât cel direct atunci când sunt folosite într-un literal caracter sau șir de caractere, fiind înlocuite cu caractere care nu ar putea fi folosite în mod direct. Toate secvențele escape încep cu c ... (mai mult)

Ciurul lui Eratostene este o metodă rapidă prin care stabilește despre fiecare număr natural mai mic sau egal cu un n dat dat este prim sau nu. Valoarea lui n trebuie să fie suficient de mică pentru a putea declara un tablou P cu n+1 elemente, un element P[k] având valoarea 1 dacă k este prim, respectiv valoarea 0 dacă k nu este prim. Următoarea secvență C++ construiește tabloul P[]: in ... (mai mult)

Operațiile pe biți, descrise aici sunt foarte rapide și au o serie de aplicații utile în practică. Acesta articol prezintă o parte dintre ele, limbajul de programare folosit fiind C/C++. Reamintim faptul că biții din reprezentarea internă a unui număr întreg se numerotează începând de la 0, de la dreapta spre stânga. Înmulțirea cu puteri ale lui 2 Înmulțirea cu o puterea lui 2 se face ... (mai mult)

Problemă: Se dă o matrice binară, reprezentând harta unui teren (labirint, clădire, tablă de joc, etc.), în care valorile 0 reprezintă zone libere, iar cele egale cu 1 reprezintă obstacole. Într-o zonă aflată la coordonate cunoscute se află un mobil, care se poate deplasa prin matrice, trecând din zona curenta în una din cele patru zone vecine de pe aceeași linie sau aceeași coloană, dacă ... (mai mult)