1.1.1 Teoria: se realizează prin împărțiri repetate:
Împart numărul dat la 2, cu rest, apoi împart câtul la 2, cu rest, apoi împart noul cât la 2, cu rest ... până ajung la 0.
Citind resturile obținute (care nu pot fi decât 0, sau 1), invers, de la ultimul spre primul, obțin scrierea numărului în baza 2
1.1.2 Exemplu: convertim 82 din baza 10 în baza 2
82:2 = 41 (rest 0)
41:2 = 20 (rest 1)
20:2 = 10 (rest 0)
10:2 = 5 (rest 0)
5:2 = 2 (rest 1)
2:2 = 1 (rest 0)
1:2 = 0 (rest 1) <- Am obținut câtul 0, mă opresc.
Citim resturile invers, de jos în sus: 1 0 1 0 0 1 0. Am obținut cifrele reprezentării lui 82 în baza 2: 82(10) = 1010010(2)
1.2.1 Teoria: se face invers, prin înmulțiri și adunări
Iau prima cifră, o înmulțesc cu 2 și adun următoarea cifră. Înmulțesc rezultatul cu 2 și adun următoarea cifră. Înmulțesc rezultatul cu 2 și adun următoarea cifră etc.
Recunoașteți Schema lui Horner, nu?
1.2.2 Exemplu: convertim 1010010 din baza 2, în baza 10
1x2 + 0 = 2
2x2 + 1 = 5
5x2 + 0 = 10
10x2 + 0 = 20
20x2 + 1 = 41
41x2 + 0 = 82
Vezi un rezumat folositor aici
Este o structură de tip FIFO (First-In-First-Out = Primul (care) intră (este) primul (care) iese
Ca la o coadă la magazin, primul venit e primul servit
Este o structură de tip LIFO (Last-In-First-Out = Ultimul (care a) intrat (este) primul (care) iese
Ca la o stivă de cutii, una peste alt. Ultima așezată va fi prima luată
Vezi un rezumat folositor aici
Într-un graf noduri sunt unite prin muchii. Numărul de muchii care leagă un nod este numit gradul acelui nod
Într-un graf neorientat (neordonat), muchiile leagă două noduri fără să conteze ordinea acestora
Un graf este numit complet, dacă fiecare nod al său este legat de fiecare alt nod al său.
CALCULE:
De exemplu, un graf complet cu două noduri (A,B), are o singură muchie (între ele, AB)
Un graf complet cu trei noduri (A, B, C), are (1) muchia AB + (2) două muchii, care leagă C cu fiecare din cele două anterioare (AC, BC). În total ... 3
Un graf complet cu patru noduri (A, B, C, D) are ... 3 muchii (din graful ABC) + încă 3 (cele care leagă al patrulea nod, D, cu cele trei anterioare). În total (1+2)+3 = 6
Câte muchii va avea un graf complet cu 5 noduri? 1+2+3+4 = 10 ... etc.
CALCULE
pentru fiecare muchie trebuie să existe câte două noduri (la un graf orientat).
Într-un graf orientat (ordonat), muchia merge de la nodul de pornire, la nodul de sosire. Pot exista două muchii între aceleași două noduri
Reprezentăm în programare un graf printr-un vector cu n elemente, pentru n noduri, și o matrice de adiacență, a, pătrată, de n x n, fiecare linie corespunzând unui nod de pornire și fiecare coloană reprezentând un nod de sosire, având ca elemente pe a[i][j] pe 0 (dacă nu există drum de la nodul i la nodul j), respectiv 1 (dacă există un asemenea drum). Evident, pentru un graf neorientat, matricea va fi simetrică (dacă i este legat cu j, automat și j este legat de i).
Dintr-un nod inițial, rădăcină (se reprezintă, de obicei, în partea de sus), repetat apoi pentru fiecare alt nod, pot fi legațe două noduri, unul spre stânga, unul spre dreapta, sau un nod (fie spre stânga, fie spre dreapta), fie niciunul (atunci nodul se numește frunză sau nod terminal)
În imagine, 1 este rădăcina, iar 4, 5, 8, 9 și 7 sunt frunze. Din 3, 6 este un nod spre stânga, iar 7 este un nod spre dreapta.
La un arbore putem construi
Vectorul TATĂ (pentru fiecare nod, în ordine pentru 1, 2, ... în figură ne oprim la 9 ... se scrie nodul din care provine, sau 0 dacă nu are nici un nod de origine (cazul rădăcinii)
În figură, vectorul TATĂ va fi (pentru 1, punem un 0, nu are tată; pentru 2 punem 1; pentru 3 punem 1; pentru 4 punem 2, pentru 5 punem 2; pentru 6 punem 3; pentru 7 punem 3; pentru 8 punem 6; pentru 9 punem 6. Cum am luat în ordine nodurile, 1,2,3, 4,5,6,7,8,9, nu mai scriem „pentru cine”, ci doar tatăl, direct. Cui corespunde, rezultă din poziție)
TATĂ = [0, 1, 1, 2, 2, 3, 3, 6, 6]
Vectorul STÂNGA va descrie, similar, nodurile descendente, spre stânga (0 dacă nu coboară nimic spre stânga)
STÂNGA = [2, 4, 6, 0, 0, 8, 0, 0, 0] (primul 2 pentru că din 1, spre stânga, coboară 2; al doilea 4, pentru că din 2, spre stânga coboară 4, al patrulea este 0, pentru că din 4 nu coboară nimic spre stânga etc.)
Vectorul DREAPTA va descrie, similar, nodurile descendente, spre dreapta (0 dacă nu coboară nimic spre dreapta)
DREAPTA = [3, 5, 7, 0, 0, 5, 0, 0, 9]
Se pot formula probleme de genul „știind vectorul stânga și vectorul dreapta, să se reprezinte arborele”. Se rezolvă ca niște puzzle-uri. Se iau perechile, se desenează, apoi se lipesc împreună. Odată desenat, putem găsi rădăcina (cel din care pornesc toate) și frunzele (cele din care nu continuă nimic)
Fiecare tehnică/metodă de programare este benefică pentru anumite categorii de probleme, niciuna însă nu acoperă toate tipurile de probleme.
O secvență de program se apelează pe ea însăși.
vezi https://www.youtube.com/watch?v=MVRIt8x2Jco
În rezolvarea unei probleme cu prea multe variante posibile, se micșorează numărul de soluții posibile încercate revenind la o soluție parțială anterioară, atunci când soluția deja în construcție se dovedește nepotrivită. Este o tehnică utilizată, de exemplu, la jocul de șah pe calculator, în loc să încercăm toate mutările posibile, începem o secvență, iar dacă ea se dovedește ineficientă renunțăm la căutarea mai departe, schimbând „înapoi” ceva, în secvența deja începută.
vezi https://ro.wikipedia.org/wiki/Backtracking
vezi https://www.youtube.com/watch?v=LU404wd8pDU
vezi https://ro.wikipedia.org/wiki/Divide_et_impera_(informatică)
vezi https://www.youtube.com/watch?v=BvWwX5XWaEc
vezi https://ro.wikipedia.org/wiki/Algoritm_greedy
SQL este un limbaj pentru interogarea structurată a bazelor de date (Structured Query Language)
vezi https://www.w3schools.com/sql/
vedeți și https://www.w3schools.com/sql/trysql.asp?filename=trysql_select_orderby_desc
vedeți și https://www.w3schools.com/sql/trysql.asp?filename=trysql_select_where_and