Motto: Arta de a cere este greu de stăpânit. Unii nici nu încearcă, alţii nu se mai opresc. (Gracian Y Morales)
C. Determinarea elementului majoritar
O secvenţă de 2015 nume (nu toate distincte) sunt citite secvenţial. Ştii că unul din nume apare majoritar (de cel puţin 1008 ori).
Dispui de un counter iniţializat pe 0, care poate fi incrementat sau decrementat de câte ori apare un nume.
Dar ai o memorie extrem de slabă; nu poţi reţine decât un singur nume: cel citit anterior. Evident, când apare un nume, poţi să-l compari cu cel reţinut în această memorie simplă.
Definiţi o strategie (algoritm liniar) care, după ce sunt citite toate numele, să puteţi spune care este cel majoritar.
Updatare: Accept si solutii in varianta mai slaba, in care numele memorat nu este obligatoriu ultimul citit (vezi comentariu).
Sursă: Macalestear Problem of the Week 1198
Logic
Versiunea in engleza:
Determine the Majority
A sequence of 1198 names (not all distinct) is going to be read out to you, and you are told that one name is in the majority, i.e., it occurs at least 600 times. You have a counter that starts at 0 and that you can increment or decrement whenever you hear a name. But your short-term memory is very low: you can remember only a single name at any given time (but when you hear a name you can check if it is the same as the one in your memory).
Find a strategy that, after all names are read, will allow you to declare the name of the majority person.
Problema mai poate fi gasita in
- M. J. Fischer and S. L. Salzberg, Finding a majority among n votes, J. of Algorithms 3:4 (Nov 1989) 362-380.
- Si in P. Winkler, Mathematical Puzzles, A Connoisseur's Collection, (A K Peters), p. 104.
" you can remember only a single name at any given time"
înseamnă că poți memora un singur nume, citit la un moment dat.
Din traducerea romțnească eu înțeleg că numele memorat este cel citit anterior citirii actuale, ceea ce nu este în concordanță cu textul englez și poate induce în eroare pe cei care vor să rezolve problema.