Metode de programare XIE

Dacă ultima solutie afişată de către algoritmul backtracking pentru generarea tuturor permutărilor multimii {1,2,…,7} este 6,5,7,4,3,2,1, atunci următoarea solutie care va fi afişată este:

• 7,1,2,3,4,5,6

• 6,7,1,2,3,4,5

• 7,6,1,2,3,4,5

• 6,7,5,4,3,2,1

Dacă ultima solutie afişată de către algoritmul backtracking pentru generarea tuturor

permutărilor multimii {1,2,…,n} este 7,6,3,5,4,2,1, atunci următoarea solutie care va fi

afişată este:

• 7,6,4,1,2,5,3

• 7,1,2,3,4,5,6

• 7,6,4,1,2,3,5

• 7,6,5,3,4,2,1

Stabiliti care dintre următoarele metode de sortare se bazează pe tehnica de programare Divide et Impera:

• sortarea rapidă

• sortarea prin interschimbare

• sortarea prin interclasare

• sortarea prin numărare

• Cautarea binara

Considerând că a este un tablou format din n numere întregi nenule şi am definit anterior un subprogram cmmdc(x,y) care returnează cel mai mare divizor comun a două numere întregi nenule x şi y, construim următorul subprogram:

┌subprogram F(p,u)

dacă p=u atunci

F <- a[p]

altfel

k <-[(p + u)]/2

F <- cmmdc(F(p,k),F(k+1,u))

sf_daca

└■sf_subprogram

Ştiind că apelul subprogramului va fi F(1, n), precizati tehnica de programare utilizată în cadrul functiei F:

• Greedy

• Backtracking

• Divide et Impera

• Programare Dinamica

Folosind tehnica de programare backtracking pentru a genera toate permutările multimii {1,2,...,n}, o solutie se memorează sub forma unui tablou unidimensional x1, x2, ..., xn. Dacă au fost deja generate valori pentru componentele x1, x2, ..., xk-1, iar pentru componenta xk (1<k<n) au fost deja testate toate valorile posibile şi nu a fost gasită niciuna convenabilă, atunci:

• se încearcă alegerea unei noi valori pentru xk-1

• se încearcă alegerea unei noi valori pentru xk+1

• se încearcă alegerea unei noi valori pentru x1, oricare ar fi valoarea lui k

• se încheie algoritmul

• se initializeaza xk cu zero

Se generează toate numerele naturale de 4 cifre, cifre aflate în ordine strict crescătoare, orice două cifre vecine din fiecare număr generat fiind valori neconsecutive. De exemplu, numerele 1579 şi 2468 sunt în şirul numerelor

generate, în timp ce 3851, 1679, 5479 nu sunt. Câte numere se generează în total?

• 15

• 24

• 20

• 12

• 126

Se generează toate numerele de 3 cifre nenule si distincte, care pe poziţii pare au cifre pare, iar pe poziţii impare au cifre impare. Primele şase numere generate sunt: 123

125,127,129,143,145. Cate solutii sunt?

• 80

• 84

• 504

• 81

• 24

Se generează toate numerele de 5 cifre, cu cifre distincte, care pe poziţii pare au cifre pare, iar pe poziţii impare au cifre impare. Primele şase numere generate sunt: 10325, 10327, 10329, 10345, 10347, 10349. Care este

următorul număr generat după numărul 96785?

• 98103

• 98125

• 98123

• 96587

Se generează toate numerele de 5 cifre nenule si distincte, care pe poziţii pare au cifre pare, iar pe poziţii impare au cifre impare. Care este următorul număr generat după numărul 72389?

• 72541

• 72501

• 72398

• 72589

Se generează produsul cartezian al mulţimilor {1,2,3}, {1,2}, {3,4,5}.Câte dintre elementele produsului cartezian conţin cel puţin o valoare egalăcu 1?

• 6

• 18

• 12

• 24

• 15