BACTRACKING2

Utilizând metoda backtracking, se generează toate parfumurile formate prin amestecarea a câte 3 esențe distincte din mulţimea {ambră, cedru, iris, mosc, santal}. Primele patru soluţii obţinute sunt, în această ordine: (ambră, cedru, iris), (ambră, cedru, mosc), (ambră, cedru, santal) şi (ambră, iris, mosc).

Indicaţi submulţimea care trebuie eliminată din enumerarea următoare, astfel încât soluţiile rămase să apară în ordinea generării lor: (ambră, mosc, santal), (cedru, mosc, santal), (cedru, iris, mosc), (cedru, iris, santal).

• (ambră, mosc, santal)

  
  

• (cedru, mosc, santal)

  
  

• (cedru, iris, mosc)

  
  

• (cedru, iris, santal)

  
  

Utilizând metoda backtracking, se generează toate numerele naturale din intervalul
[100,999] care au suma cifrelor egală cu 5. Primele cinci soluţii obţinute sunt, în această ordine 104, 113, 122, 131, 140. Utilizând acelaşi algoritm, se generează toate numerele naturale din intervalul [1000,9999] care au suma cifrelor egală cu 6. Al treilea număr generat este:

• 1005

• 1023

• 1031

• 1041

Utilizând metoda backtracking, se generează toate șiragurile formate din câte 5 pietre distincte din mulţimea {opal, rubin, safir, smarald, topaz}. Două șiraguri sunt distincte dacă pietrele sunt dispuse în altă ordine. Primele patru soluţii obţinute sunt, în această ordine: (opal, rubin, safir, smarald, topaz), (opal, rubin, safir, topaz, smarald), (opal, rubin, smarald, safir, topaz) şi (opal, rubin, smarald, topaz, safir). Indicați soluția care trebuie eliminată din enumerarea următoare, astfel încât cele rămase să apară în ordinea generării lor, pe poziții consecutive:

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

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

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

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

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

  
  

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

  
  

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

  
  

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

  
  

Utilizând metoda backtracking, se generează toate posibilitățile de a obține suma 4 cu numere naturale nenule. Două sume sunt distincte dacă diferă prin cel puțin un termen. Soluţiile generate sunt, în această ordine, 1+1+1+1, 1+1+2, 1+3, 2+2.

Aplicând același algoritm pentru a genera toate posibilitățile de a obține suma 6, dacă prima soluție generată este 1+1+1+1+1+1, atunci soluția 1+2+3 este generată:

• a 6-a

• a 7-a

• a 8-a

• a 9-a

Utilizând metoda backtracking, se generează toate posibilitățile de a forma succesiuni de câte 5 genuri muzicale distincte din mulțimea {jazz, rock, latino, house, pop}, astfel încât în fiecare succesiune genul latino precede genul house. Două succesiuni sunt distincte dacă genurile muzicale sunt în altă ordine.
Primele cinci soluţii generate sunt, în această ordine:

• (jazz, rock, latino, house, pop)

• (jazz, rock, latino, pop, house)

• (jazz, rock, pop, latino, house)

• (jazz, latino, rock, house, pop)

• (jazz, latino, rock, pop, house)

Imediat înainte de (pop, latino, house, jazz, rock) este generată soluția:

• (rock, jazz, house, latino, pop)

• (rock, jazz, latino, house, pop)

• (pop, latino, rock, house, jazz)

• (pop, rock, latino, house, jazz)

Utilizând metoda backtracking se generează toate cuvintele de 5 litere din mulţimea {A, M}, cuvinte care încep şi se termină cu M. Primele patru soluţii generate sunt, în această ordine: MAAAM, MAAMM, MAMAM, MAMMM. Scrieţi cea de a cincea şi cea de a şasea soluţie, în ordinea generării acestora.

Scrieți cele două soluții în ordinea generării, separate prin exact un spațiu!!

Utilizând metoda backtracking, se generează în ordine lexicografică toate şirurile de câte 5 litere distincte din mulţimea {A, B, C, D, E}, astfel încât în fiecare şir litera D precede literele A şi B. Primele cinci soluţii generate sunt, în această ordine: CDABE, CDAEB, CDBAE, CDBEA, CDEAB. Scrieţi cea de a şasea şi cea de a şaptea soluţie, în ordinea generării acestora.

Algoritmul de generare a tuturor numerelor naturale de 5 cifre, fiecare număr având toate cifrele nenule şi distincte, este echivalent cu algoritmul de generare a:

• aranjamentelor de 9 elemente luate câte 5

• combinărilor de 9 elemente luate câte 5

• permutărilor a 5 elemente

• permutărilor a 5 elemente

Utilizând metoda backtracking se generează, în ordine lexicografică, toate şirurile de 5 cifre din mulţimea {0, 1, 2}, cu proprietatea că nu există două cifre pare pe poziţii consecutive.

Primele opt şiruri generate sunt, în această ordine: 01010, 01011, 01012, 01101, 01110, 01111, 01112, 01121. Al nouălea şir generat este:

• 01120

• 01201

• 01210

• 10101