Un algoritm generează în ordine descrescătoare, toate numerele de n
cifre (n<9
), cu cifrele în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5
, primele cinci soluţii generate sunt 56789
, 45789
, 45679
, 45678
, 36789
, precizaţi care sunt următoarele trei soluţii generate, în ordinea obţinerii lor, separate prin exact un spațiu.
Următoarele probleme se referă la mulţimea de numere reale M={x
1
, x
2
, …, x
n
}
(n≤1000
). Care dintre acestea, comparativ cu celelalte, admite un algoritm care se încheie după un număr minim de paşi?
Varianta 1 |
sortarea elementelor mulţimii |
Varianta 2 |
generarea elementelor produsului cartezian |
Varianta 3 |
determinarea elementului minim al mulţimii |
Varianta 4 |
generarea tuturor permutărilor mulţimii |
In timpul procesului de generare a permutărilor mulţimii {1,2,…,n}
prin metoda backtracking, în tabloul unidimensional x
este plasat un element x[k]
(1≤k≤n
). Acesta este considerat valid dacă este îndeplinită condiţia:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Algoritmul de generare a tuturor numerelor de 5
cifre nenule, fiecare având cifrele ordonate strict crescător, este echivalent cu algoritmul de generare a:
Varianta 1 |
submulţimilor unei mulţimi cu |
Varianta 2 |
produsului cartezian a unor mulţimi de cifre |
Varianta 3 |
aranjamentelor de |
Varianta 4 |
combinărilor de |
Generând şirurile de maximum 3
caractere distincte din mulţimea {A,B,C,D,E}
, ordonate lexicografic, obţinem succesiv: A
, AB
, ABC
, ABD
, … . Ce şir va fi generat imediat după BAE
?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Un program citeşte o valoare naturală nenulă impară pentru n
şi apoi generează şi afişează în ordine crescătoare lexicografic toate combinaţiile formate din n
cifre care îndeplinesc următoarele proprietăţi:
0
;1
.Astfel, pentru n=5
, combinaţiile afişate sunt, în ordine, următoarele: 01010
, 01210
. Dacă se rulează acest program şi se citeşte pentru n
valoarea 7
, imediat după combinaţia 0101210
va fi afişată combinaţia:
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Pentru generarea numerelor cu n
cifre formate cu elementele mulţimii {0,2,9}
se utilizează un algoritm backtracking care, pentru n=2
, generează, în ordine, numerele 20
, 22
, 29
, 90
, 92
, 99
.
Dacă n=4
şi se utilizează acelaşi algoritm, care este numărul generat imediat după numărul 2009
?
Varianta 1 |
|
Varianta 2 |
|
Varianta 3 |
|
Varianta 4 |
|
Pentru generarea în ordine crescătoare a numerelor cu n
cifre formate cu elementele mulţimii {0,2,8}
se utilizează un algoritm backtracking care, pentru n=2
, generează, în ordine, numerele 20
, 22
, 28
, 80
, 82
, 88
.
Dacă n=4
şi se utilizează acelaşi algoritm, precizaţi câte numere generate sunt divizibile cu 100
?
Varianta 1 |
8 |
Varianta 2 |
90 |
Varianta 3 |
6 |
Varianta 4 |
10 |
Generarea tuturor cuvintelor de trei litere mici, nu neapărat distincte, ale alfabetului englez, se poate realiza cu ajutorul unui algoritm echivalent cu cel de generare a:
Varianta 1 |
produsului cartezian |
Varianta 2 |
combinărilor |
Varianta 3 |
aranjamentelor |
Varianta 4 |
permutărilor |
În câte dintre permutările elementelor mulţimii {‘I’,’N’,’F’,’O’}
vocalele apar pe poziţii consecutive?
Varianta 1 |
24 |
Varianta 2 |
6 |
Varianta 3 |
12 |
Varianta 4 |
4 |