Probleme rezolvate metoda backtracking

Realizat de catre :  

• Ginghina Cristian
• Neculai Alexandru
• Anton Cosmin
• Onica Viorel

1.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru

litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Câte dintre cuvintele generate încep cu litera b şi se termină cu litera e?

babe,bace,bade – 3                                       3 X 5 = 15

bbbe,bbde,bbce – 3

bebe,bcce,bcde – 3                                       Raspuns : 15

bdbe,bdce,bdde - 3

bebe,bece,bede – 3

2.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru

litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este ultimul cuvânt generat?

Edda,eddb,eddc,eddd,edde,edeb,edec,eded Raspuns : eded – ultimul cuv. generat

                                

3.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru

litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este penultimul cuvânt generat?

Edda,eddb,eddc,eddd,edde,edeb,edec,eded Raspuns : edec

4.Utilizând metoda backtracking se generează în ordine lexicografică cuvintele de câte patru

litere din mulţimea A={a,b,c,d,e}, cuvinte care nu conţin două vocale alăturate. Primele

opt cuvinte generate sunt, în ordine: abab, abac, abad, abba, abbb, abbc, abbd, abbe.

Care este antepenultimul cuvânt generat?

Edda,eddb,eddc,eddd,edde,edeb,edec,eded                                   Raspuns: edeb

5.Folosind modelul combinărilor se generează numerele naturale cu câte trei cifre distincte din

mulţimea {1,2,3,7}, numere cu cifrele în ordine strict crescătoare, obţinându-se, în ordine:

123, 127, 137, 237. Dacă se utilizează exact aceeaşi metodă pentru a genera numerele

naturale cu patru cifre distincte din mulţimea {1,2,3,4,5,6,7,8}, câte dintre numerele

generate au prima cifră 2 şi ultima cifră 7?

2345, 2346, 2347, 2348, 2456, 2457, 2458, 2567, 2568, 2578 Raspuns: 3 numere

                      1                             2                 3

6.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ă?

103 , 105 , 107 , 109 , 123 , 125 ,127 ,129 , 143 , 145 Raspuns: 145

  1      2       3       4        5      6       7     8       9      10

7.Un algoritm de tip backtracking genereaza in ordine lexicografica toate sirurile de 5 cifre 0 si 1 cu proprietatea ca nu exista mai mult de doua cifre zero pe pozitii consecutive. Primele 7 solutii generate sunt : 00100, 00101, 00110, 00111, 01001, 01010, 01011. Care este a 8-a solutie generata de acest algoritm ?

Raspuns: 01110 a 8-a solutie

8.Folosind tehnica bactracking un elev a scris un program care generează toate numerele de

câte n cifre (0<n≤9), cifrele fiind în ordine strict crescătoare. Dacă n este egal cu 5, scrieți

în ordine crescătoare toate numerele având cifra unităților 6, care vor fi generate de

program.

Raspuns: 12346, 12356, 12456, 13456, 23456

9.Câte numere cu exact două cifre pot fi construite folosind doar cifre pare distincte?

20, 40, 60, 80, 24, 26, 28, 42, 46, 48, 62, 64, 68, 82, 84, 86

Raspuns: 16 numere

10.Un algoritm generează în ordine crescătoare toate numerele de n cifre, folosind doar cifrele

3, 5 şi 7. Dacă pentru n=5, primele 5 soluţii generate sunt 33333, 33335, 33337,

33353, 33355, precizaţi care sunt ultimele 3 soluţii generate, în ordinea generării.

Raspuns: 77773, 77775, 77777

11.Un algoritm generează în ordine descrescătoare toate numerele de 5 cifre, fiecare dintre ele

având cifrele în ordine strict crescătoare. Ştiind că primele 5 soluţii generate sunt 56789,

46789, 45789, 45689, 45679, precizaţi care sunt ultimele 3 soluţii generate, în ordinea

generării.

Raspuns: 12347, 12346, 12345

12.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 4 soluţii generate sunt 00000, 00001, 00010, 00011,

precizaţi care sunt ultimele 3 soluţii generate, în ordinea obţinerii lor.

00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111, 01000, 01001, 01010, 01011, 01100, 01101, 01110, 01111 -> 11101, 11110, 11111

Raspuns: 11101, 11110, 11111

13.Un algoritm generează în ordine crescătoare, toate numerele de n cifre (n<9), cu cifre

distincte, care nu au două cifre pare alăturate. Dacă pentru n=5, primele 5 soluţii generate

sunt 10325, 10327, 10329, 10345, 10347, precizaţi care sunt următoarele 3 soluţii

generate, în ordinea obţinerii lor.

10325, 10327, 10329, 10345, 10347,10349,10365,10367

Raspuns: 10349, 10365, 10367

14.Un algoritm generează în ordine descrescătoare, toate numerele de n cifre (n<9), cu cifrele

în ordine strict crescătoare, care nu au două cifre pare alăturate. Dacă pentru n=5, primele

5 soluţii generate sunt 56789, 45789, 45679, 45678, 36789, precizaţi care sunt

următoarele 3 soluţii generate, în ordinea obţinerii lor.

56789, 45789, 45679, 45678, 36789, 35679, 35678, 34789, 34679

Raspuns: 35679, 35678, 34789

15.Algoritmul de generare a tuturor numerelor de 5 cifre nenule, fiecare având cifrele ordonate

strict crescător, este echivalent cu algoritmul de generare a:

a. submulţimilor unei mulţimi cu 5 elemente

b. produsului cartezian a unor mulţimi de cifre

c. aranjamentelor de 9 elemente luate câte 5

d. combinărilor de 9 elemente luate câte 5 (RASPUNS)

16.Generând şirurile de maximum 3 caractere distincte din mulţimea {A,B,C,D,E}, ordonate

lexicografic, obţinem succesiv: A, AB, ABC, ABD,…. Ce şir va fi generat imediat după

BAE?

a. BCA

b. CAB

c. BC  (RASPUNS)

d. BEA

17.Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9,

se poate utilza un algoritm echivalent cu algoritmul de generare a: (4p.)

a. permutărilor de 5 elemente

b. submulţimilor mulţimii{1,2,3,4,5,6,7,8,9} (RASPUNS)

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

d. aranjamentelor de 9 elemente luatecâte 5

18.Utilizand metoda backtracking  se genereaza permutarile cuvantului INFO. Daca primele 3 solutii generate sunt : FINO, FION, FNIO care este cea dea 5a solutie ?

INFO – 1234

FINO – 3124 Raspuns: FNOI -> a 5-a solutie

FION – 3142

FNIO – 3214

FNOI – 3241

Realizat de catre :

• Enache Marian
• Balan Ana-Maria
• Dunac Cristiana 
• Lazar Maricel

1. Folosind un algoritm de generare putem obţine numere naturale de k cifre care au suma

cifrelor egală cu un număr natural s. Astfel, pentru valorile k=2 şi s=6 se generează, în

ordine, numerele: 15, 24, 33, 42, 51, 60. Care va fi al treilea număr generat pentru k=4 şi

s=5?

         a. 1301       b. 1022      c. 2201       d. 1031

  

       Raspuns: a)

2. Completarea unui bilet de LOTO presupune colorarea a 6 numere din cele 49 înscrise pe

bilet. O situaţie statistică pe o anumită perioadă de timp arată că cele mai frecvente numere

care au fost extrase la LOTO sunt: 2, 20, 18, 38, 36, 42, 46, 48. Câte bilete de 6

numere se pot completa folosind doar aceste valori ştiind că numărul 42 va fi colorat pe

fiecare bilet.

         a. 21       b. 6!      c. 42      d. 56

    Raspuns: a)

3. Pentru generarea tuturor mulţimilor de câte 5 cifre, având la dispoziţie cifrele de la 1 la 9,

se poate utilza un algoritm echivalent cu algoritmul de generare a:

         a. permutărilor de 5 elemente              

         b. submulţimilor mulţimii {1,2,3,4,5,6,7,8,9}

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

         d. aranjamentelor de 9 elemente luate câte 5

   

    Raspuns: c)

4. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca

sumă a cel puţin două numere naturale nenule distincte. Termenii descompunerii sunt în

ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8,

2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi metodă pentru scrierea lui 12. Scrieţi

în ordine toate soluţiile de forma 2+...?

     Raspuns: 2+3+7*2+4+6 ; 2+10

5. Se utilizează un algoritm pentru a genera în ordine lexicografică inversă toate permutările

mulţimii {1,2,3,4,5}. Primele patru permutări generate sunt: 54321, 54312, 54231,

54213. A cincea permutare este:

        a. 53421            b. 54321            c. 54132          d. 54123

     Raspuns: c)

6. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 9 ca

sumă a cel puţin două numere naturale nenule distincte. Termenii descompunerii sunt în

ordine strict crescătoare. Soluţiile se generează în ordinea: 1+2+6, 1+3+5, 1+8,

2+3+4, 2+7, 3+6 şi 4+5. Se aplică exact aceeaşi metodă pentru scrierea lui 8. Câte

soluţii vor fi generate?

         a. 3               b. 4              c. 6            d. 5

     Raspuns: d)

7. Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca

sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine

crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3,

1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea

lui 9. Care este penultima soluţie? (6p.)

          a. 3+3+3         b. 3+6        c. 4+5       d. 2+7

      Raspuns:b)

8.Utilizăm metoda backtracking pentru generarea tuturor modalităţilor de a scrie numărul 6 ca

sumă a cel puţin două numere naturale nenule. Termenii descompunerii sunt în ordine

crescătoare. Soluţiile se generează în ordinea: 1+1+1+1+1+1, 1+1+1+1+2, 1+1+1+3,

1+1+4, 1+5, 2+2+2, 2+4 şi 3+3. Se aplică exact aceeaşi metodă pentru scrierea

lui 9. Câte soluţii de forma 2+... vor fi generate?

            a. 2         b. 3         c. 4        d. 5

       Raspuns: c)

9. Utilizând metoda backtracking se generează numerele naturale formate din exact 3 cifre şi

care au suma cifrelor egală cu 4, în această ordine: 103, 112, 121, 130, 202,

211, 220, 301, 310, 400. Dacă utilizăm acelaşi algoritm pentru a genera toate

numerele de 4 cifre ce au suma cifrelor egala cu 7 precizaţi care este numarul generat

imediat dupa 1222.

           a. 1231            b. 1223         c. 1213         d. 1321

       Raspuns: a)

10. Utilizând metoda backtracking se generează toate permutările mulţimii {1,2,3,4}. Dacă

primele trei permutări generate sunt, în acestă ordine: 1234, 1243, 1324 precizaţi care

este permutarea generată imediat după 3412.

           a. 3421              b. 3413            c. 4123                 d. 3214

     Raspuns: a)

11. Utilizând metoda backtracking se generează numerele formate din câte 3 cifre distincte din

mulţimea {1,3,5,7}. Dacă primele trei numere generate sunt, în acestă ordine: 135,

137,153 care este cel de-al patrulea număr generat?

           a. 157        b. 173       c. 315      d. 357

     Raspuns: a)

12.Utilizând metoda backtracking se generează permutările cuvântului info. Dacă primele trei

soluţii generate sunt: fino, fion, fnio care este cea de-a cincea soluţie?

            a. Foin           b. Fnoi           c. Foni           d. Ifon

      Raspuns: a)

13.Utilizând metoda backtracking se generează toate cuvintele de câte 3 litere din mulţimea

{a,b,c}. Dacă primele patru cuvinte generate sunt, în acestă ordine: aaa, aab, aac,

aba, care este cel de-al optulea cuvânt generat?

         a. acb          b. acc          c. aca           d. bca

     Raspuns: a)

14. Un program generează, în ordine crescătoare, numerele naturale, de exact 5 cifre din

mulţimea {1, 2, 3, 4, 5}. Fiecare dintre numerele generate are cifrele distincte două câte

două. Primele 3 numere astfel generate sunt: 12345, 12354, 12435. Care este numărul

generat imediat după 12543?

           a. 15342              b. 12534            c. 13245             d. 13452

      Raspuns: c)

15. Într-un penar sunt unsprezece creioane, dintre care trei sunt roşii iar celelalte sunt negre.

Dacă scoatem din penar cinci creioane, câte posibilităţi există ca două dintre ele să fie roşii?

       Raspuns: 168

Realizat de catre:

• Apostolache Diana
• Onea Cristian
• Focsa Alexandru
• Popa Anton

ApostolacheDiana-Raluca:

Varianta 49 subiectul III

2.  Se generează în ordine strict crescătoare numerele de câte şase cifre care conţin: cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine, numerele:

122333, 123233, 123323, …, 333221. Câte numere generate prin această metodă au

prima cifră 1 şi ultima cifră 2?

Raspuns: 122333, 123233, 123323, 123332, 132332,132323, 132233, 133223, 133232, 133322=> 4 numere

Varianta 50 subiectul III

2.  Se generează în ordine strict crescătoare toate numerele de câte şase cifre care conţin:

cifra 1 o singură dată, cifra 2 de două ori şi cifra 3 de trei ori. Se obţin, în această ordine,

numerele: 122333, 123233, 123323, …, 333221. Ce număr se generează imediat după

332312?

Raspuns: 332321

Varianta 51 subiectul III

2.  Se consideră un număr natural nenul x având exact 8 cifre, cifrele lui fiind distincte 2 câte 2, iar printre cifrele sale se găseşte şi cifra 0. Permutând cifrele lui x se obţin alte numere

naturale. Câte dintre numerele obţinute, inclusiv x, au exact 8 cifre?

Raspuns: Numarul de permutari pentru un numar de 8 cifre este 8!.Dian acestea se scad cele cu cifra 0 pe prima pozitie,adica7!. 8!-7!=35280.

Varianta 52 subiectul III

1.  Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele

cuvântului caiet ( cuvinte formate din aceleaşi litere, eventual în altă ordine). Câte cuvinte

vor fi generate?

Rezolvare: Permutari de n litere.Cuvantul are 5 litere.P5=5!=1*2*3*4*5=120.

Onea Cristian:

Varianta 54 subiectul III

1. Utilizând metoda backtracking se generează în ordine lexicografică toate anagramele

cuvântului caiet ( cuvinte formate din aceleaşi litere, eventul în altă ordine). Care este a

şasea soluţie? (4p.)

a. catei

b. actie

c. actei

d. catie

Rezolvare: caiet, caite,caeti,caeit,catei,catie

Varinata 55 Subiectul III

Utilizând metoda backtracking se generează toate matricele pătratice de ordinul 4 ale căror

elemente aparţin mulţimii {0,1} cu proprietatea că pe fiecare linie şi pe fiecare coloană

există o singură valoare 1. Primele 3 soluţii generate sunt, în această ordine:

1 0 0 0     1 0 0 0      1 0 0 0

0 1 0 0     0 1 0 0      0 0 1 0

0 0 1 0     0 0 1 0      0 1 0 0

0 0 0 1     0 0 0 1      0 0 0 1

Care este penultima soluţie? (4p.)

a. 0 0 0 1

   0 0 1 0

   1 0 0 0

   0 1 0 0

b. 0 1 0 0

   1 0 0 0

   0 0 1 0

   0 0 0 1

c. 0 0 0 1

   0 1 0 0

   0 0 1 0

   1 0 0 0

d. 0 0 1 0

   1 0 0 0

   0 1 0 0

   0 0 0 1

Raspuns:a

Varianta 56:

1. Pentru a genera toate numerele naturale cu exact 4 cifre şi care au cifrele în ordine strict

descrescătoare, se poate utiliza un algoritm echivalent cu cel pentru generarea: (4p.)

a. aranjamentelor de 4 obiecte luate câte 10

b. combinărilor de 10 obiecte luate câte 4

c. permutărilor a 10 obiecte

d. permutărilor a 4 obiecte

Varianta57:

1. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte patru litere distincte din mulţimea {d,a,n,s}. Ştiind că al doilea cuvânt generat este dans, iar al treilea este dsan, care va fi ultimul cuvânt obţinut? (4p.)

a. nsad          b. snad              c. snda             d. dans

Raspuns: dasn, dans, dsan, dnsa, dnas,…., nsad

Focsa Alexandru

Varinata:58

1. Se utilizează metoda backtracking pentru a genera toate cuvintele de câte trei litere distincte din mulţimea {i,n,f,o}. Ştiind că ultimele trei cuvinte generate sunt, în ordine, ion, inf şi ino, care este cel de-al doilea cuvânt obţinut? (4p.)

a. ofn         b. ifo          c. foi        d. nif

Raspuns:

Varianta 59:

1. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o dat într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf, care este ultimul cuvânt obţinut? (4p.)

a. nifo        b. ofni       c. ofin      d. foni

Varinata:60:

1. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o dat într-un cuvânt şi literele n şi o să nu se afle pe poziţii vecine. Ştiind că primul cuvânt generat este info, iar al treilea este nifo care este cel de-al doilea cuvânt obţinut? (4p.)

a. iofn b. inof c. ionf d. niof

Varianta:61

1. Generarea matricelor pătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pe

fiecare linie şi pe fiecare coloană există un singur element egal cu 1, se poate realiza

utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare

a: (4p.)

a. combinărilor

b. permutărilor

c. aranjamentelor

d. produsului cartezian

Cristian Badea

1. Se utilizează metoda backtracking pentru a genera toate cuvintele care conţin toate literele din mulţimea {i,n,f,o}, astfel încât fiecare literă să apară exact o dat într-un cuvânt. Ştiind că al doilea cuvânt generat este info iar al treilea este ionf, care este ultimul cuvânt obţinut? (4p.)

a. nifo    b. ofni     c. ofin    d. foni

Daca al 2-lea cuvant generat din multimea {info} este info si al treilea cuvant generat este ionf=> ca primul cuvant generat este inof iar al 4-lea este iofn. De la primul cuvant observam ca ultimele 4 cuvinte generate vor incepe cu f ,prin eliminare ,ultimul cuvant va fi foni.

2.  Generarea matricelor pătratice de ordinul n, cu elemente 0 şi 1, cu proprietatea că pe fiecare

linie şi pe fiecare coloană există un singur element egal cu 1, se poate realiza utilizând metoda backtracking. Algoritmul utilizat este echivalent cu algoritmul de generare a:(4p.)

a. combinărilor

b. permutărilor

c. aranjamentelor

d. produsului cartezian

Prin definitie, metoda backtracking poate fi asociata cu permutarile.

3.Se generează, prin metoda backtracking toate partiţiile mulţimii A={1,2,3} obţinându-se

următoarele soluţii: {1}{2}{3};{1}{2,3};{1,3}{2};{1,2}{3};{1,2,3}. Se observă că dintre acestea,

prima soluţie e alcătuită din exact trei submulţimi. Dacă se foloseşte aceeaşi metodă pentru a genera partiţiile mulţimii {1,2,3,4} stabiliţi câte dintre soluţiile generate vor fi alcătuite din exact

trei submulţimi. (4p.)

a. 3       b. 12       c. 6       d. 5

Generand fiecare solutie din submultimea A, vom obtine exact 6 solutii a cate 3 submultimi.

4. Se generează, prin metoda backtracking, toate modalităţile de aşezare a numerelor

naturale de la 1 la 5, astfel încât oricare 2 numere consecutive să nu se afle pe poziţii

alăturate. Dacă primele 2 soluţii sunt: (1,3,5,2,4) şi (1,4,2,5,3), care este prima

soluţie generată în care primul număr este 4? (4 p.)

a. (4, 1, 3, 2, 5)

b. (4,2,5,1, 3)

c. (4, 3, 5, 3, 1)

d. (4, 1, 3, 5, 2)

Dupa 4 trebuie sa fie neaparat 1 ,ramane A si D. La A ai pe pozitia 2 si 3 numere consecutive deci sare..inseamna ca a mai ramas D.