W dniu sobota, 30 marca 2013 17:20:48 UTC+1 użytkownik Roman W napisał:
> No zarówno indeksowanie linii jak i wybor n-tej linii sie
> kwalifikuje. Moze zle ooisalem zadanie. Zalozmy ze ktos Ci wysle
> Bardzo Duzy plik jako strumien danych przez siec. Nie mozesz zapisac
> pliku po swojej stronie. Wiesz ze plik jest skonczony ale nie wiesz
> ile ma linii. Dowiesz sie o tym ze dostales komplet danych jak
> otrzymasz na wejsciu umowiony znak ASCII. Wybierz z pliku losowa
> linie z jednorodnym rozkladem prawdopodobieństwa.
Nie znam rozwiązania, ale mogę na głos pomyśleć.

Zadanie uproscimy do podania numeru "nr" poczatkowego znaku, powrot
do oryginalnej wersji zadania bedzie banalny.

Poczatkowo
nr=0 - znaki liczymy od zera.
curr_byte=0 - numer wczytanego znaku, inkrementujemy po kazdym znaku
cnt_rows=1 - ilosc wierszy, inkrementujemy po kazdym wierszu


Czytamy po jednym znaku. Gdy poprzednim znakiem byl inny znak niz
znak nowej linii to nie robimy nic. Wiec algorytm dziala poprawnie
dla pierwszego wiesza - w nr jest poprawna wartosc.

Teraz sprobujemy krok indukcyjny na kolejne wiersze:

Jesli porzednim znakiem byl znak konca wiersza, to mamy poprawne wartosci:

nr - bajt rozpoczynajacy poprzednio wylosowany wiersz
curr_byte - bajt rozpoczynajacy ten wiersz
cnt_row - ilosc rozpoznanych wierszy do tej pory


Generujemy calkowita liczbe losowa z przedzialu otwartego od 1 do cnt_row.
Bylo do tej pory wczytanych cnt_row wierszy. Czyli prawdopodobienstwo ze
liczba losowa bedzie rowna 1 jest rowna 1/cnt_row. Jesli liczba losowa
rowna jest 1 to do zmiennej nr przypisujemy curr_byte. A wiec w zmiennej
nr po tym kroku bedzie poprawny (zgodny z rozkladem rownomiernym) wiersz,
wiec krok mozna powtarzac do konca.

Co konczy dowod - o ile sie nie myle :D

Pozdrawiam