Clasele 11-12 lecția 2 - 25 sep 2015
Prima oră
Operații logice
Operatorii logici discutați au fost:
- && și / and / conjuncție
- || sau / or / disjuncție
- ! not / negație
Acești operatori iau ca parametri orice tip de date. Prin convenție se consideră că parametrii lor iau valorile: - Adevărat - pentru 0 sau NULL; - Fals - pentru orice este diferit de 0.
Operatorii funcționează după următoarele reguli:
x&&y | x==0 | x!=0 |
y==0 | 0 | 0 |
y!=0 | 0 | 1 |
x||y | x==0 | x!=0 |
y==0 | 0 | 1 |
y!=0 | 1 | 1 |
x==0 | x!=0 | |
!x | 1 | 0 |
Operații pe biți
Operatorii pe biți discutați au fost:
- & și pe biți / bitwise and
- | sau pe biți / bitwise or
- ^ sau exclusiv pe biți / bitwise xor
- ~ complementarul / bitwise not
Operatorul ^ funcționează după următoarele reguli:
x^y | x==0 | x==1 |
y==0 | 0 | 1 |
y==1 | 1 | 0 |
Operatorii pe biți se aplică pe (perechi de) secvențe de biți (de lungimi egale) și calculează o secvență de biți produsă prin aplicarea repetată a operației logice corespunzătoare pe fiecare poziție a secvenței.
Radixsort
Radixsort este un algoritm de sortare care se aplică cel mai bine pe o mulțime de șiruri de caractere de aceeași lungime.
O problemă pe care puteți testa o implementare a algoritmului este [[1]].
Idea principală a algoritmului este să analizăm, pe etape, caracterele de pe o anumită poziție din toate cuvintele. Pe baza acestei idei, există două versiuni total diferite ale algoritmului, în funcție de ordine în care parcurgem caracterele.
LSD (Least Significant Digit)
Acest algoritm parcurge caracterele șirului de la ultimul la primul (de la caracterul care influențează cel mai puțin ordinea finală a cuvintelor către cel care o influențează cel mai semnificativ).
Algoritmul are L (= lungimea cuvintelor) pași. În primul pas se efectuează asupra șirului de intrare o sortare stabilă ținând cont de cea mai puțin semnificativă cifră. În pasul i se efectuează asupra șirului rezultat la pasul i-1 o sortare stabilă ținând cont de a i-a cea mai puțin semnificativă cifră.
Se poate demonstra prin inducție că după al i-lea pas șirurile sunt sortate după ultimele i cifre.
MSD (Most Significant Digit)
Acest algoritm parcurge caracterele șirului de la primul la ultimul (de la caracterul care influențează cel mai mult ordinea finală a cuvintelor către cel care o influențează cel mai puțin semnificativ).
Algoritmul este unul recursiv. În primul pas, toate cuvintele sunt sortate ținând cont de primul caracter. Pe baza acestuia se formează mai multe grupe compacte de cuvinte care au același prefix de lungime 1. În pasul următor fiecare din aceste grupe se sortează recursiv după următorul caracter. Acest proces se repetă recursiv fie până la ultimul caracter fie până când se ajunge la o grupă cu un singur element.
A doua oră
Codificarea și memorarea submulțimilor
Putem codifica și memora o submulțime a unei mulțimi cu un număr finit (și mic) de elemente folosindu-ne de biții unui întreg. Presupunem că mulțimea are 64 de elemente (numerele întregi de la 0 la 63). Atunci putem asocia bitul i al unui ungined long long elementului cu valoarea i. Dacă elementul i face parte din submulțime, vom seta bitul i pe 1. Dacă elementul i nu face parte din submulțime, vom seta bitul i pe 0.
Exemple de codificare:
întreg10 | întreg2 | submulțime |
0 | 000 | {} |
1 | 001 | {0} |
2 | 010 | {1} |
3 | 011 | {1, 0} |
4 | 100 | {2} |
5 | 101 | {2, 0} |
6 | 110 | {2, 1} |
7 | 111 | {2, 1, 0} |
La tablă am prezentat un algoritm de generare (și afișare) a tuturor submulțimilor mulțimii numerelor de la 0 la N-1:
void genereaza(int N) {
int lim = 1 << N;
for (i = 0; i < lim; ++i) {
for (j = 0; j < N; ++j) {
if (i & (1 << j)) {
printf("%d ", j);
}
}
printf("\n");
}
}
Aplicație
Am discutat apoi o problemă (Sobo (Infoarena)) de programare dinamică care calculează costuri optime pentru fiecare submulțime.
Apoi am schițat o rezolvare a acesteia. (Atenție: sursa de mai jos nu a fost testată)
#include <cstdio>
#include <algorithm>
using namespace std;
int N, L;
int M[15][1000];
int sobolaniCu1[1000];
int Cost[1000];
int Solve[1 << 15];
int answer;
// 1 <= sobolani <= 2^N
int solve(int sobolani) {
if (Solve[sobolani] == 0) {
if (sobolani & (sobolani - 1) == 0) { // se testeaza
// daca a ramas un singur sobolan in submultime
Solve[sobolani] = 0;
} else {
int i;
Solve[sobolani] = 0;
for (i = 0; i < L; ++i) {
int cu0 = sobolani & (~sobolaniCu1[i]);
int cu1 = sobolani & sobolaniCu1[i];
if (cu0 > 0 && cu1 > 0) {
int answerI = Cost[i] +
max(solve(cu0), solve(cu1));
Solve[sobolani] = min(Solve[sobolani], answerI);
}
}
}
}
return Solve[sobolani];
}
// Functia recursiva foloseste:
// Timp: O(L^N) Spatiu pt. functie: O(N) (fara memoizare)
// Timp: O(2^N*L) Spatiu pt. functie: O(2^N) (cu memoizare)
int main(void) {
int i, j;
// citirea datelor
// ...
// calcularea solutiei
for (i = 0; i < N; ++i) {
for (j = 0; j < L; ++j) {
sobolaniCu1[j] |= (1 << i) || M[i][j];
// if (M[i][j]) {
// sobolaniCu1[j] |= 1 << i;
// }
}
}
answer = solve((1 << N) - 1);
// afisarea solutiei
printf("%d\n", answer);
return 0;
}
Temă
Pentru data viitoare veți avea de rezolvat următoarele probleme: