Clasa VI/VII/VIII lecția 12 - 20 nov 2012

From Algopedia
Jump to navigationJump to search

Clasa a șasea

Test

  • Problema romb de la vianuarena. Timp: 1h.

Exerciții recapitulative

Probleme din urmă:

  • xy (campion) ONI 2011, clasa 6: problemă de simulare. Necesită atenție la modul de desenare. Ultimul punct este cel mai greu, necesită o construcție auxiliară (Anastasia).
  • joc16 (campion) ONI 2011, clasa 6: problemă de simulare. De remarcat că dacă un copil calcă unde a mai călcat el nu poate fi decît punctul de plecare. E mai simplu să lucrați cu vectori de la zero, pentru indici.
  • tetris (campion) ONI 2009, clasa 6: problemă de simulare. Cum memorăm tabla de joc? Desigur că ne trebuie o matrice care memorează tabla cu piesele așezate. Dar pentru rapiditate în calcul avem nevoie pentru fiecare coloană să știm poziția celei mai de sus piese din coloană. Vom folosi un vector de înălțimi ale coloanelor.
  • trigrame (vianuarena): problemă de baze de numerație. Atenție la modul de transformare a unui caracter într-o cifră în baza 62, precum și a unei trigrame într-un număr în baza 62.
  • bile6 (campion) ONI 2012 clasa 7, folosind radix sort: putem sorta ușor obstacolele. Putem folosi o simplificare, pentru fiecare linie ținem o listă de coloane unde sînt obstacole.
  • problema zigzag (campion) ONI 2012 clasa 7, folosind radix sort: putem genera mai întîi perechile de (lin, col) ale caracterelor, așa cum se așează șirul de codificat în matrice. Apoi le sortăm după linie, și apoi după coloană (dar după coloană sînt sortate deja). După sortare putem asocia în ordine caracterele din textul codificat. Apoi resortăm după coloană și luăm caracterele în noua ordine.

Temă clasa a șasea

  • control1 la campion (ONI 2010, clasa a 6-a) rezolvare aici [1]
  • talent la campion (ONI 2011 clasa a 6-a) rezolvare aici [2]
  • Opțional: macheta la campion (ONI 2011 clasa 8)

Clasa a șaptea și a opta

Exerciții recapitulative

  • mesaj3 (campion) ONI 2011 clasa 7: problemă relativ ușoară. Partea interesantă este indirectarea: pentru fiecare caracter din cheie trebuie sa știm al cîtelea este el în șirul sortat. Putem face o sortare cu vector caracteristic de caractere A-Z: poz[car – 'A'] = poziția caracterului car în cuvîntul cheie:
    for ( i = 0; i < p; i++ )
      poz[cheie[i] – 'A'] = i + 1;

Apoi parcurgem vectorul poz și pentru fiecare element diferit de zero, vom completa în matrice coloana i – 1 cu următoarele caractere din șirul codificat. Trebuie să avem grijă la lungimea coloanei de completat care va fi n / p sau n / p + 1.

  • skyline (vianuarena): algoritmul.
  • problema bile6 (campion) ONI 2012 clasa 7, folosind radix sort: vezi explicația de la clasa a șasea.
  • problema zigzag (campion) ONI 2012 clasa 7, folosind radix sort: vezi explicația de la clasa a șasea.
  • tetris (campion) ONI 2009 clasa 6, pentru simulare: vezi explicația de la clasa a șasea.
  • macheta (campion) ONI 2011 clasa 8. Sînt mai mulți algoritmi posibili. Discuție despre algoritmul de grafică z-buffer. Dar depășește timpul. Cum adaptăm z-buffer pentru a folosi doar un vector în loc de o matrice, ceea ce duce la algoritmul O(N∙LxMax) (Alex). O altă variantă este să sortăm clădirile după x, și apoi după y și să luăm prima clădire și să decupăm din toate celelalte clădiri bucățile obstrucționate de ea. Eliminăm prima clădire și reluăm. Acest algoritm este O(n2∙log n) folosind quicksort, sau O(n3) cu select sort (Antonia). Avantajul acestui algoritm este că nu depinde de mărimea lui Lx. Cum putem face ca nici primul algoritm să nu mai depindă de Lx?
  • Urmează o discuție despre: puncte5, zeratul, taburet (baraj gimnaziu 2011)

Test

  • Problema numere de la vianuarena. Timp: 1h. Indicații de rezolvare aici [3]

Temă clasa a șaptea

  • Problema joc17 (campion), ONI 2011 clasa a 7-a, însă cu următoarea implementare:
    • Vom memora o listă cu 12 matrice 3x3, corespunzătoare celor 3 tipuri de piese și rotațiilor lor. Această listă de matrice o vom ține într-un vector preinițializat, rezultînd o matrice tridimensională. Folosind această matrice tridimensională parcurgem matricea cea mare căutînd la fiecare element una sau mai multe dintre matricele mici, 3x3.
    • matricea tridimensională va fi declarată astfel:
      char piese[12][3][3] = {
        { {1, 0, 0}, // piesa 1 pozitia 1
          {1, 0, 0},
          {1, 1, 1} },
        { {1, 1, 1}, // piesa 1 pozitia 2
          {1, 0, 0},
          {1, 0, 0} },
      ... completeaza cele 12 piese/pozitii...
      };
  • Opțional: problema drenaj (campion) rezolvare aici [4]

Temă clasa a opta

  • Problema drenaj (campion) rezolvare aici [5]
  • Prolema alee (campion), OJI 2007 clasa 10