Clasa a V-a lecția 29 - 17 mar 2015

From Algopedia
Jump to: navigation, search

Tema - rezolvări

Rezolvări aici [1]

Lecție

Exerciții cu vectori (continuare)

Vector mulțime

Se dă un vector v de n elemente. Să se transforme într-un vector mulțime. Cu alte cuvinte, să se elimine duplicatele din vector. Un vector mulțime este un vector în care orice element apare o singură dată.

Avem mai multe soluții posibile. O primă soluție se bazează pe vectori de frecvență. Putem construi un vector de apariții ale elementelor din v. Apoi vom colecta elementele din vectorul de apariții înapoi in v. Această soluție funcționează pentru valori relativ mici ale elementelor din v.

Dacă valorile din v sînt prea mari pentru a folosi un vector de frecvență, atunci putem să verificăm fiecare element din vector și să îl copiem în alt vector, w, numai dacă el nu apare deja în vectorul w. Iată această soluție:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului w
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in w
  j = 0;
  while ( j < m && w[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in vectorul w, il adaugam
    w[m] = v[i];
    m++;
  }
}

Observație importantă: vectorul w are întotdeauna lungime mai mică sau cel mult egală cu vectorul v.

De aceea putem să nu folosim un vector diferit w, ci să lucrăm chiar pe vectorul v! Codul este identic cu cel de mai sus, înlocuind w cu v:

// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului multime
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in multime
  j = 0;
  while ( j < m && v[j] != v[i] )
    j++;
  if ( j == m ) { // daca elementul v[i] nu exista in multime, il adaugam
    v[m] = v[i];
    m++;
  }
}
// in final vectorul v de lungime m contine multimea vectorului original

Căutare subvector în vector

Dați doi vectori, p (vectorul de căutat) și v (vectorul în care se caută) să se spună de cîte ori apare vectorul p în v. De exemplu dacă p = [1, 2, 1] și v = [1, 2, 1, 2, 1, 3, 1, 2, 1] atunci p apare de 3 ori in v.

Să observăm că aparițiile vectorului p în vectorul v pot fi suprapuse, ca în exemplul de mai sus. Un algoritm direct este să încercăm toate pozițiile de suprapunere ale vectorului p peste vectorul v și să testăm dacă toate elementele din p se potrivesc cu cele din v:

   1, 2, 1, 2, 1, 3, 1, 2, 1
0: 1, 2, 1
1:    1, 2, 1
2:       1, 2, 1
3:          1, 2, 1
4:             1, 2, 1
5:                1, 2, 1
6:                   1, 2, 1

Suprapunînd vectorul p peste v observăm că avem potriviri la pozițiile 0, 2 și 6. Iată programul pentru această metodă:

// avem vectorul v de n elemente si vectorul de cautat p, de m elemente
nr = 0;                                // numarul de aparitii este initial zero
for ( poz = 0; poz < n – m; poz++ ) {   // pentru fiecare pozitie posibila
  i = 0;
  while ( i < m && p[i] == v[poz + i] ) // ne oprim la prima inegalitate
    i++;
  if ( i == m )                         // daca toate elementele au fost egale
    nr++;                               // am mai gasit o aparitie a lui p in v
}
// acum nr contine numarul de aparitii ale lui p in v

Vom vedea în anii următori că există și algoritmi mai eficienți pentru rezolvarea acestei probleme.

Comparație vectori

Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.

Un vector v1 este lexicografic mai mic decît alt vector v2 dacă v1 și v2 sînt egale de la 0 la i-1, iar poziția i este fie în afara vectorului v1, fie v1[i] < v2[i]. Vom compara elementele vectorilor pe aceleași poziții cîtă vreme sînt egale, oprindu-ne la prima diferență, sau cînd unul din vectori se termină. Acolo vom decide care din vectori este mai mic.

Iată programul:

// avem vectorii v1 de n1 elemente si v2 de n2 elemente
i = 0;
while ( i < n1 && i < n2 && v1[i] == v2[i] ) // cita vreme avem egalitate
  i++;                                       // avansam i
// pentru ca v1 sa fie primul in ordine lexicografica trebuie ca
// fie i sa fi depasit ultimul element din v1, fie ca v1[i] < v2[i]
// pentru a doua conditie e nevoie ca v2 sa aiba ceva pe pozitia i
if ( i == n1 || (i < n2 && v1[i] < v2[i]) )
  m = 0;
else
  m = 1;

Rotire multiplă de vector *

Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].

O soluție ar putea fi să rotim vectorul cîte o poziție de k ori. Această soluție face multe deplasări, respectiv k∙n. Un algoritm mai bun este următorul:

  1. Răstoarnă vectorul v.
  2. Răstoarnă subvectorul v[0..n-k-1]
  3. Răstoarnă subvectorul v[n-k..n-1]

De ce funcționează acest algoritm?

Care este numărul de deplasări ale acestui algoritm? Demonstrați că este 3∙n.

Manipularea orelor și minutelor pe ceas

Deși orele și minutele sînt doar numere, anumite exerciții pot pune probleme.

Problemă: se dau doi timpi, t1 și t2, specificați ca ore și minute. Astfel, vom avea la intrare o1, m1 și o2, m2. Cîte ore și minute se află între acești doi timpi? Atenție! Dacă t2 este înaintea lui t1 se consideră că am trecut într-o nouă zi. Exemplu: dacă t1 este 10:35 și t2 este 18:20 atunci vom afișa 07:45. Dacă t1 este 22:25 și t2 este 20:05 vom afișa 21:40.

La prima vedere acest exercițiu pare încîlcit. Va trebui să comparăm cei doi timpi. Dacă t1 este înaintea lui t2 atunci va trebui să comparăm cîte ore avem între o1 și o2. Dar și aceasta va depinde de relația dintre m1 și m2. Dacă t1 este după t2 lucrurile se complică și mai mult: trebuie să aflăm cîte ore și minute avem pîna la finalul zilei, apoi să aflăm cîte ore și minute avem de la începutul zilei pînă la t2, iar în final trebuie să le adunăm. Multe cazuri particulare. Cum facem să simplificăm lucrurile?

Regulă: pentru a nu ne încurca întotdeauna vom face conversia orelor la cea mai mică unitate de măsură, fie ea minut sau secundă. În final vom face conversia inversă, de la minute, la ore și minute.

În cazul problemei noastre, vom converti t1 și t2 la minute. Algoritmul este următorul:

1. calculează t1 = o1 * 60 + m1
2. calculează t2 = o2 * 60 + m2
3. calculează d = t2 - t1
4. dacă d < 0 atunci
     4.1 calculează d = 24 * 60 - d
5. calculează o3 și t3 pe baza lui d, astfel:
     5.1 o3 = d / 60
     5.2 m3 = d % 60
6. afișează o3 și m3

Concluzie: în problemele în care avem nevoie să lucrăm cu ore, minute și secunde, este foarte important să transformăm timpul într-un singur număr exprimat în cea mai mică unitate de timp implicată. În exemplul de mai sus această unitate este minutul. Uneori s-ar putea să fie secunda. După transformare vom face calculele cerute de problemă. În final vom transforma înapoi în ore, minute, posibil secunde, dacă problema necesită acest lucru.

Discuţie temă

Scurtă discuţie despre rezolvarea problemei şiruri1.

Temă

Tema 29 clasa a 5a

  • şiruri1 dată la OJI 2004, clasa a 7a
  • case1 dată la ONI 2009 clasa a 5a

Rezolvări aici [2]