Clasa VI/VII/VIII lecția 9 - 30 oct 2012

Clasa a șasea

Rezolvări teme din urmă

• număr5 (campion); rezolvare aici [1]
• figura (campion); rezolvare aici [2].

Baze de numerație

• Aplicație: să se afișeze toate submulțimile unei mulțimi de n elemente. Numărăm în baza 2 de la 0 la 2ⁿ – 1 și "decodăm" fiecare submulțime:

#include <stdio.h>

int main() {
  int n, i, j, p2, ic;
  scanf( "%d", &n );
  p2 = 1;
  for ( i = 0; i < n; i++ )
    p2 = p2 * 2;
  for ( i = 0; i < p2; i++ ) {
    printf( "{" );
    ic = i;
    for ( j = 0; j < n; j++ ) {
      if ( ic % 2 )
        printf( " %d", j + 1 );
      ic /= 2;
    }
    printf( " }\n" );
  }
  return 0;
}

• Conversie din baza zece în baza 16 și invers. Algoritmi, pe scurt:

#include <stdio.h> int cifre[10]; int main() { int n, i; scanf( "%d", &n ); i = 0; while ( n > 0 ) { cifre[i] = n % 16; n /= 16; i++; } // afisare for ( i--; i >= 0; i-- ) if ( cifre[i] < 10 ) fputc( '0' + cifre[i], stdout ); else fputc( 'A' + cifre[i] - 10, stdout ); return 0; }	#include <stdio.h> int cifre[10]; int main() { int n; char c; n = 0; c = fgetc( stdin ); while ( c != '\n' ) { c -= ( c <= '9' ) ? '0' : ('A' - 10); n = n * 16 + c; c = fgetc( stdin ); } printf( "%d\n", n ); return 0; }
Conversie din baza 10 în baza 16	Conversie din baza 16 în baza 10

• Generalizare din baza 10 în orice bază b intre 2 și 36 și invers.
  • Aplicație: problema trigrame la vianuarena; o trigramă poate fi privită ca un număr de 3 cifre în baza 62. Idee: fiecare caracter se convertește la o cifră între 0 și 61. Rămîne ca temă pentru acasă.

Temă clasa a șasea

• Probleme rămase din urmă: xy
• problema joc16 (campion) ONI 2011 clasa a 6-a
• trigrame la vianuarena (rezolvare trigrame aici [3])
• Opțional: tetris, bile6 (data viitoare le discutăm)

Clasa a șaptea și a opta

Recursivitate, încheiere

• Turnurile din hanoi iterativ. Este o problemă deosebită în sensul în care deși rezolvarea ei se potrivește foarte bine cu modelul recursiv, există și o rezolvare iterativă ușoară. Rezolvarea aici [4]
• Problema optim. Singurii care mi-au trimis-o sînt Ori și Alex. Am văzut că și Antonia a rezolvat-o, dar nu mi-a trimis sursa și nu a folosit recursivitate. Două motive care mă fac să mă întreb cine a rezolvat-o de fapt ☺. Rezolvare aici [5]

Indicații la probleme din urmă

• Trigrame: folosiți numere în baza 62 și vectori caracteristici (rezolvare trigrame aici [6])
• Maxim: folosiți algoritmul de maxim în fereastră glisantă.
• Data viitoare le discutăm.

Despre structura de date coadă

• Exercițiu cu coadă: fill cu frontieră versus fill recursiv (n-am discutat algoritmul recursiv). Exemplu în matrice de zero și unu. Poate fi folosit pentru a determina dacă există drum intre două puncte din matrice.

Temă clasa a șaptea

• Rămase de data trecută: maxim și trigrame la vianuarena (rezolvare trigrame aici [7])
• mesaj3 (ONI 2011 clasa 7)
• Opțional: macheta la campion (oni 2011 clasa 8)
• Opțional: skyline la vianuarena (analiză amortizată)

Temă clasa a opta

• Rămase de data trecută: maxim și trigrame la vianuarena (rezolvare trigrame aici [8])
• Macheta la campion (oni 2011 clasa 8) (pe viitor: taburet baraj 2011, canonizare, vedere în spațiu)
• skyline la vianuarena (analiză amortizată)
• Opțional: puncte5.
• Opțional: zeratul