1/5
00:00
Fie o matrice cu linii și coloane, care conține numere reale, cu următoarea proprietate: elementele de pe fiecare linie, precum și de pe fiecare coloană, sunt sortate crescător.Putem construi un algoritm pentru a verifica dacă un număr dat apare în matrice. Care este complexitatea timp minimă a acestuia?
Un muzician generează toate secvențele de trei note muzicale din mulțimea {DO, RE, MI}. Într-o secvență notele muzicale se pot repeta. Fie numărul total de secvențe obținute. Care este valoarea lui ?
Se consideră n, f și i numere întregi pozitive, cu , și următoarea secvență în pseudocod.Care dintre următoarele secvențe de pseudocod conduc la aceeași valoare a lui f ca secvența de mai sus?
f <- 1
pentru i <- 2, n execută
f <- f*i
I
f <- 1
i <- 1
execută
i <- i+1
f <- f*i
cât timp i<n
II
f <- 1
i <- 2
cât timp i<=n
execută
f <- f*i
i <- i+1
III
f <- 1
i <- 2
cât timp i<n
execută
i <- i+1
f <- f*i
IV
f <- 1
pentru i <- 2, n execută
f <- f*(n-i)i crește la și f se înmulțește de fiecare dată, iar bucla se oprește când i ajunge la n (pentru face un singur pas): . II: înmulțește cu : . III: crește i înainte de înmulțire, deci înmulțește doar cu : . IV: ultimul factor este , deci . Corecte: I și II.Fie o mulțime de simboluri cu care se pot forma șiruri distincte de lungime (). Fiecare dintre cele simboluri apare în fiecare șir de ori, , .Pentru simbolurile {A, B, C} care apar de , și, respectiv, ori, primele șiruri generate cu metoda backtracking sunt: ABBBCC, ABBCBC, ABBCCB, ABCBBC. Care este următorul șir care va fi generat?
ACCBBBABCBCBABCCBBABBBCCACBBBCBABCCBABCBBC, prefixul ABCB poate continua și cu CB (rămân de pus un B și un C), deci următorul șir este ABCBCB; abia apoi urmează ABCCBB.Fie un graf neorientat cu noduri (). Care este numărul maxim de muchii ale grafului?