Clasa a IX-a lecția 26 - 24 mai 2020

From Algopedia
Jump to navigationJump to search

Clasament teme lecțiile 1 - 25

Pe categorii

Divizori / Primalitate / Ciur
Sortări
Matrici
Căutare binară
Stivă
Recursivitate
Parcurgeri matrice
Divide et Impera
Programare dinamică
Backtracking
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Liste înlănțuite

Definiție

O listă înlănțuită este o structură de date care reprezintă o înlănțuire secvențială de noduri. Fiecare nod este format dintr-un element (care conține date, poate fi un număr natural, un caracter, etc.) și o referință către următorul nod din listă. Lista înlănțuită permite inserarea și ștergerea eficientă a elementelor de pe orice poziție.

Implementare

Sunt mai multe moduri de a implementa o listă. Să luăm ca exemplu o listă care este formată din elemente numere întregi. Vom citi elementele într-un vector V. Inițial, lista conține toate elementele, iar după fiecare element V[i] în listă, urmează elementul V[i + 1]. Deci, ne putem declara un vector auxiliar NEXT, unde NEXT[i] = j reprezintă că elementul V[j] este următorul dupa V[i] în listă. Evident, ultimul element din listă nu are un succesor, deci îi putem da o valoare terminală/invalidă (-1 de exemplu).

Crearea listei din citirea unui vector

scanf("%d", &n);
for (i = 0; i < n; ++i) {
  scanf("%d", &v[i]);
  next[i] = i + 1;
}
next[n - 1] = -1; // marcam ca este ultimul element din lista

Citim un vector și creăm o structură de tip listă care ține valorile din vectorul citit.

Afișarea listei

i = 0;
while (i != -1) {       // cat timp nu am ajuns la o pozitie terminala
  printf("%d ", v[i]);  // afisam elementul
  i = next[i];          // mutam cursorul la urmatorul element
}

Afișăm elementele din listă. Se observă că în vectorul next reținem pozițiile din vector care fac parte din listă, vectorul v conținând valorile efective.

Ștergere element din listă după poziție

Vrem să ștergem din listă elementul care se află după elementul de la poziția i.

if (next[i] != -1)         // daca avem ceva dupa elementul i
  next[i] = next[next[i]]; // luam ce avem in dreapta acelui element

Afișarea elementului de pe pozitia k

Spre deosebire de un vector, unde avem acces direct la poziția k prin V[k], într-o listă suntem nevoiți să parcurgem elementele.

i = 0;                  // Setam pozitia de start ca fiind primul element din lista
for (j = 1; j < k; ++j) // Avansam de k-1 ori
  i = next[i];
printf("%d", v[i]);

Atenție În codul de mai sus, nu am verificat dacă nu cumva lista noastră are mai puțin de k elemente. Puteam verifica acest lucru asigurându-ne că nu ajungem niciodată cu valoarea lui i pe nodul terminal, -1. Acest lucru este însă ineficient, pentru că adăugăm o operație în plus, o întrebare la fiecare pas din parcurgere. Este mai eficient să reținem numărul de elemente din listă și să ne asigurăm că îl actualizăm de fiecare dată când este cazul. Vom compara k cu acel număr o singură dată, fiind astfel eficienți.

Aplicație

Enunț

Sursă IQAcademy

n copii numerotați de la 1 la n și așezați în cerc numără la v-ați ascunselea, din k în k, începând cu copilul 1. Date n și k să se afișeze ordinea în care ies copiii din cerc.

Rezolvare

Problema are multe modalități de abordare. Folosind vectori simpli, putem să ne jucăm cu diverse parcurgeri/eliminări ale elementelor și vom ajunge în majoritatea cazurilor la o complexitate O(N2). Soluțiile sunt prezentate foarte fain aici. Voi prezenta soluția care folosește liste. Aceasta este, întâmplător și cea mai eficientă, având o complexitate egală cu O(N * K).

Ideea este simplă: la fiecare pas, luăm cel de-al k-lea element, îl ștergem din listă și repetăm procedeul.

#include <stdio.h>

int v[100], next[100];

int main() {
  int n, k, i, j, pos;

  scanf("%d%d", &n, &k);
  // initializam lista
  for (i = 0; i < n; ++i) {
    v[i] = i + 1;
    next[i] = (i + 1) % n; // copiii sunt asezati in cerc, copilul din dreapta ultimului este primul
  }

  pos = n - 1; // pos e pozitia copilului din-nainte de copilul de eliminat
  for (i = 0; i < n; ++i) {
    // avanseaza k - 1 elemente deoarece eliminarea conteaza ca un element
    for (j = 1; j < k; ++j)
      pos = next[pos];

    printf("%d ", v[next[pos]]);
    next[pos] = next[next[pos]];
  }
  printf("\n");

  return 0;
}

Union-find

Enunț

Avem N valori distincte de la 0 la N - 1, fiecare valoare făcând parte din "submulțimea ei". Se dau două tipuri de operații:

  • Unifică submulțimile valorilor i și j. (union)
  • Fac valorile i și j parte din aceeași submulțime? (find)

Rezolvare

Ideea #1

Vom reține un vector m[i] = indicatorul unic al mulțimii din care face parte valoarea i. Avem astfel:

Operația find
int find(int i) {
  return m[i];
}

Funcția find ne întoarce chiar indicatorul mulțimii. Avem complexitate O(1).

Operația union
void union(int i, int j) {
  int mj = m[j];              // retinem multimea din care face parte j
  for (int k = 0; k < N; ++k) // parcurgem toate valorile
    if (m[k] == mj)           // daca dam de un element care face parte din multimea lui j
      m[k] = m[i];            // il setam sa faca parte din multimea lui i
}

Avem complexitate O(N).

Ideea #2 - Optimizare union

Vom reține pentru fiecare valoare i, care este șeful suprem acesteia (sau dacă preferați termeni de corporație, managerul). Inițial, fiecare valoare i se are pe ea însăși pe post de manager. În momentul în care vrem să facem union între două valori, vom găsi șefii acestora, și vom seta șeful unuia dintre ei ca fiind celălalt. Implementarea arată cam așa:

Operația find
int find(int i) {
  if (sef[i] == i)       // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
    return i;            // il returnam
  return find(sef[i]); // altfel returnam seful sefului meu
}

Se observă că de data aceasta, pe cel mai rău caz, funcția find poate face N operații, deci are complexitate O(N)

Operația union
void union(int i, int j) {
  int sefi, sefj;

  sefi = find(i);   // seful suprem al lui i
  sefj = find(j);   // seful suprem al lui j

  sef[sefj] = sefi; // seful suprem al lui sefj devine sefi
}

Funcția union apelează de două ori find și mai face încă o operație. Chiar dacă find este o funcție lentă, putem considera că union este optimizată, pentru că am scăpat de acea parcurgere de complexitate N.

Ideea #3 - Optimizare find

O optimizare foarte importantă pentru funcția find pleacă de la observația că atunci când vrem să găsim șeful suprem al valorii i, noi trecem prin mai mulți șefi, șefi ai cărui șef suprem este egal cu cel al valorii i. Astfel, putem să actualizăm șefii acestor șefi în timpul parcurgerii recursive:

int find(int i) {
  if (sef[i] == i)     // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
    return i;          // il returnam
  return sef[i] = find(sef[i]); // altfel legam i la seful suprem, pe care il si returnam
}

Astfel ajungem la o complexitate de O(logN) atât pe find, cât și pe union, unde logN este adâncimea arborelui de manageri.

(Opțional) Ideea #4 - Optimizare union #2

Putem optimiza și mai mult algoritmul, având grijă ca în momentul în care vrem să unim două mulțimi să alegem corespunzător care șef devine subordonat celuilalt. Altfel spus, trebuie să alegem cum trebuie dacă șeful lui i devine seful șefului lui j sau viceversa. Pentru aceasta, trebuie să reținem pentru fiecare mulțime numărul elementelor ale acesteia, iar atunci când împreunăm două mulțimi, vom atașa mulțimea mică la mulțimea mare.

Temă

zigzag - varena Aplicație la liste
lacoada - varena Aplicație la liste

disjoint - varena
bile3 - varena