Clasele 11-12 lecția 2 - 25 sep 2015

From Algopedia
Jump to navigationJump to search

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: