Font size
WorksheetsMetoda Backtracking
Total questions: 5
Worksheet time: 11mins
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:
(a)
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:
(a)
