Dnia 30-03-2013 o 19:25:40 Michoo <m...@v...pl> napisał(a):

> On 30.03.2013 18:39, Roman W wrote:
>>
>> Nada sie i pewnie w praktyce zadziala, ale wymaga O(log N) pamieci.
>> Mozna to zrobic w O(1).
>
> Wybierasz pierwszą. W każdym kroku z prawdopodobieństwem P zależącym od
> ilości wczytanych linii wybierasz bieżącą a z (1-P) zostajesz przy
> poprzednim wyborze. Tylko trzeba mieć dobry generator dla takich
> sekwencji i nie nadziać się na zaokrąglenia.

moje prawie wszytkie losowania robi dla zakresu 256, więc o zaokrąglenia
nie trzeba się martwić, i pewnie szybciej działa, robiąc ok. n/255
prostych losowań, a nie n trudniejszych

--
Jordan Szubert