Diferente pentru problema-majoritatii-votului intre reviziile #11 si #32

Nu exista diferente intre titluri.

Diferente intre continut:

Problema majorităţii votului
h1. Problema majorităţii votului
Negruşeri Cosmin
== include(page="template/implica-te/scrie-articole" user_id="andrici_cezar") ==
(Categoria _Algoritmi_, Autor _Cosmin Negruşeri_)
(toc){width: 20em}*{text-align:center} *Conţinut:*
* 'Enunţ':problema-majoritatii-votului#enunt
** 'Soluţie $O(n^2^)$':problema-majoritatii-votului#solutie-1
** 'Soluţie $O(n + k)$ particulară':problema-majoritatii-votului#solutie-2
** 'Soluţie $O(n)$ cu tabele de dispersie':problema-majoritatii-votului#solutie-3
** 'Soluţie $O(n log{~2~}n)$':problema-majoritatii-votului#solutie-4
** 'Soluţie $O(n)$ cu statistici de ordine':problema-majoritatii-votului#solutie-5
** 'Soluţie $O(n log{~b~} k)$ particulară':problema-majoritatii-votului#solutie-6
** 'Soluţie $O(n + k)$ probabilistică':problema-majoritatii-votului#solutie-7
** 'Soluţie $O(n)$':problema-majoritatii-votului#solutie-8
* 'Generalizare':problema-majoritatii-votului#generalizare
** 'Soluţii $O(n*k)$':problema-majoritatii-votului#solutie-9
* 'Bibliografie':problema-majoritatii-votului#bibliografie
În acest articol dezbatem problema dezvoltării de algoritmi eficienţi pentru determinarea candidatului care a întrunit un număr majoritar de voturi.
Problema enunţată formal este următoarea: Se dă un şir de n numere naturale, se cere determinarea unui element care apare de cel puţin [n/2]+1 ori în şir dacă există un astfel de element în şir.
h2(#enunt). Enunţ
Un algoritm naiv ar verifica pentru fiecare element din şir de câte ori mai apare acesta. O astfel de rezolvare are complexitatea O(n^2) ca timp si O(n) ca memorie.
bq. Se dă un şir de $n$ numere naturale. Se cere determinarea unui element care apare de cel puţin $[n/2]+1$ ori în şir dacă există un astfel de element în şir.
 
h3(#solutie-1). Soluţie O(n^2^)
 
Un algoritm naiv ar verifica pentru fiecare element din şir de câte ori mai apare acesta. O astfel de rezolvare are complexitatea $O(n^2^)$ ca timp şi $O(n)$ ca memorie.
== code(cpp) |
int bruteForceMajority(int n, int[] a)
    for (int i = 0; i < n; i++) {
          int nr = 0;
          for (int j = 0; j < n; j++) {
               if (a[j]==a[i]) nr++;
          }
          if  (nr > n / 2) return a[i];
        int nr = 0;
        for (int j = 0; j < n; j++) {
            if (a[j]==a[i])
                nr++;
        }
        if  (nr > n / 2)
            return a[i];
    }
    return -1;
}
==
Dacă numerele din şir aparţin unei mulţimi {1, 2, ... k} iar acest k este mic comparativ cu n, atunci putem să îmbunătăţinm ideea de mai devreme şi să folosim un şir auxiliar b, unde b[x] va număra de câte ori apare un număr x în şirul nostru. Această soluţie are complexitate O(n + k) ca timp şi O(n + k) ca spaţiu.
 
h3(#solutie-2). Soluţie O(n + k) particulară
 
Dacă numerele din şir aparţin unei mulţimi ${1, 2, ... k}$ iar acest $k$ este mic comparativ cu $n$, atunci putem să îmbunătăţim ideea de mai devreme şi să folosim un şir auxiliar $b$, unde $b[x]$ va număra de câte ori apare un număr $x$ în şirul nostru. Această soluţie are complexitate $O(n + k)$ ca timp şi $O(n + k)$ ca spaţiu.
 
== code(cpp) |
int countMajority(int n, int[] a, int k) {
     int[] b = new int[k];
    int[] b = new int[k];
    for (int i = 0; i < n; i++) {
         b[a[i]]++;//incrementăm numărul de apariţii al elementului a[i]
        b[a[i]]++;    // incrementăm numărul de apariţii al elementului a[i]
    }
    for (int i = 0; i < k; i++) {
         if (b[i] > n/2) return i;
         if (b[i] > n/2)
             return i;
    }
    return -1;
}
==
Soluţia această este destul de eficientă în cazul menţionat anterior, dar când k este mult mai mare decât n, atunci această rezolvare ajunge să fie foarte lentă. Însă folosind o structură avansată de date putem să facem soluţia din nou eficientă. Această structură are la bază o tabelă de dispersie, ea mapează perechi de numere <cheie, valoare>, cheile vor fi numerele din şir, iar valorile vor fi numărul de apariţii al cheilor în şirul nostru.
 
h3(#solutie-3). Soluţie O(n) cu 'tabele de dispersie':tabele-hash-prezentare-detaliata
 
Soluţia precedentă este destul de eficientă în cazul menţionat anterior, dar când $k$ este mult mai mare decât $n$, atunci această rezolvare ajunge să fie foarte lentă. Însă folosind o structură avansată de date putem să facem soluţia din nou eficientă. Această structură are la bază o tabelă de dispersie: ea mapează perechi de numere $<cheie, valoare>$, unde cheile vor fi numerele din şir, iar valorile vor fi numărul de apariţii al cheilor în şirul nostru.
 
== code(cpp) |
int hashMajority(int n, int[] a) {
    HashMap<Integer, Integer> b = new HashMap<Integer, Integer>();
    for (int i = 0; i < n; i++) {
         if (b.get(a[i])==null) {
         if (b.get(a[i]) == null) {
             b.put(a[i], 1);
         } else {
             int num = b.get(a[i]);
         }
    }
    for (int i = 0; i < n; i++) {
         if (b.get(a[i]) > n/2) return i;
         if (b.get(a[i]) > n/2)
             return i;
    }
    return -1;
}
==
Această soluţie are complexitate O(n) ca timp, şi O(n) memorie suplimentară. Menţionăm că un dezavantaj al acestei soluţii ar fi că este una randomizată.
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii a unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.
Această soluţie are complexitate $O(n)$ ca timp, şi $O(n)$ memorie suplimentară. Menţionăm că un dezavantaj al acestei soluţii ar fi că este una randomizată.
 
h3(#solutie-4). Soluţie O(n log{~2~}n)
 
O altă soluţie care ar permite numărarea eficientă a numărului de apariţii al unui element în acest şir ar fi să sortăm şirul pentru că apoi elementele egale vor fi în poziţii consecutive.
 
== code(cpp) |
int sortMajority(int n, int[] a) {
    Arrays.sort(a);
    int i = 0;
    while (i < n) {
          int j = i;
          while (j < n && a[j + 1]==a[i]) j++;
          if (j – i + 1 > n / 2) return a[i];
          while (j < n && a[j + 1] == a[i])
              j++;
          if (j–i+1 > n/2)
              return a[i];
          i = j + 1;
    }
    return -1;
}
==
Această soluţie are complexitatea O(n log n), nu foloseşte suplimentară, dar suprascrie şirul iniţial.
Această soluţie are complexitatea O(n log n), nu foloseşte memorie suplimentară, dar suprascrie şirul iniţial.
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia n/2.Ştim că există algoritmi de selecţie care ne găsesc elemente de poziţie o fixată k din şirul sortat în complexitate O(n). Astfel vom găsi mai întâi elementul de pe poziţia n/2 iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate O(n) iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.
h3(#solutie-5). Soluţie O(n) cu 'statistici de ordine':problema/sdo
 
O idee ce ne vine pe urma acestei rezolvări este aceea că în şirul sortat, un element majoritar se va afla în şirul sortat şi pe poziţia $n/2$. Ştim că există algoritmi de selecţie care ne găsesc elemente de o poziţie fixată $k$ din şirul sortat în complexitate $O(n)$. Astfel, vom găsi întâi elementul de pe poziţia $n/2$ iar apoi vom verifica dacă acesta este elementul majoritar al şirului. Astfel avem o soluţie de complexitate $O(n)$ iar şirul iniţial va fi modificat. Există metode de selecţie nerandomizate, dar pentru uşurinţa implementării vom folosi una randomizată.
== code(cpp) |
int  select(int n, int[] a, int left, int right, int k) {
        i = left + ran.nextInt(right – left + 1);
        aux = a[left]; a[left] = a[i]; a[i] = aux;
        int x = a[left];
        i = left  1;
        i = left - 1;
        j = right + 1;
        while (true) {
           do { i++; } while a[i] < x;
           do { j--; } while a[j] > x;
            if (i < j) { aux = a[i]; a[i] = a[j]; a[j] = aux; }
            else break;
           if (i < j) {
               aux = a[i]; a[i] = a[j]; a[j] = aux;
           } else
               break;
        }
        q = right  left + 1;
        q = right - left + 1;
        if (k <= q) {
            right = j;
        } else {
}
int selectMajority(int n, int[] a) {
   int x = select(n,  a,  0, n  1, n / 2 - 1), nr = 0;
   int x = select(n,  a,  0, n - 1, n / 2 - 1), nr = 0;
   for (int i = 0; i < n; i++) {
         if (a[i]==x) nr++;
       if (a[i] == x)
           nr++;
   }
   if (nr > n/2) return x;
   else return -1;
   if (nr > n/2)
       return x;
   else
       return -1;
}
==
O altă idee de rezolvare porneşte de la observaţia următoare: Dacă există un element majoritar în şir, atunci ultima lui cifră va fi elementul majoritar în şirul format din ultimele cifre a numerelor din şirul iniţial. Această observaţie este valabilă pentru orice cifră a numerelor nu doar ultima. Astfel putem determina pentru fiecare a x-a cifră a numemerelor care este cifra majoritară şi apoi să punem cap la cap cifrele majoritare pentru a forma numărul majoritar. Evident putem să folosim orice bază, dacă folosim baza b şi valoarea maximă a unui număr ar fi k atunci algoritmul va avea complexitatea O(n log in baza b din k) şi foloseşte memorie suplimentară O(b * log in baza b din k).  În practică putem considera acest algoritm ca fiind liniar. Să vedem o implementare a algoritmului pentru b = 1000 şi k = 999.999.999.
 
h3(#solutie-6). Soluţie O(n log{~b~} k) particulară
 
O altă idee de rezolvare porneşte de la observaţia următoare: dacă există un element majoritar în şir, atunci ultima lui cifră va fi elementul majoritar în şirul format din ultimele cifre a numerelor din şirul iniţial. Această observaţie este valabilă pentru orice cifră a numerelor nu doar ultima. Astfel putem determina pentru fiecare a $x$-a cifră a numerelor care este cifra majoritară şi apoi să punem cap la cap cifrele majoritare pentru a forma numărul majoritar. Evident putem să folosim orice bază, dacă folosim baza $b$ şi valoarea maximă a unui număr ar fi $k$ atunci algoritmul va avea complexitatea $O(n log{~b~} k)$ şi foloseşte memorie suplimentară $O(b * log{~b~}k)$.  În practică putem considera acest algoritm ca fiind liniar. Să vedem o implementare a algoritmului pentru $b = 1000$ şi $k = 999 999 999$.
 
== code(cpp) |
int digitMajority(int n, int[] a) {
     int[][] dig = new int[3][1000];
     for (int i = 0; i < n; i++) {
           int tmp = a[i];
           for (int j = 0; j < 3; j++) {
                 dig[j][tmp % 1000]++;
                 tmp /= 1000;
           }
     }
     int ret = 0;
     for (int i = 0; i < 999; i++) {
           if (dig[0][i] > n/2) ret += i;
           if (dig[1][i] > n/2) ret += i * 1000;
           if (dig[2][i] > n/2) ret += i * 1000000;
    int[][] dig = new int[3][1000];
    for (int i = 0; i < n; i++) {
        int tmp = a[i];
        for (int j = 0; j < 3; j++) {
            dig[j][tmp % 1000]++;
            tmp /= 1000;
        }
    }
    int ret = 0;
    for (int i = 0; i < 999; i++) {
        if (dig[0][i] > n/2)
            ret += i;
        if (dig[1][i] > n/2)
            ret += i * 1000;
        if (dig[2][i] > n/2)
            ret += i * 1000000;
     }
     int nr = 0;
     for (int I = 0; I < n; i++) {
           if (a[i]==ret) nr++;
         if (a[i] == ret)
             nr++;
     }
     if (nr > n/2) return ret;
     else return -1;
     if (nr > n/2)
         return ret;
     else
         return -1;
}
==
Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea 0.5 să nu îl nimerim, dacă alegem k numere aleatoare din şirul respectiv, atunci avem probabilitatea
(˝)^k să nu îl nimerim. Astfel algoritmul nostru va fi să luăm k numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste k numere în şirul nostru. Dacă folosim o structură ce mapează chei valori atunci algoritmul va avea complexitate O(n + k) şi probabilitate de reuşită P = 1 - (˝)^k. În practică o valoare de 10 pentru k ne dă o probabilitate de reuşită de 0.999. Să vedem mai departe codul:
 
h3(#solutie-7). Soluţie O(n + k) probabilistică
 
Putem aborda probabilistic. Astfel dacă alegem un număr aleator şi există o celebritate, avem probabilitatea $0.5$ să nu îl nimerim. Dacă alegem $k$ numere aleatoare din şirul respectiv, atunci avem probabilitatea <tex> (\frac{1}{2})^k </tex> să nu îl nimerim. Astfel algoritmul nostru va fi să luăm $k$ numere aleatoare, iar apoi să numărăm de câte ori apare fiecare din aceste $k$ numere în şirul nostru. Dacă folosim o structură ce mapează $<chei, valori>$ atunci algoritmul va avea complexitate $O(n + k)$ şi probabilitate de reuşită <tex> P = 1 - (\frac{1}{2})^k </tex>. În practică o valoare de $10$ pentru $k$ ne dă o probabilitate de reuşită de $0.999$. Să vedem mai departe codul:
 
== code(cpp) |
int probabilisticMajority(int n, int[] a) {
    Random ran = new Random(System.currentTimeMilis());
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < 10; i++) {
          map.put(a[ran.nextInt(n)], 0);
        map.put(a[ran.nextInt(n)], 0);
    }
    for (int i = 0; i < 10; i++) {
          if (map.contains(a[i])) {
             int num = map.get(a[i]);
             if (num + 1 > n/2) return a[i];
             map.remove(a[i]);
             map.add(a[i], num + 1);
          }
        if (map.contains(a[i])) {
            int num = map.get(a[i]);
            if (num + 1 > n/2) return a[i];
            map.remove(a[i]);
            map.add(a[i], num + 1);
        }
    }
    return -1;
}
==
Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea [1] şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
Imaginaţi-vă o sală de conferinţă în care votanţii ţin fiecare o placă ce poartă numele candidatului preferat. Să presupunem se ajunge la o bataie generală în care votanţii cu convingeri diferite încep să se lovească reciproc cu plăcile. Să mai presupunem că fiecare votant care pune la pământ un membru cu alte convingeri este simultan şi el pus la pământ de adversar. Este evident că dacă ar fi vreun candidat care are mai multe voturi decăt toate voturile celorlalţi candidaţi, atunci această luptă va fi câştigată de acest candidat şi la dispariţia haosului din urma luptei, votanţii ce au rămas în picioare vor fi susţinători ai candidatului amintit. În caz că nu există o majoritate clară pentru un candidat sau altul, la finalul luptei rămân ăn picioare votanţi care susţin acelaşi candidat, dar acesta poate să nu fie reprezentantul majorităţii. Deci, în general, dacă cineva rămâne în picioare, preşedintele conferinţei este obligat să verifice dacă întradevar candidatul întruneşte votul a jumătate plus unu de votanţi. Algoritmul practic folosit de noi va fi un fel de joc al împerecherilor între candidaţi de opinii diferite până când toţi votanţii rămaşi necuplaţi vor susţine acelaşi candidat.
Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi k neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat cand pentru că altfel am fi putut să cuplăm câţiva dintre ei.
Menţionăm că această rezolvare doar operaţii în care se verifică dacă două valori sunt identice, fapt ce se poate dovedi util pentru obiecte complexe care ar substitui candidaţii din problemă. Rezolvările anterioare s-au folosit de faptul că între elementele şirului ar exista o relaţie de ordine sau că am putea efectua asupra lor operaţii aritmetice.
 
h3(#solutie-8). Soluţie O(n)
 
Un ultim algoritm şi cel mai eficient dintre cele prezentate apare în lucrarea [1] şi probabil acesta este cunoscut cititorilor. Autorii au un mod plastic de a prezenta algoritmul:
 
„Imaginaţi-vă o sală de conferinţă în care votanţii ţin fiecare o placă ce poartă numele candidatului preferat. Să presupunem că se ajunge la o bătaie generală în care votanţii cu convingeri diferite încep să se lovească reciproc cu plăcile. Să mai presupunem că fiecare votant care pune la pământ un membru cu alte convingeri este simultan şi el pus la pământ de adversar. Este evident că dacă ar fi vreun candidat care are mai multe voturi decât toate voturile celorlalţi candidaţi, atunci această luptă va fi câştigată de acest candidat şi la dispariţia haosului din urma luptei, votanţii ce au rămas în picioare vor fi susţinători ai candidatului amintit. În caz că nu există o majoritate clară pentru un candidat sau altul, la finalul luptei rămân în picioare votanţi care susţin acelaşi candidat, dar acesta poate să nu fie reprezentantul majorităţii. Deci, în general, dacă cineva rămâne în picioare, preşedintele conferinţei este obligat să verifice dacă într-adevar candidatul întruneşte votul a jumătate plus unu din votanţi. Algoritmul practic folosit de noi va fi un fel de joc al împerecherilor între candidaţi de opinii diferite până când toţi votanţii rămaşi necuplaţi vor susţine acelaşi candidat.”
 
Realizăm acest algoritm parcurgând lista votanţilor şi ţinând un contor cu numărul de candidaţi $k$ neîmperecheaţi până la pasul curent, evident dacă ei sunt neîmperecheaţi trebuie să susţină acelaşi candidat pentru că altfel am fi putut să cuplăm câţiva dintre ei.
Menţionăm că această rezolvare are doar operaţii în care se verifică dacă două valori sunt identice, fapt ce se poate dovedi util pentru obiecte complexe care ar substitui candidaţii din problemă. Rezolvările anterioare s-au folosit de faptul că între elementele şirului ar exista o relaţie de ordine sau că am putea efectua asupra lor operaţii aritmetice.
== code(cpp) |
int mooreMajority(int n, int[]  a) {
    int cand = -1, k = 0;
    for (int i = 0; i < n; i++) {
          if (k==0) {
             cand = a[i];
             k = 1;
          } else  if (a[i]==cand) {
              k++;//nu am putut împerechea pe votantul i şi astfel trebuie să mărim numărul de votanţi necuplaţi
          } else k--;//cuplăm votantul i cu orice votant ce îl susţine pe cand şi micşorăm astfel numărul de votanţi necuplaţi
    }
    if (cand < 0) return cand;
    //faza de verificare
        if (k == 0) {
            cand = a[i];
            k = 1;
        } else if (a[i] == cand) {
            k++;   // nu am putut împerechea pe votantul i şi astfel trebuie să mărim numărul de votanţi necuplaţi
        } else
            k--;   // cuplăm votantul i cu orice votant ce îl susţine pe cand şi micşorăm astfel numărul de votanţi necuplaţi
    }
    if (cand < 0)
        return cand;
    // verificare
    int nr = 0;
    for (int i = 0; i < n; i++) {
          if (a[i]==cand) nr++;
        if (a[i] == cand)
            nr++;
    }
    if (nr > n / 2) return cand;
    else return – 1;
    if (nr > n / 2)
        return cand;
    else
        return – 1;
}
==
Această problemă a fost propusă în prima rundă a concursului Bursele Agora în 2005, Atunci nu era posibilă ţinerea tuturor numerelor din fişier în memorie şi citirea numerelor era greoaie.Doar doi concurenţi au reuşit obţinerea unui punctaj maxim la acea rundă. Autorul a fost unul dintre aceştia, el a evitat citirea de două ori a fişierului de intrare prin folosirea soluţiei cu cifre, în care calcula două rezultate pentru două baze diferite b1 şi b2 alese aleator la startul rulării, iar apoi  verifica dacă candidaţii care erau probabil câştigatori erau egali. Aceasta rezolvare făcea improbabilă scrierea unui răspuns incorect.
Vom generaliza acum problema: Se dă un şir de n numere naturale şi un număr întreg k, se cere determinarea tuturor elementelor care apar de cel puţin [n/k]+1 ori în şir.
 
Această problemă a fost propusă în prima rundă a concursului Bursele Agora în 2005. Atunci nu era posibilă ţinerea tuturor numerelor din fişier în memorie şi citirea numerelor era greoaie. Doar doi concurenţi au reuşit obţinerea unui punctaj maxim la acea rundă. Autorul a fost unul dintre aceştia. El a evitat citirea de două ori a fişierului de intrare prin folosirea soluţiei cu cifre, în care calcula două rezultate pentru două baze diferite b1 şi b2 alese aleator la startul rulării, iar apoi verifica dacă candidaţii care erau probabil câştigatori erau egali. Aceasta rezolvare făcea improbabilă scrierea unui răspuns incorect.
 
h2(#generalizare). Generalizare
 
bq. Se dă un şir de $n$ numere naturale şi un număr întreg $k$, se cere determinarea tuturor elementelor care apar de cel puţin $[n/k]+1$ ori în şir.
 
h3(#solutie-9). Soluţii O(n*k)
 
Primele trei rezolvări prezentate pentru problema iniţială pot fi evident generalizate şi folosite şi pentru această problemă. Generalizarea abordării care implica folosirea cifrelor pentru a rezolva noua problemă pare imposibilă. Vom vorbi mai departe de două din celelalte trei abordări.
Evident dacă un număr apare de cel puţin [n/k] + 1 ori în şir atunci el va apărea în şirul sortat pe una din poziţiile i * [n/k] cu i de la 1 la k. De aici se conturează algoritmul următor: determinăm în O(n * k) elementele de pe poziţiile i * [n/k] iar apoi verificăm care dintre acestea sunt elemente majoritare în sensul menţionat mai sus. Acest algoritm are complexitate liniară daca îl considerăm pe k o constantă.
A doua soluţie este similară cu cea mai bună soluţie pentru prima problemă, numai că în loc să grupăm câte doi votanţi diferiţi vom grupa câte k votanţi cu păreri diferite.
 
== code(cpp) |
int[] mooreKMajority(int n, int[]  a, int k) {
    int[] cand = new int[k - 1], notMatched = new int[k - 1],  num = new int[k-1];
    Arrays.fill(cand, -1);
    int num = 0;
    //faza de cuplare
    // cuplare
    for (int i = 0; i < n; i++) {
          boolean found = false;
          for (int j = 0; j < k - 1; j++) {
                if (cand[j]==a[i]) {
                   notMatched[j]++;
                   found = true;
                   break;
        boolean found = false;
        for (int j = 0; j < k - 1; j++) {
            if (cand[j] == a[i]) {
                notMatched[j]++;
                found = true;
                break;
            }
        }
        if (!found) {
            for (int j = 0; j < k - 1; j++) {
                if (notMatched[j] == 0) {
                    cand[j] = a[i];
                    notMatched[j] = 1;
                    found = true;
                    break;
                }
          }
          if (!found) {
              for (int j = 0; j < k - 1; j++) {
                    if (notMatched[j]==0) {
                       cand[j] = a[i];
                       notMatched[j] = 1;
                       found = true;
                       break;
                    }
              }
              if (!found) {
                  for (int  j = 0; j < k – 1; j++) notMatched[j]--;
              }
          }
            }
            if (!found) {
                for (int  j = 0; j < k – 1; j++) notMatched[j]--;
            }
        }
    }
   //faza de verificare
   // verificare
   for (int i = 0; i < n; i++) {
          for (int j = 0; j < k - 1; j++) {
                if (a[i]==cand[j] && notMatched[j] != 0)  num[j]++;
          }
       for (int j = 0; j < k - 1; j++) {
           if (a[i] == cand[j] && notMatched[j] != 0)  num[j]++;
       }
   }
   int numMaj = 0;
   for (int j = 0; j < k - 1; j++) {
        if (num[j] > n/k) numMaj++;
       if (num[j] > n/k) numMaj++;
   }
   int[] ret = new int[numMaj];
   numMaj = 0;
   for (int j = 0; j < k - 1; j++) {
        if (num[j] > n/k) {
            ret[numMaj] = cand[j];
            numMaj++;
        }
       if (num[j] > n/k) {
           ret[numMaj] = cand[j];
           numMaj++;
       }
   }
   return ret;
}
==
Bibliografie:
[1] T.H.Cormen, C. E. Leiserson, R. R. Rivest, Introducere în algoritmi, ed. Agora 2000
[2] R. S. Boyer, J. S. Moore A Fast Majority Vote Algorithm
 
h2(#bibliografie). Bibliografie
 
# T.H.Cormen, C. E. Leiserson, R. R. Rivest, _Introducere în algoritmi_, ed. Agora 2000
# R. S. Boyer, J. S. Moore, _A Fast Majority Vote Algorithm_
 
!probleme-majoritatii-votului?IA_bug_in_FF2.jpg!

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
4383