[darsto]

#programowanie #euler #projecteuler #matematyka

Cześć mirki, rozwiązuję problemy z projecteuler.net i utknąłem przy # 573 "Unfair race" [1] . Ewidentnie brakuje mi tutaj wiedzy, ale jestem uparty i chciałbym bardzo to rozwiązać, a przynajmniej wiedzieć czego konkretnie muszę się douczyć. Czy mógłby mi ktoś napisać w jaki sposób zostały policzone te przykładowe wartości P(n, k)?

[1]: https://projecteuler.net/problem=573

[darsto]

@darsto: problem dotyczy prawdopodobieństwa

[m.....r]

@darsto: a wszystkie poprzednie już rozwiązałeś? :)

[c.....a]

@darsto: obawiam się, że wielowymiarową całką, którą można jakoś (?) sprytnie wyznaczyć.

[f.....y]

Może coś wniosę:

Niech Xi oznacza próbę losową o rozkładzie U(0,1) ; Xi <= X(i+1). Ponieważ czas jest równy droga/prędkość to tk = X_k*n/k Prawdopodobieństwo, że wygra gość z numerem k oznacza, że to tk <= ti dla każdego 1<=i<=n; i!=k. Teraz popatrzmy na n-k lepszych zawodników od k. Prawdopodobieństwo że k+1 nie wygra z k oznacza, że zmienna losowa, nazwijmy ją Y(k+1), z rozkładu

[m.....r]

@darsto: @fade-away: nie mam wiedzy matematycznej, ale mam skrypt, który jest w stanie mniej-więcej pokazać rozkład, może sie przydać do weryfikacji rozwiązań https://repl.it/EDGw/1 :)

[m.....r]

@darsto: znalazłem jakąś zależność, jak chcesz mogę coś o tym napisać
np. pierwszy wyraz jest zawsze równy (n-1)^(n-1) / n^(n-1), a ostatni 1/n, te środkowe też nie są przypadkowe i mają związek z potęgami,
np. dla n = 5
E(5) = (4^4 + 2x4x3^3 + 2x4x3^3 + 4^4 + 5^4) / 5^4

stworzyłem pewien wzór, ale przeanalizowałem za mało danych i wymaga on poprawek

[MasterSoundBlaster]

@darsto:
Nieźle zabrnąłeś. Gratki.