Element majoritar. Ciurul lui Eratostene Clasa a IX-a

1

I. Element majoritar

1. Prezentarea problemei

Se dă un şir de n numere naturale. Se cere să se verifice dacă există un element majoritar în acest

șir. Un element este majoritar dacă apare de cel puţin [n/2]+1 ori în şir

2. Soluţie O(n2)

Un algoritm naiv ar verifica pentru fiecare element din şir de câte ori mai apare acesta. O

astfel de rezolvare are complexitatea O(n2) ca timp şi O(n) ca memorie.

Subalgoritm bruteForce()

pentru i 1, n executa

nr 0

pentru j 1, n executa

daca a[i] = a[j] atunci

nr nr + 1

sf. daca

sf. pentru

daca nr > n/2 atunci

returneaza a[i]

sf. daca

sf. pentru

returneaza -1 //nu am gasit element majoritar

sfârşit subalgoritm

3. Soluţie O(n)

Algoritmul e prezentat în cartea Introducere în algoritmi de T.H.Cormen, C. E.

Leiserson, R. R. Rivest în felul următor: „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

Element majoritar. Ciurul lui Eratostene Clasa a IX-a

2

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.

cand -1 //initializam candidatul cu unul fictiv

nr 0 //numarul de voturi ale candidatului

pentru i 1, n executa

daca nr = 0 atunci

cand a[i]//posibilul candidat e cel actual

nr 1 //cu un vot

altfel

daca cand == a[i] atunci //daca mai e un vot pt posibilul

castig

nr nr + 1 //numaram votul

altfel //in caz contrar

nr nr – 1 //scadem votul

sf. daca

sf. daca

sf. pentru

//verificam daca posibilul candidat e majoritar

nr 0

Element majoritar. Ciurul lui Eratostene Clasa a IX-a

3

pentru i 1, n executa

daca cand = a[i] atunci

nr nr + 1

sf. daca

sf. pentru

daca nr > n/2 atunci

scrie cand “e majoritar”

altfel

scrie “nu majoritar”

sf. daca

Livada1 - http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1083

Avarcolaci - http://oni2014.cnlodobescu.ro/wp-content/uploads/2014/04/avarcolaci.pdf

II. Ciurul lui Eratostene

Fie n un număr natural (n≤10000). Să se genereze toate numerele prime mai mici decât n.

O primă idee ar fi să parcurgem toate numerele naturale din intervalul [2, n], pentru

fiecare număr să verificăm dacă este prim şi să afişăm numerele prime determinate.

O idee mai eficientă provine in antichitate şi poartă numele ciurul lui Eratostene. Ideea

este de a „pune în ciur” toate numerele mai mici decât n, apoi de a „cerne” aceste numere până

rămân în ciur numai numerele prime. Mai întâi „cernem” (eliminăm din ciur) toți multiplii lui 2,

apoi cernem multiplii lui 3, ş.a.m.d.

Vom reprezenta ciurul ca un vector cu 10000 de componente care pot fi 0 sau 1, cu

semnificația ciur[i]=0 dacă numărul i este prim şi 1 altfel.

Vom parcurge vectorul ciur de la 2 (cel mai mic număr prim), până la √n). Dacă ciur[i]

este 1 deducem că i este prim, dar toți multiplii lui nu vor fi (deci eliminăm din ciur toți multiplii

lui i).

pentru i 1, n executa

ciur[i] 0 //pp numerele sunt prime

sf. pentru

pentru i 2, √n executa

daca ciur[i] = 0 atunci //daca i este prim

pentru j 2, n/i executa

ciur[j * i] 1 //elimin multipli lui i

Element majoritar. Ciurul lui Eratostene Clasa a IX-a

4

sf. pentru

sf. daca

sf. pentru

pentru i 2, n executa

daca ciur[i] = 0 atunci

scrie i

sf. daca

sf. pentru

O idee de optimizare ar fi sa nu mai luam in calcul numerele pare pentru ca stim ca

singurul numar prim par e 2. Deci sa vedem noua varianta a programului:

pentru i 1, n executa

ciur[i] 0 //pp numerele sunt prime

sf. pentru

pentru i 3, √n, 2 executa

daca ciur[i] = 0 atunci //daca i este prim

pentru j 3, n/i, 2 executa

ciur[j * i] 1 //elimin multipli lui i

sf. pentru

sf. daca

sf. pentru

scrie “2”//afisam singurul numar prim par

pentru i 3, n, 2 executa

daca ciur[i] = 0 atunci

scrie i

sf. daca

sf. pentru

O altă posibilitate de optimizare ar putea fi marcarea multiplilor numarului prim i de

la i*i nu de la 2*i cum am făcut in prima variantă sau de la 3*i cum am făcut în a 2-a. Aceasta

optimizare este evidentă: orice numar prim compus multiplu de i mai mic decat i*i are un factor

prim mai mic decat i, si acel factor l-a marcat mai devreme, deci nu are rost sa il marcam si la

pasul i.

Element majoritar. Ciurul lui Eratostene Clasa a IX-a

5

Putem avea și optimizări de memorie. Pentru că nu mai avem nevoie de elementele cu

index par din șirul ciur, putem considera doar n/2 elemente în vector. Atunci semnificatia

lui ciur[i] s-a schimbat ciur[i] fiind 0 daca 2*i+1 e numar prim si 1 daca nu. De asemenea putem

considera vectorul ciur de tip char.