Clasa VI/VII/VIII lecția 7 - 16 oct 2012
From Algopedia
Anunț
Făceți-vă cont pe varena.ro. Vom începe să lucrăm unele probleme de acolo, începînd chiar de azi. Contul nu este comun cu cel de pe infoarena. Sînt servere diferite, conturi diferite. Puteți să vă puneți același user sau parola, pentru ușurință.
Lecție
Clasa a șasea
Matrice, continuare
- Problemă în clasă: parcurgere pe diagonale: se citește o matrice pătrată de caractere. Să se afișeze două linii de caractere, fiecare linie conținînd toate caracterele matricei. Prima linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala principală. A doua linie afișată conține caracterele matricei în parcurgerea pe diagonale paralele cu diagonala secundară. Diagonala principală este din coțul stînga sus în colțul dreapta jos. Diagonala secundară este din colțul dreapta sus, în colțul dreapta jos. Atenție! Fișierul de intrare conține numai matricea de caractere, fiecare linie terminîndu-se cu '\n'. Nu se dă n, dimensiunea matricei, trebuie sa o deduceți. Exemplu:
 |
 |
- Problemă în clasă: zoom x2: se citește o matrice pătrată de caractere. Să se construiască o altă matrice în care fiecare caracter apare de două ori pe orizontală și de două ori pe verticală (zoom ori 2). Exemplu:
|
 |
- Am vorbit despre problema joc17, care are o implementare ușoară cu condiția să țineți toate matricele de căutat, inclusiv rotațiile lor, într-un vector de 12 matrice cu elemente zero și unu. Astfel, va trebui să declarați un tablou tridimensional inițializat. Necesită atenție la declararea acestui tablou, dar programul se simplifică.
Temă clasa a șasea
- problemele rămase din urmă, cu matrice: joc14, cifru, robinson
- joc17 (oni 2011 clasa 7), cu rezolvarea simplă folosind tablouri tridimensionale.
- Opțional: tetris, bile6 (ONI 2012 clasa 7), trigrame la varena.ro (rezolvare trigrame aici [1]).
Clasa a șaptea și a opta
Recursivitate, continuare
- Din urmă: rezolvări la problemele de recursivitate:
- Există două moduri de implementare a unei soluții recursive:
- Recursie Top-Down: cînd pornim cu o problemă mai mare și apelăm funcția pentru probleme mai mici pe care le folosim ulterior în apelul curent. În subproblema de bază returnăm un rezultat de bază, cum ar fi zero sau unu. În această categorie sînt toate exemplele de mai sus cu excepția combinărilor și permutărilor.
- Recursie Bottom-Up: cînd pornim cu o problemă mai mare și cu un acumulator de soluție, care inițial este vid (zero sau unu), iar în apelurile ulterioare reducem mărimea problemei adăugînd (construind) soluția finală în acumulator. Exemplele de combinări și permutări sînt Bottom-Up în care acumulatorul este vectorul și nu este transmis în mod explicit, deși am putea face acest lucru.
- Exemple de recursie Bottom-Up cu acumulator:
- factorial
#include <stdio.h> int fact( int n, int ac ) { if ( n == 1 ) // cind n = 1 am terminat calculul in ac return ac; return fact( n - 1, n * ac ); // adaugam n la acumulator } int main() { int n; scanf( "%d", &n ); printf( "%d! = %d\n", n, fact( n, 1 ) ); return 0; } - an în O(n)
#include <stdio.h> int putere( int a, int n, int ac ) { if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul return ac; return putere( a, n - 1, a * ac ); // acumuleaza a la rezultat } int main() { int n, a; scanf( "%d%d", &a, &n ); printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) ); return 0; } - verificare palindrom
#include <stdio.h> int palindrom( int n, int nc, int ac ) { if ( n == 0 ) // cind n=0 ac este inversul lui nc return nc == ac; // daca sint egale, returnam 1, altfel 0 return palindrom( n / 10, nc, ac * 10 + n % 10 ); // taiem o cifra tin n } // si o adaugam la ac int main() { int n; scanf( "%d", &n ); if ( palindrom( n, n, 0 ) ) printf( "%d este palindrom\n", n ); else printf( "%d nu este palindrom\n", n ); return 0; } - an în O(log n)
#include <stdio.h> // in permanenta a^n * ac detine rezultatul // cind n devine zero a^n * ac = ac int putere( int a, int n, int ac ) { if ( n == 0 ) // cind puterea e zero acumulatorul are rezultatul return ac; if ( n % 2 ) // cind n impar return putere( a, n - 1, a * ac ); // acumuleaza a la rezultat return putere( a * a, n / 2, ac ); // totuna cu (a*a)^(n/2) } int main() { int n, a; scanf( "%d%d", &a, &n ); printf( "%d^%d = %d\n", a, n, putere( a, n, 1 ) ); return 0; }
- factorial
- Orice funcție recursivă de tip Top-Down care pe orice cale de execuție are un singur apel recursiv se poate transforma într-o funcție de tip Bottom-Up prin adăugarea unui parametru acumulator.
- Temă de gîndire în clasă: turnurile din hanoi. Fie trei tije și n discuri perforate de diametre diferite. Discurile sînt așezate inițial pe tija 1 în ordinea descrescătoare a diametrelor aceostora, considerînd sensul de la bază la vîrf. Problema constă în a muta turnul de n discuri de pe tija 1 pe tija 2 ținînd cont de următoarele reguli:
- La fiecare mutare se mută un singur disc, care se află în vîrful unui turn
- În permanență, pe fiecare tijă, deasupra unui disc pot fi mutate numai discuri de diametre mai mici.
Analiza amortizată
Despre analiza amortizată. Citat din CLR: În analiza amortizată facem media timpului necesar pentru a executa o secvență operații împărțindu-l la toate operațiile executate. Prin analiza amortizată putem să arătăm că costul mediu al unei operații este mic, atunci cînd împărțim la numărul de operații, cu toate că o singură operație din secvență ar putea fi "scumpă". Exemple de calcul:
- Problema bibliotecarului, de data trecută (implementarea unei cozi folosind două stive).
- Incrementare contor binar.
Despre structura de date coadă
- Într-o coadă putem adăuga elemente și putem scoate elemente. Ele vor fi scoase în ordinea primul sosit primul plecat, sau FIFO (first in, first out)
- O posibilitate eficientă de implementare a unei cozi este cu un vector circular, în care după indicele n-1 urmează indicele 0, din nou. Vom memora doi indici in acest vector, p (primul), poziția primului element din coadă și u (ultimul), poziția imediat următoare ultimului element din coadă. Avansul indicilor se face modulo n:
p = (p + 1) % n
șiu = (u + 1) % n
.
Temă clasa a șaptea și a opta
- Turnurile din Hanoi: se citește n, numărul de discuri aflate inițial pe tija 1, afișați secvența de mutări prin care putem muta toate discurile pe discul 2. Implementați folosind o funcție recursivă. Rezolvare aici: [2]
- Coada: La o coadă se așează oameni cu numere agățate de gît, numere naturale mai mici sau egale cu un milion. Oamenii vin și pleacă, secvența de veniri și plecări fiind dată la intrare. Numărul maxim de veniri nu va depăși 100000. Se știe de asemenea că coada nu va depăși 1000 oameni. Să se spună care este suma maximă a numerelor aflate în coadă pe parcursul simulării noastre. La intrare se va citi pe prima linie m, numărul de veniri și plecări, iar pe următoarele m linii vom avea fie "v<nr>" cu semnificația "venire <nr> în coadă", fie "p", cu semnificația "plecare om din coadă". Exemplu:
| Intrare | Ieşire | Explicaţii |
|---|---|---|
| 10 v100 |
170 |
Coada va varia astfel: 100 |
