Pagina informaticii

Teste de informatică pentru liceu, articole C#, C/C++, PHP

Teză clasa a XI-a – Tehnici de programare

Rândul 1

1. Utilizând metoda backtracking, se aranjează şirurile de 8 paranteze rotunde care se închid corect. Primele 3 succesiuni corecte sunt:
( ( ( ( ) ) ) )    ( ( ( ) ( ) ) )    ( ( ( ) ) ( ) )
Care sunt ultimele 3 succesiuni corecte de paranteze rotunde

a

b

c

d

( ) ( ( ) ( ) )
( ) ( ) ( ( ) )
( ) ( ) ( ) ( )

( ) ( ) ( ( ) )
( ) ( ) ( ) ( )
( ) ( ( ) ) ( )

( ) ( ( ) ) ( )
( ) ( ) ( ( ) )
( ) ( ) ( ) ( )

( ) ( ) ( ( ) )
( ) ( ( ) ( ) )
( ) ( ( ) ) ( )

2. Considerând că v este un vector de n numere întregi şi avem o funcţie deja definită funcţia Cmmdc(x1, x2) care returnează cel mai mare divizor comun al numerelor întregi x1 şi x2, se construieşte funcţia:

int F(int a, int b)
{
            int k ;
            if (b – a <= 1) return Cmmdc(v[a], v[b]) ;
            else
            {
               k = (a + b) / 2 ;
               return F(Cmmdc(a, m), Cmmdc(m+1, b)) ;
}
}
Apelul funcţiei va fi: F(1, n). Precizaţi ce face funcţia şi care tehnică de programare se aplică în funcţie.

3. Se consideră un şir de n numere naturale mai mici decât 30000. Folosind metoda backtracking, să se genereze toate subşirurile strict crescătoare de k numere care se pot forma începând cu primul element din şir. Fiecare subşir se va afişa pe câte o linie din fişierul subsiruri.txt.
De exemplu, pentru n=5, k=3 şi numerele 3, 10, 5, 6, 4, 9 se va afişa:
3 5 6
3 5 9
3 6 9
3 4 9
5 6 9

4. Se consideră un şir de n valori 0 şi 1 şi o valoare k. Singura operaţie permisă este să se aleagă o secvenţă de k elemente şi inversarea valorilor lor (adică o devine 1 şi 1 devine 0). De exemplu, pentru şirul 0, 0, 1, 1, 1, 0, 1, 0 şi k=4, dacă aplicăm operaţia pentru poziţia 2, obţinem 0, 1, 0, 0, 0, 0, 1, 0. Să se determine, în caz că este posibil, o secvenţă de astfel de operaţii aplicate şirului astfel încât şirul să devină 0 peste tot. De exemplu, pentru şirul 0 1 0 0 0 1 0 0 şi k = 4:

Şir

Operaţie

rezultat

0 1 0 0 0 1 0 0

Poziţia 3

0 1 1 1 1 0 0 0

0 1 1 1 1 0 0 0

Poziţia 2

0 0 0 0 0 0 0 0


Rândul 2

1. Se generează, utilizând metoda backtracking, toate partiţiile mulţimii {1,2,3,4}. Ultimele trei partiţii generate sunt:
{1} {2, 4} {3}
{1} {2} {3, 4}
{1} {2} {3} {4}
Care este partiţia care le precede?
a. {1, 4} {2, 3}            b. {1} {2, 3} {4}         c. {1, 4} {2} {3}         d. {1} {2, 3, 4}

2. Considerând că v este un vector de n numere întregi, se contruieşte funcţia:
int F(int a, int b)
{
            int k, x, y ;
            if (a = = b) return v[a] ;
            k = (a + b) / 2 ;
            x = F(a, k) ;
            y = F(k+1, b) ;
return x > y ? x : y ;
}
Apelul funcţiei va fi: F(1, n). Precizaţi ce face funcţia şi care tehnică de programare se aplică în funcţie.

3. Într-o permutare p=(p1, p2, ..., pn) un punct fix este o valoare pi = i. Un ciclu de lungime 2 are proprietatea că dacă pi = k, atunci pk = i. Un exemplu de permutare care are doar puncte fixe şi cicli de lungime 2 este: {2, 1, 6, 4, 5, 3}. Utilizând metoda backtracking, să se genereze toate permutările mulţimii {1,2,…, n} cu proprietatea că are doar puncte fixe sau cicli de lungime 2. De exemplu, pentru n = 3, permutările sunt:
{1, 2, 3},  {1, 3, 2},  {2, 1, 3},  {3, 2, 1}

4. Se consideră un şir de n valori 0 şi 1 şi o valoare k. Singura operaţie permisă este să se aleagă o secvenţă de k elemente şi inversarea valorilor lor (adică o devine 1 şi 1 devine 0). De exemplu, pentru şirul 0, 0, 1, 1, 1, 0, 1, 0 şi k=4, dacă aplicăm operaţia pentru poziţia 2, obţinem 0, 1, 0, 0, 0, 0, 1, 0. Să se determine, în caz că este posibil, o secvenţă de astfel de operaţii aplicate şirului astfel încât şirul să devină 0 peste tot. De exemplu, pentru şirul 0 1 0 0 0 1 0 0 şi k = 4:

Şir

Operaţie

rezultat

0 1 0 0 0 1 0 0

Poziţia 3

0 1 1 1 1 0 0 0

0 1 1 1 1 0 0 0

Poziţia 2

0 0 0 0 0 0 0 0

 

Despre autor
Author

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

Comentarii (2)
  • Avatar

    danciu mihaela 12-10-2012 14:12:48

    am si eu o problema la informatica si nu stiu cum sa o rezolv ati putea sa ma ajutati?
    enuntul este :Fie multimea A={1,2,...,n} care se numeste partitie a multimii A,un set k<=n de multim care indeplinesc conditiile.a) A1 U A2 U...U Ak=A si b)Ai intersectat cu Aj=0 taiat,oricare i diferit de j apartine {1,2,...,n}.ASTEPT UN RASP CAT MAI REPEDE CU PUTINTA

  • Avatar

    Dan Pracsiu 12-10-2012 16:22:8

    Stiu ce este o partitie. Care este cerinta? Se cere generarea partitiilor?

    Am postat un articol la sectiunea C++ legat de backtracking in care am abordat si problema generarii partitiilor unei multimi:
    Articolul

Scrie un comentariu
Nume:

Comentariu:

15 + 10 =