3 leilākais skaitlis

[Mr.Key]

Teiksim, ja jāatrod N lielākais skaitlis starp M garu skaitļu virkni, kur N un M ir lielāks par iekārtas atmiņas iespējām to visu gan kārtot, gan uzglabāt (piemēram, cauri rūterim plūstoša datu plūsma)

 

Risinājums kaut kur galvā ir, pāris tekošās max vērtības (absolūtais max un kandidāts max), kā arī viens vai divi diffi. Nezinu, vai risinājums ir, kādā brīdī jāpadomā.. doma tāda, ka nevis N lielā masīvā uzglabā tekošās atrastās max vērtības, bet glabā D kā atstarpes starp līdz šim atmestajām vērtībām, kas, atrodot jaunu max vērtību, ļautu pārrēķināt Nmax kandidāta vērtību, kura jau ir aizplūdusi (rūtera gadījumā nevarēs pastaigāt šurpu turpu ar pointeriem)....

 

Nevaru arī izdomāt praktisku vajadzību šādam uzdevumam, bet gribētos to atrisināt tā, ka lietotās atmiņas apjoms ir daži baiti un skaitļu plūsma teorētiski ir bezgalīga :)

 

Edit: Tā laikam nevarēs viss.. :)

http://en.wikipedia....ction_algorithm

 

Odds algorithm: http://en.wikipedia.org/wiki/Odds_algorithm

Edited November 8, 2011 by Mr.Key

[codez]

Teiksim, ja jāatrod N lielākais skaitlis starp M garu skaitļu virkni, kur N un M ir lielāks par iekārtas atmiņas iespējām to visu gan kārtot, gan uzglabāt (piemēram, cauri rūterim plūstoša datu plūsma)

Domāju, ka šāds risinājums nav iespējams, kā minimums tev ir vajadzīgas zināšanas par N lielākajiem skaitļiem.

 

 

Nevaru arī izdomāt praktisku vajadzību šādam uzdevumam, bet gribētos to atrisināt tā, ka lietotās atmiņas apjoms ir daži baiti un skaitļu plūsma teorētiski ir bezgalīga :)

Mans pēdējais risinājums bija ar mazu atmiņu, jo glabāju tikai 3 skaitļus iekš priority queue

[Mr.Key]

Domāju, ka šāds risinājums nav iespējams, kā minimums tev ir vajadzīgas zināšanas par N lielākajiem skaitļiem.

Nu re, ja atrisināsi šo problēmu, būsi ģēnijs. Līdz tam tev varētu interesēt kaut kas no šī: http://en.wikipedia...._in_mathematics ...

Edited November 8, 2011 by Mr.Key

[codez]

Nu re, ja atrisināsi šo problēmu, būsi ģēnijs. Līdz tam tev varētu interesēt kaut kas no šī: http://en.wikipedia...._in_mathematics ...

 

O, būs nākamajiem 5 gadiem ko darīt, savadāk jau domāju, ka dzīve tik neinteresanta.

[Kavacky]

Ko kā tāds komunistu funkcionārs? Mūsdienās piecgades nerullē.