Test backtracking & Div et Imp

Utilizând metoda backtracking, se generează toate modalitățile de a pregăti o ținută, luând, într-o

anumită ordine, articolele din mulțimea {cămașă, cravată, pantaloni, pantofi, sacou, șosete},

având în vedere următoarele restricții: cămașa va fi luată înaintea cravatei, cravata înaintea sacoului și

atât șosetele, cât și pantalonii, înaintea pantofilor. Primele trei soluții generate sunt, în această ordine:

(cămașă, cravată, pantaloni, sacou, șosete, pantofi), (cămașă, cravată, pantaloni,

șosete, pantofi, sacou), (cămașă, cravată, pantaloni, șosete, sacou, pantofi). Indicați

cea de a șasea soluție generată.

• (cămașă, cravată, sacou, șosete, pantaloni, pantofi)

• (cămașă, cravată, șosete, pantaloni, sacou, pantofi)

• (cămașă, cravată, șosete, pantaloni, pantofi, sacou)

• (cămașă, cravată, șosete, sacou, pantaloni, pantofi)

Utilizând metoda backtracking, se generează toate numerele impare de cel mult trei cifre din mulţimea

{5, 6, 7, 8}. Primele 8 soluţii generate sunt, în această ordine: 5, 55, 555, 557, 565, 567, 57, 575.

Cea de a 12-a soluţie generată este:

• 65

• 67

• 587

• 655

Utilizând metoda backtracking se generează toate posibilitățile de a forma liste de câte 3 locuri izolate

distincte din lume, din mulțimea {Hanging, Meteora, Sumela, Taktsang, Taung Kalat}, astfel încât

pe oricare două poziții alăturate să nu se afle locuri din submulțimea {Hanging, Sumela,

Taung Kalat}. Două liste diferă prin cel puțin un loc sau prin ordinea acestora. Primele șase soluții

generate sunt, în această ordine: (Hanging, Meteora, Sumela), (Hanging, Meteora, Taktsang),

(Hanging, Meteora, Taung Kalat), (Hanging, Taktsang, Meteora), (Hanging, Taktsang,

Sumela), (Hanging, Taktsang, Taung Kalat). Indicați numărul de soluții generate care au pe prima

poziție Meteora.

• 4

• 6

• 8

• 10

Utilizând metoda backtracking se generează toate posibilitățile de a forma șiraguri din câte 4 pietre

prețioase din mulțimea {rubin,opal,safir,smarald,topaz}, astfel încât pe oricare două poziții

alăturate să nu se afle două pietre din submulțimea {rubin,safir,topaz}. Primele opt șiraguri

generate sunt, în această ordine, (rubin,opal,rubin,opal), (rubin,opal,rubin,smarald),

(rubin,opal,opal,rubin), (rubin,opal,opal,opal), (rubin,opal,opal,safir),

(rubin,opal,opal,smarald), (rubin,opal,opal,topaz), (rubin,opal,safir,opal).

Ultimul șirag generat este:

• (topaz,smarald,topaz,topaz)

• (topaz,smarald,topaz,opal)

• (topaz,smarald,topaz,smarald)

• (topaz,smarald,smarald,topaz)

Se consideră un număr natural nenul x având exact 8 cifre, distincte două câte două; printre cifrele sale se găseşte şi cifra 0. Permutând cifrele lui x se obţin alte numere naturale. Câte dintre numerele obţinute, inclusiv x, au exact 8 cifre?

Aplicând metoda backtracking pentru a genera toate permutările celor n elemente ale unei mulţimi, o soluţie se memorează sub forma unui tablou unidimensional x₁,x₂,…,x_n. Dacă sunt deja generate valori pentru componentele x₁,x₂,…,x_k-1, iar pentru componenta curentă, x_k (1<k<n), a fost găsită o valoare convenabilă, atunci se încearcă alegerea

• unei noi valori pentru componenta x_{k- 1}

• unei valori pentru componenta x_k+1

• unei noi valori pentru componenta x_k

• unei noi valori pentru componenta x₁

Se generează în ordine strict crescătoare numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele: 122333, 123233, 123323, …, 333221. Câte numere generate prin această metodă au prima cifră 1 şi ultima cifră 2?

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:

• x_{k nu apartine multimii} {x₁, x₂, …, x_k-1}

• x_k ≠ x_k-1

• x_{k apartine multimii} {x₁, x₂, …, x_n}

• x_k ≠ x_k-1 şi x_k ≠ x_k+1

Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9, se poate utiliza un algoritm echivalent cu algoritmul de generare a:

• permutărilor de 5 elemente

• submulţimilor mulţimii {1,2,3,4,5,6,7,8,9}

• combinărilor de 9 elemente luate câte

• aranjamentelor de 9 elemente luate câte 5

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:

• produsului cartezian

• combinărilor

• aranjamentelor

• permutărilor