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ă
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; } |
- 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