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

From Algopedia
Jump to navigationJump to search

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 2n – 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