algorytm.org

Problem przy rozwiązaniu dwóch zadań



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Forum www.algorytm.org :: Arytmetyka i procedury numeryczne
Witaj Gość   
[Zarejestruj się]  
[Zaloguj się]
Zamieść odpowiedź
 Problem przy rozwiązaniu dwóch zadań

Witam,

mam problem z dwoma zadaniami, prowadząca powiedziała że ich nie przyjmie bo są źle ale nie powiedziała co jest źle.

Pierwsze:

Przedstawiony algorytm wykorzystywany jest w turniejach ewolucyjnych do wyboru lepiej przystosowanych osobników (zamiast stałej 3 może być inny rozmiar „turnieju”)

Kod:
select(n)
P:= [1,2,...,n]
for i:= 1 to n do
for j:= 1 to 3 do
tj:= wylosowana liczba ze zbioru P
wybrany:= max(t1, t2, t3)

Jaka jest wartość oczekiwana liczby elementów zbioru P, które ani razu nie zostaną wybrane?

Chciałem wykorzystać wzór Bernoulliego
Pn(k )=(nk)∗p^k∗q^(n−k)
gdzie:
n- reprezentuję liczbę turniejów
k- reprezentuje liczba sukcesów – nie wylosowania liczby
i doszedłem do wniosku że wzór się skróci
Pn=p^k

Później obliczłem ilość wariacji
V =n^k

I podstawiam to wszystko pod wzór wartości oczekiwanej:
EX=Σxi pi
wynik:
EX=Σxi∗(1−(pi^k/n^k))^n

i drugi:
Załóżmy, że zbudowano drzewo BST dla kluczy 1,2,...,n w sposób następujący. Wygeneruj losową permutację π zbioru
{1,2,...,n}, a następnie wstaw do początkowo pustego drzewa wszystkie klucze w kolejności: π(1),π(2),...,π(n).
Oszacuj wartość oczekiwaną wysokości takiego losowego drzewa.

jako wynik podałem log2n gdyż taka jest wysokość drzewa zrównoważonego ale wydaje mi się że miałem uwzględnić również niezrównoważone ale nie wiem jak się do tego zabrać.

Gdyby ktoś mógł jakoś pomóc byłbym bardzo wdzięczny.
Cytuj
Zamieść odpowiedź Strona # 
Szybka odpowiedź

Kod:    


Powered by ccBoard