eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingIle czasu zajmie komputerowi rozszerzony algorytm euklidesa? › Re: Ile czasu zajmie komputerowi rozszerzony algorytm euklidesa?
  • X-Received: by 2002:ac8:a8b:: with SMTP id d11mr2271533qti.94.1576065194038; Wed, 11
    Dec 2019 03:53:14 -0800 (PST)
    X-Received: by 2002:ac8:a8b:: with SMTP id d11mr2271533qti.94.1576065194038; Wed, 11
    Dec 2019 03:53:14 -0800 (PST)
    Path: news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!goblin1!goblin.stu.neva.r
    u!g89no3751522qtd.0!news-out.google.com!w29ni969qtc.0!nntp.google.com!g89no3751
    516qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Wed, 11 Dec 2019 03:53:13 -0800 (PST)
    In-Reply-To: <1...@g...com>
    Complaints-To: g...@g...com
    Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=213.192.68.153;
    posting-account=f7iIKQoAAAAkDKpUafc-4IXhmRAzdB5r
    NNTP-Posting-Host: 213.192.68.153
    References: <e...@g...com>
    <f...@g...com>
    <7...@g...com>
    <1...@g...com>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <a...@g...com>
    Subject: Re: Ile czasu zajmie komputerowi rozszerzony algorytm euklidesa?
    From: g...@g...com
    Injection-Date: Wed, 11 Dec 2019 11:53:14 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    Xref: news-archive.icm.edu.pl pl.comp.programming:214530
    [ ukryj nagłówki ]

    W dniu środa, 11 grudnia 2019 04:40:28 UTC+1 użytkownik osobliwy nick napisał:
    > > Przychylam się do tej sugestii.
    > >
    > Ok. Zmotywowaliście mnie. Będę myślał w takim razie o powrocie do tematu
    programowania. A właściwie o zaczęciu od początku, bo pomimo, że wiem co to
    programowanie, jak to się robi itd., to moje praktycznie umiejętności są znikome. Co
    do języka myślałem o C++, bo często mam do policzenia jakieś matematyczne rzeczy, a
    ten język kojarzy mi się z takimi inżynierskimi i matematycznymi zastosowaniami. Poza
    tym łatwo znaleźć materiały na jego temat.

    Ja osobiście raczej bym odradzał C++ do Twoich zastosowań.
    Jest to język nadmiernie skomplikowany, i nawet nie za dobrze radzi sobie z liczbami
    (domyślnie implementuje arytmetykę modulo 2^32 albo 2^64)

    Raczej bym polecał albo Racket, bo jest bardzo prosty i jest dla niego dużo dobrych
    materiałów dydaktycznych, a do tego wspiera od razu arytmetykę o dowolnej precyzji
    oraz liczby wymierne. Spośród materiałów dydaktycznych jest książka "How To Design
    Programs", dostępna za darmo tutaj (jakościowo o rzędy wielkości lepsza od
    jakichkolwiek materiałów o C++, z jakimi miałem styczność):

    https://htdp.org/2019-02-24/

    Na podstawie tej książki powstał kurs o systematycznym projektowaniu programów:

    https://www.youtube.com/channel/UC7dEjIUwSxSNcW4PqNR
    QW8w

    Jest też nieco starsza, ale wciąż nie chcąca się zestarzeć książka "Structure and
    Interpretation of Computer Programs" (wydana swego czasu też po Polsku przez WNT jako
    "Struktura i Interpretacja Programów Komputerowych"), udostępniona za darmo na
    stronie MIT:

    https://mitpress.mit.edu/sites/default/files/sicp/in
    dex.html

    Kurs, na potrzeby którego książka została opracowana, również można znaleźć na
    youtubie:

    https://www.youtube.com/watch?v=-J_xL4IGhJA&list=PLE
    18841CABEA24090

    Warto ewentualnie rozważyć język Haskell, który jest bardziej złożony, ale ma dość
    wydajną implementacje, i jest też sobie w stanie poradzić z dużymi liczbami (i pod
    względem składni mocno przypomina klasyczną notację matematyczną).

    Rozwiązanie podlinkowanego przez Ciebie przykładu wyglądałoby tak.
    Najpierw definiujemy sobie iloczyn kartezjański listy list, żeby móc generować ciągi
    wartośći x1, ..., xN:

    cartprod [] = [[]]
    cartprod (xs:xss) = [x:ys | x <- xs, ys <- cartprod xss]

    wyprowadzenie powyższej definicji możesz znaleźć tutaj:
    http://myhaskelljournal.com/cartesian-product-of-lis
    ts/

    następnie definiujemy produkt kartezjański

    cartpow l n = cartprod $ take n $ repeat l

    gdzie (repeat l) tworzy nieskończoną listę powtórzeń listy l, zaś take n bierze tylko
    n początkowych elementów.

    Ponieważ jest u Ciebie warunek, że

    x1 >= x2 >= ... >= xN

    to możemy wybrać tylko te punkty z iloczynu kartezjańskiego, których wartościami są
    nierosnące ciągi:

    nonasc (x:y:zs) = x >= y && nonasc (y:zs)
    nonasc _ = True

    Wreszcie, funkcja budująca zbiory punktów [x1, ..., xN] może mieć postać:

    dom x n = [p | p <- (cartpow [0 .. x] n), nonasc p]

    czyli zbiór wszystkich punktów z potęgi kartezjańskiej, których kolejne współrzędne
    tworzą ciąg nierosnący.

    Można łatwo sprawdzić, że np. (dom 3 2) da nam wartość

    [[0,0],[1,0],[1,1],[2,0],[2,1],[2,2],[3,0],[3,1],[3,
    2],[3,3]]

    I teraz chcemy znaleźć elementy, które spelniają Twoje kryterium.
    Żeby Haskell obsłużył liczby wymierne, trzeba załadować moduł Data.Ratio:

    import Data.Ratio

    Operator dzielenia wymiernego liczb całkowitych jest wówczas wyrażany symbolem %.

    Pozwala to zdefiniować nam zbiór interesujących Cię liczb jako:

    ws x y p = [(sum [(p^xn)%(2^xn) | xn <- seq]) * ((2^(y-1))%(2^(x+y)-p^y))
    | seq <- (dom x (y-1))]

    i wtedy możemy sprawdzić, że wyrażenie (ws 3 3 3) da nam listę

    [8 % 37,
    10 % 37,
    12 % 37,
    13 % 37,
    15 % 37,
    18 % 37,
    35 % 74,
    39 % 74,
    45 % 74,
    27 % 37]

    Jest to inny zbiór od tego, który podałeś w swoim drugim poście, więc możliwe, że źle
    zrozumiałem specyfikację.

    W każdym razie "rozmawiając" sobie z interpreterem Racketa albo Haskella, możesz dość
    łatwo przeszukać interesujące Cię dziedziny.

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

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: