Metoda Backtracking

Utilizând metoda backtracking se generează toate şirurile formate din cifrele binare 0 şi 1. Astfel, se generează în această ordine pentru n=3 şirurile: 111, 110,101, 100,011,010, 001,000. Pentru n=4 care vor fi cele două şiruri afişate imediat după şirul 1001?

• 0111 1000

• 1000 1100

• 0011 1000

• 1000 1101

Un algoritm generează, în ordine lexicografică, toate şirurile alcătuite din câte n cifre binare (0 şi 1). Ştiind că pentru n=5, primele patru soluţii generate sunt 00000, 00001, 00010, 00011, precizaţi care sunt ultimele trei soluţii generate, în ordinea obţinerii lor:

Utilizând metoda backtracking sunt generate numerele de 3 cifre, având toate cifrele distincte şi cu proprietatea că cifrele aflate pe poziţii consecutive sunt de paritate diferită. Ştiind că primele şase soluţii generate sunt, în această ordine, 103, 105, 107, 109, 123, 125, care este a zecea soluţie generată?

• 145

• 147

• 230

• 149

Folosind numai cifrele {0,1,2,3}, se construiesc, prin metoda Backtracking, toate numerele cu 3 cifre în care oricare două cifre alăturate nu au aceeaşi paritate. Se obţin în ordine numerele: 101, 103, 121,123,210,... Utilizând aceeaşi metodă pentru a obţine numere cu patru cifre din multimea {0,1,2,3,4} în care oricare două cifre alăturate nu au aceeaşi paritate care este al 4-lea număr generat?

• 1034

• 1030

• 1012

• 1232

Se consideră mulțimea de cuvinte {info, mate, fizica, chimie, biologie}. Se generează

folosind metoda backtracking, lexicografic, în ordinea inversă citirii cuvântului,

submultimi de câte trei cuvinte distincte. Dacă primele trei soluții sunt: {fizica,

biologie, chimie};{fizica, biologie, mate};{fizica, biologie, info}; înaintea soluției

{chimie, mate, info} este soluția: