test backtracking - exercitii

Alfabetul Morse este format doar din simbolurile linie (notat cu -) şi punct (notat cu •). Utilizând metoda bactracking se generează toate cuvintele scrise în alfabetul Morse, formate din câte 5 simboluri, care încep şi se termină cu punct. Primele patru soluţii generate sunt, în această ordine (vezi imaginea).

Scrieți a cincea și a șaptea soluție despărțite de exact un spațiu. (veți folosi doar caracterele minus și punct)

Utilizând metoda backtracking se generează, în ordine crescătoare, toate numerele de patru cifre din mulțimea {1, 4, 6, 8, 9}, cu proprietatea că nu au două cifre alăturate egale. Primele patru numere generate sunt, în această ordine: 1414, 1416, 1418, 1419. Scrieți următoarele 3 numere generate

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 7, dacă prima soluție generată este 1+1+1+1+1+1+1, atunci soluția 1+1+2+3 este generată:

• a 5-a
• a 6-a
• a 7-a
• a 8-a

Utilizând metoda backtracking, se generează toate posibilitățile de a forma succesiuni decâ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 suntdistincte 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)
• (pop, latino, rock, house, jazz)
• (rock, jazz, latino, house, pop)
• (pop, rock, latino, house, jazz)

Se utilizează metoda backtracking pentru a genera toate cuvintele formate din două litere distincte din muţimea {w,x,z,y} astfel încât nici un cuvânt să nu înceapă cu litera x şi nici un cuvânt să nu conţină litera w lângă litera z. Cuvintele vor fi generate în ordinea wx, wy, zx, zy, yw, yx, yz. Folosind aceeaşi metodă se generează toate cuvintele de trei litere distincte din mulţimea {w,x,z,y,t} astfel încât niciun cuvânt să nu înceapă cu litera x şi niciun cuvânt să nu conţină litera w lângă litera z. Care sunt a treia şi a patra soluţie generată?

Utilizând metoda backtracking se generează toate submuţimile nevide ale mulţimii {3,6,2,5}. Primele şase submulţimi generate sunt, în ordine: {3}, {3,6}, {3,6,2},{3,6,2,5}, {3,6,5}, {3,2}. Care sunt, în ordinea obţinerii, ultimele trei submulţimi, generate după această regulă?

Utilizând metoda backtracking se generează toate modalitățile de a prepara o băutură din câte 3 sau 4 tipuride fructe distincte din mulțimea {căpșune, mere, pepene, pere, portocale}. Primele patru soluții generatesunt, în această ordine: (căpșune, mere, pepene), (căpșune, mere, pepene, pere), (căpșune, mere,pepene, portocale), (căpșune, mere, pere). Indicați cea de a șasea soluție generată.

• (pepene, pere, portocale)
• (mere, pepene, pere, portocale)
• (căpșune, mere, pere, pepene)
• (căpșune, mere, portocale)

Se generează, utilizând metoda backtracking, cuvintele cu exact 3 litere din mulţimea {a,x,c,f,g}. Dacă primele șase cuvinte generate sunt, în ordine, aaa, aax, aac, aaf, aag, axa câte soluții care încep cu litera g vor fi generate?

• 64
• 81
• 12
• 125

Pentru generarea în ordine crescătoare a numerelor cu n cifre formate cu elementele mulţimii {0,2,5} se utilizează un algoritm backtracking care, pentru n=2, generează, înordine, numerele 20, 22, 25, 50, 52, 55. Dacă n=4 şi se utilizează acelaşi algoritm, precizaţi câte numere generate sunt divizibilecu 25?

• 10
• 15
• 18
• 24

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 componentacurentă, x[k] (1

• unei noi valori pentru componenta x[k-1]
• unei noi valori pentru componenta x[k]
• unei valori pentru componenta x[k+1]
• unei noi valori pentru componenta x[1]