backtracking4

Ionel doreşte să ofere cadouri membrilor familiei sale, formată din cei doi părinţi şi o soră. Decide să le ofere stilouri de diferite culori. La magazin există stilouri de 5 culori diferite. Algoritmul de generare a tuturor posibilităţilor de a atribui câte un stilou fiecăruia dintre cei trei membri ai familiei, fără să se repete vreo culoare, este similar cu algoritmul de generare a

• elementelor produsului cartezian

  
  

• aranjamentelor

  
  

• permutărilor

  
  

• submulţimilor

O clasă formată din 28 de elevi doreşte să trimită la consfătuirea reprezentanţilor claselor şcolii o delegaţie formată din 3 elevi. Algoritmul de generare a tuturor posibilităţilor de a forma o delegaţie este similar cu algoritmul de generare a:

• combinărilor

  
  

• aranjamentelor

  
  

• permutărilor

• submulţimilor

  
  

Pentru a planifica în orarul unei şcoli, la clasa a XI-a, 4 ore de informatică în zile lucrătoare diferite din săptămână, câte o singură oră pe zi, se poate utiliza un algoritm echivalent cu algoritmul de generare a:

• permutărilor de 4 elemente

• aranjamentelor de 4 elemente luate câte 5

  
  

• aranjamentelor de 5 elemente luate câte 4

  
  

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

  
  

La un bal mascat, magazia şcolii pune la dispoziţia elevilor 10 pelerine, 10 măşti şi 10 pălării divers colorate. Algoritmul de generare a tuturor posibilităţilor de a obţine un costum format dintr-o pălărie, o mască şi o pelerină este similar cu algoritmul de generare a:

• elementelor produsului cartezian

  
  

• aranjamentelor

  
  

• permutărilor

  
  

• submulţimilor

  
  

Având la dispoziţie cifrele 0, 1 şi 2 se pot genera, în ordine crescătoare, numere care au suma cifrelor egală cu 2. Astfel, primele 6 soluţii sunt 2, 11, 20, 101, 110, 200. Folosind acelaşi algoritm, se generează numere cu cifrele 0, 1, 2 şi 3 care au suma cifrelor egală cu 4. Care va fi al 7-lea număr din această generare?

• 130

• 301

• 220

• 103

Un elev realizează un program care citeşte o valoare naturală pentru o variabilă n şi apoi afişează în fişierul permut.txt, pe prima linie, valoarea lui n, apoi toate permutările mulţimii {1,2,...,n}, câte o permutare pe câte o linie a fişierului. Rulând programul pentru n=3 fişierul va conţine cele 7 linii de mai jos. 3 3 2 1 3 1 2 2 3 1 2 1 3 1 3 2 1 2 3. Dacă va rula din nou programul pentru n=4, ce va conţine a 8-a linie din fişier?

• 2 1 3 4

  
  

• 2 1 4 3

  
  

• 3 4 2 1

  
  

• 3 4 1 2

  
  

Un program citeşte o valoare naturală nenulă pentru n şi apoi generează şi afişează, în ordine crescătoare lexicografic, toate combinaţiile formate din n cifre care aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt afişate în următoarea ordine: 00, 01, 10, 11. Dacă se rulează acest program şi se citeşte pentru n valoarea 9, imediat după combinaţia 011011011 va fi afişată combinaţia

• 011100100

  
  

• 011011100

  
  

• 011011011

• 011100000

Un program citeşte o valoare naturală nenulă pentru n şi apoi generează şi afişează, în ordine descrescătoare lexicografic, toate combinaţiile de n cifre care aparţin mulţimii {0,1}. Astfel, pentru n=2, combinaţiile sunt afişate în următoarea ordine: 11, 10, 01, 00. Dacă se rulează acest program şi se citeşte pentru n valoarea 8, imediat după combinaţia 10101000 va fi afişată combinaţia:

• 01010111

• 10100111

  
  

• 10100100

  
  

• 10101001

  
  

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[1], x[2], …, x[n]. Dacă sunt deja generate valori pentru componentele x[1], x[2], …, 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[1]