eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingSzybki algorytm na permutacjęRe: Szybki algorytm na permutację
  • X-Received: by 10.182.19.129 with SMTP id f1mr290397obe.20.1461406205424; Sat, 23 Apr
    2016 03:10:05 -0700 (PDT)
    X-Received: by 10.182.19.129 with SMTP id f1mr290397obe.20.1461406205424; Sat, 23 Apr
    2016 03:10:05 -0700 (PDT)
    Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
    atman.pl!goblin2!goblin.stu.neva.ru!feeder.erje.net!2.us.feeder.erje.net!news.g
    lorb.com!sq19no229546igc.0!news-out.google.com!u9ni96igk.0!nntp.google.com!sq19
    no229538igc.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-ma
    il
    Newsgroups: pl.comp.programming
    Date: Sat, 23 Apr 2016 03:10:05 -0700 (PDT)
    In-Reply-To: <nffgc0$foj$1@node1.news.atman.pl>
    Complaints-To: g...@g...com
    Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=178.37.232.66;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    NNTP-Posting-Host: 178.37.232.66
    References: <nfbjra$fer$1@node2.news.atman.pl>
    <5...@g...com>
    <nfed5s$4oo$1@node2.news.atman.pl>
    <d...@g...com>
    <nffgc0$foj$1@node1.news.atman.pl>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <2...@g...com>
    Subject: Re: Szybki algorytm na permutację
    From: "M.M." <m...@g...com>
    Injection-Date: Sat, 23 Apr 2016 10:10:05 +0000
    Content-Type: text/plain; charset=ISO-8859-2
    Content-Transfer-Encoding: quoted-printable
    Xref: news-archive.icm.edu.pl pl.comp.programming:209340
    [ ukryj nagłówki ]

    On Saturday, April 23, 2016 at 11:47:45 AM UTC+2, bartekltg wrote:
    > On 23.04.2016 11:38, M.M. wrote:
    > > On Saturday, April 23, 2016 at 1:47:09 AM UTC+2, bartekltg wrote:
    > >> >On 22.04.2016 18:43, M.M. wrote:
    > >>> > >On Friday, April 22, 2016 at 12:22:35 AM UTC+2, Borneq wrote:
    > >>>> > >>z wykorzystaniem random()
    > >>>> > >>Przychodzi mi do głowy jeden pomysł: tablicę posortowanych wielkości n i
    > >>>> > >>drugą, początkowo wielkości 0.
    > >>>> > >>Z posortowanych wybieram za pomocą random(n) któryś element, i
    > >>>> > >>najważniejsze: w dziurę (dziura - element o indeksie random(n)) wkładam
    > >>>> > >>element ostatni.
    > >>>> > >>Potem wybieram za pomocą random(n-1) wkładam w dziurę.
    > >>>> > >>I tak dalej
    > >> >
    > >>> > >
    > >>> > >Może tak?
    > >>> > >for( int i=1 ; i<=N ; i++ )
    > >>> > > tab[i] = i;
    > >>> > >for( int i=0 ; i<N*2 ; i++ )
    > >>> > > swp( tab[rand()%N] , tab[rand()%N] );
    > >> >
    > >> >Bardzo źle.
    > >> >Wynonujesz 4N losowań.
    > >> >Czy rozkład wyniku jest równomierny, wcale bym się nie zakładał.
    > >> >
    > >> >pzdr
    > >> >bartekltg
    > > Nie wiem, też bym się nie założył, ale na pewno Knuth shuffle dał
    > > mniejsze odchylenie standardowe w kilku testach:
    >
    >
    > Knutha możęsz policzyć. Bardzo prosto. Wymyśl dowolną
    > permutację i licz prawdopodobieństwo, że ją wylosujesz.
    > W każdym kroku musisz wybrać właściwa liczbę i nie ma potem
    > możliwośći popsucia. 1 liczba z n, 1 liczba z n-1....
    > Łącznie prawdopodobieństwo 1/n! Identyczne dla dowolnej permutacji.

    Tak, zaletą knutha jest to, że można łatwo przeprowadzić dowód.



    > BTW, dlaczego wołasz srand( seed ); dwa razy?
    Chyba z rozpędu, zazwyczaj trzeba zadbać o to, aby obie metody dostały
    ten sam losowy ciąg, ale tutaj jest inna ilość losowań, więc
    nic to nie daje.

    Pozdrawiam

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj

Najnowsze wątki z tej grupy


Najnowsze wątki

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: