Dodaj do ulubionych

wojenko, wojenko...

08.02.03, 21:25
Wielki ruch zapanował i podniecenie dnia pewnego w
Królestwie Turyngów, albowiem wieści o wojnie
nieuchronnej nadeszły i spokój mieszkańców krzemowych,
stateczność i dobrobyt z dawien dawna miłujących
zburzyły. W całym kraju krzątaninę wielką rozpoczęto i
przygotowania nadzwyczajne. Najtęższe zaś w Królestwie
umysły kwarcowe jak co dzień przy wielkim stole w
pałacowej karczmie zasiadły, gdzie trunki najlepsze w
całym kraju podawano, umysł wybornie rozjaśniający, by
problemy przedyskutować państwowe.
- Tak nam to wygląda - Książę Wielki Binarny
przedstawiał, głównym marszałkiem na dworze króla
Tyrynga Pierwszego będący - że za godzin sześćdziesiąt
wielką armię Turyngan na wojnę wystawić nam przyjdzie,
a to nam dziś tylko wiadomo, że ich liczba większa niż
trzydziesta druga potęga dwójki być nie może, bo tyle
naród nasz niezwyciężony pod rządami Jego Światłości
osobników liczy.
- Wiekie badania i przeglądy kontrolne od wczoraj
prowadzimy - rzekł tedy hetman Bitnicki, szklanicę
pękatą odstawiwszy i piankę plazmową niezrównaną z ust
otarłszy - by ostateczną liczbę do kampanii zdolnych
poznać, ale co wam mogę powiedzieć, to że akcję tą na
godzinę przed wyruszeniem armii skończymy, wielka jest
bowiem troska naszego pana o obywateli dobro i
detaliczność kontroli stąd wynikająca.
Co powiedziawszy, wzrok zatroskany na twarze
słuchaczy skierował, głowami kiwających nad
prawdziwością słów ministra a mądrość swojego władcy
kontemplujących.
- W tym rzecz jednak najpilniej rozwiązania żądająca
- głos Książę Binarny ponownie zabrał - że armię naszą
na oddziały podzielić trzeba i na czele każdego z nich
hetmana postawić, a król w poczuciu swoim
sprawiedliwości znieść nie może, by dwa dowolne
oddziały różną liczbę żołnierzy liczyły, innych tym
samym trosk różnym hetmanom przysparzając.
Co powiedziawszy, szklanicę z nektarem złocistym
podniósł i łyk potężny pociągnąwszy, zapas sił
witalnych a rozumu klarowność podreperował.
- Wiadomym jest oczywiście dla panów - rzekł hetman,
znowu uwagę na drugi koniec stołu skupiając - że pan
nasz, w swej przenikliwości niezrównany i świadom
ułomności natury krzemowej, od zawsze nie pozwala
żadnemu hetmanowi liczbą większą niż szesnasta potęga
dwójki żołnierzy dowodzić, by każdego z nich pamiętać
potrafił i talenta jego bojowe optymalnie
wykorzystywał. Sam zaś, głównym wodzem armii będąc i
osobisty kontakt z każdym hetmanem mieć musząc, ich
liczbę róznież na szesnastą potęgę dwójki ustalił,
rozsądku swego a skromności dowód dając i własnych
możliwości pysznie nie przeceniając.
- Dlatego - marszałek, skupienie i mądrość na twarzach
towarzyszy czytając, rzecz podsumować zdecydował -
problem, który dziś w gronie tym zacnym rozwiązać nam
przyszło, na odszukaniu sposobu podziału naszej armii
na oddziały polegać będzie, tak jednak, by dla
każdej liczby żołnierzy, która na polach podzamkowych
za szećdziesiąt godzin niecałych stanąć może, sposób
ten uwag Najjaśniejszego Pana bezwzględnie
przestrzegał, a najmniejszej możliwej liczbie żołnierzy
do swoich domów, ku hańbie wiecznej, powrócić
nakazywał. By, gdy żołnierze do stolicy zjadą, bez
zwłok dalszych i według planu z góry ułożonego armię
zhierarchizować i na czas w kierunku wroga wyruszyć, ku
wielkim zwycięstwom naszego króla a wiecznej narodu
chwale...

* * *

Czy potrafisz zaproponować algorytm, który dla dowolnej
liczby żołnierzy - z zachowaniem powyższych więzów -
pozwoli znaleźć optymalną liczbę oddziałów i żołnierzy
przypadających na każdy z nich? Jeśli masz jakiś
pomysł, a nie jesteś pewien jego "optymalności",
przedstaw go tutaj, a może wspólnymi siłami jego
przydatność ocenimy i z czasem do najsłuszniejszej
metody dojdziemy...;) Oczywiście - przedstawienie planu
nie uwzględniającego wskazówek króla karane jest
ścięciem głowy i szeregiem innych szykan, o których już
tylko Cardemon opowiedzieć by potrafił....

pozdrawiam - Kopperek
Obserwuj wątek
    • cardemon Re: wojenko, wojenko... 09.02.03, 14:00
      kopperek napisał:

      > (...)
      > Oczywiście - przedstawienie planu
      > nie uwzględniającego wskazówek króla karane jest
      > ścięciem głowy i szeregiem innych szykan, o których już
      > tylko Cardemon opowiedzieć by potrafił....


      Cardemon wlasnie powrocil z palmowych plaz i jego umysl nadal pracuje na
      jalowym biegu... No coz, nic bardziej nie rozleniwia niz slonce, plaza, palmy i
      te... no wiecie... ;)

      Pozdrowienia, CdM
      • kopperek Re: wojenko, wojenko... 09.02.03, 14:19
        o, witam witam:)

        Byłbym jednakowoż wdzięczny panu Cardemonowi, gdyby
        otworzył leniwie rozmarzone oczy i spróbował trochę
        pokombinować...:) Niekoniecznie tylko nad zakończeniem.
        Bo problem zaczyna mnie trochę boleć (jego geneza jest
        jak najbardziej z życia wzięta, po prostu przydałaby mi
        się znajomość tego algorytmu), a przy tym - wydaje mi
        się, że jest sam w sobie dosyć ciekawy.

        pozdrawiam - Kopperek
    • mesquaki Re: wojenko, wojenko... 09.02.03, 19:34
      Ojej, cudne aze oczom straszno od wesela :)))).

      Przepraszam najmocniej za odarcie problemu z pieknej jego szaty, jednak ze
      plynu klarownosc umyslu reperujacego nie posiadam a szykan sie okrutnie lekam
      przeto chcialabym sie upewnic co do jego istoty.
      Czy trzeba rozlozyc liczbe zolnierzy na iloczyn takich dwoch liczb nie
      wiekszych niz 2 do 16 (ewentualnie +1 jesli nie wliczamy hetmana) tak, zeby
      powstala reszta byla najmniejsza?

      m
      • kopperek Re: wojenko, wojenko... 10.02.03, 13:45
        mesquaki napisała:

        > Przepraszam najmocniej za odarcie problemu z pieknej
        jego szaty, jednak ze
        > plynu klarownosc umyslu reperujacego nie posiadam a
        szykan sie okrutnie lekam
        > przeto chcialabym sie upewnic co do jego istoty.
        > Czy trzeba rozlozyc liczbe zolnierzy na iloczyn takich
        dwoch liczb nie
        > wiekszych niz 2 do 16 (ewentualnie +1 jesli nie
        wliczamy hetmana) tak, zeby
        > powstala reszta byla najmniejsza?
        >
        > m

        Mes, Twoje odarcie oczywiście jest precyzyjne,
        profesjonalne i bezlitośnie w istotę problemu trafiające.
        Niektórym, jak widać, nawet płynów nie potrzeba
        złocistych, tacy to dobrze mają.

        pozdrawiam - Kopperek

        PS Chociaż - moje doświadczenia wskazują, że amerykanckie
        płyny reperujące nienadzwyczajnej są jakości.
    • andy._ Re: wojenko, wojenko... 10.02.03, 10:28
      Witam po swiąteczno-noworoczno-feryjnym okresie zastoju i marazmu,

      Okazuje się, że rozleniwiają nie tylko plaża i palmy, ale również śniegowe
      stoki i świerki. Tekst Kopperka zaiste piękny, chociaż wymaga pewej
      koncentracji aby wyłuskać sedno. Odarcie Mesquaki, choć brutalne (jak to
      odarcie) wydaje się trafne, więc prezentuję szkic narzucającego się siłowego
      algorytmu:
      Rozkładamy liczbę żołnierzy na czynniki pierwsze i sprawdzamy czy największy
      czynnik jest nie większy niż szesnasta potęga dwójki. Jeśli tak to mamy
      podział, jeśli nie to odstawiamy jednego żołnierza na bok i powtarzamy
      procedurę aż do skutku.
      Mam nadzieję, że uda się w przeciągu 60 godzin wyszukać coś bardziej
      finezyjnego,
      Pozdr. A.
      • marchewa4 Re: wojenko, wojenko... 10.02.03, 11:21
        andy._ napisał:

        > Rozkładamy liczbę żołnierzy na czynniki pierwsze i sprawdzamy czy największy
        > czynnik jest nie większy niż szesnasta potęga dwójki. Jeśli tak to mamy
        > podział, jeśli nie to odstawiamy jednego żołnierza na bok i powtarzamy
        > procedurę aż do skutku.

        I skutek mamy od razu, bo jesli liczba zolnierzy jest mniejsza od 2^32, a
        najwiekszy czynnik pierwszy jest wiekszy niz 2^16, to jest to liczba pierwsza.
        Po odjeciu jednego zolnierza pozostanie nam parzysta liczba zolnierzy, i to
        taka, ze jej polowa jest mniejsza niz 2^16.

        Ale wydaje mi sie to za proste. Chyba czegos nie zrozumialem.

        Pozdrawiam

        M.

        PS. Nie tylko palmy rozleniwiaja, snieg tez ;-)
        • kopperek Re: wojenko, wojenko... 10.02.03, 13:37
          marchewa4 napisał:

          Zerknij proszę do mojej odpowiedzi dla Andy'ego.

          > jesli liczba zolnierzy jest mniejsza od 2^32, a
          > najwiekszy czynnik pierwszy jest wiekszy niz 2^16, to
          jest to liczba pierwsza.

          Z tym się oczywiście zgadzam.

          > Po odjeciu jednego zolnierza pozostanie nam parzysta
          liczba zolnierzy, i to
          > taka, ze jej polowa jest mniejsza niz 2^16.

          Z tym już nie! Oczywiście to taki poboczny wątek, bo
          odnosi się so pomysłu Andy'ego, który sam w sobie budzi
          (przynajmniej moje) wątpliwości. Ale - dla porządku:) -
          weźmy liczbę pierwszą rzędu 2^30. Po odjęciu 1 mamy nadal
          około 2^30, połowa z niej to ok. 2^29, nie?

          >
          > Ale wydaje mi sie to za proste. Chyba czegos nie
          zrozumialem.
          >
          > Pozdrawiam
          >
          > M.
          >
          > PS. Nie tylko palmy rozleniwiaja, snieg tez ;-)

          PS Mi do rozleniwienia nie potrzeba niczego oprócz
          odrobiny dobrej woli...:P
        • marchewa4 Re: wojenko, wojenko... 10.02.03, 13:40
          marchewa4 napisał:

          No nie! Ten snieg to mnie nie tylko rozleniwil, ale i mozg mi zamrozil. Czy nie
          mozna jakos skasowac tych glupot, ktore poprzednio napisalem?
          Czerwienie sie od sniegu i ze wstydu i dopoki nie wymysle czegos w miare chocby
          rozsadnego, zabieram sie za pourlopowe zaleglosci.

          Pozdrawiam serdecznie

          M.

          > I skutek mamy od razu, bo jesli liczba zolnierzy jest mniejsza od 2^32, a
          > najwiekszy czynnik pierwszy jest wiekszy niz 2^16, to jest to liczba pierwsza.
          > Po odjeciu jednego zolnierza pozostanie nam parzysta liczba zolnierzy, i to
          > taka, ze jej polowa jest mniejsza niz 2^16.
          >
          > Ale wydaje mi sie to za proste. Chyba czegos nie zrozumialem.
          >
          > Pozdrawiam
          >
          > M.
          >
          > PS. Nie tylko palmy rozleniwiaja, snieg tez ;-)
      • kopperek Re: wojenko, wojenko... 10.02.03, 13:31
        Witam również, miło widzieć sstarych znajomych:).

        andy._ napisał:

        > Rozkładamy liczbę żołnierzy na czynniki pierwsze i
        sprawdzamy czy największy
        > czynnik jest nie większy niż szesnasta potęga dwójki.
        Jeśli tak to mamy
        > podział, jeśli nie to odstawiamy jednego żołnierza na
        bok i powtarzamy
        > procedurę aż do skutku.

        Andy - nie do końca rozumiem. Czyli - jeżeli ten
        największy czynnik jest mniejszy od 2^16, to bierzesz go
        jako jedną z liczb? To chyba nie implikuje, że iloczyn
        pozostałych czynników też będzie mniejszy od 2^16. Pewnie
        chodziło Ci o coś innego, ale zamiast spekulacji -
        kontrprzykład: liczba żołnierzy rozkłada się na trzy
        czynniki, powiedzmy około 17000, około 15000 i 5. Nie
        sądzę, aby było po sprawie.

        pozdrawiam - Kopperek
        • andy._ Re: wojenko, wojenko... 10.02.03, 22:43
          kopperek napisał:

          > Andy - nie do końca rozumiem. Czyli - jeżeli ten
          > największy czynnik jest mniejszy od 2^16, to bierzesz go
          > jako jedną z liczb?
          Taka była moja intencja.

          > To chyba nie implikuje, że iloczyn
          > pozostałych czynników też będzie mniejszy od 2^16.
          Tak mi się wydawało, ale to chyba efekt śniegu, karnawału itp.

          > Pewnie chodziło Ci o coś innego,
          Niestety nie. Mea culpa!

          > ale zamiast spekulacji -
          > kontrprzykład: liczba żołnierzy rozkłada się na trzy
          > czynniki, powiedzmy około 17000, około 15000 i 5. Nie
          > sądzę, aby było po sprawie.
          Słusznie nie sądzisz. 15000*5 będzie większe niż 65536.

          Zaczynam główkowanie od nowa
          Pozdr. A.
    • Gość: Baton Re: wojenko, wojenko... IP: *.apex / 192.168.10.* 10.02.03, 15:12
      Koncepcyi nijakiej nie mam, azaliz dreczy mnie pytanie.....
      .... czy liczebnosc oddzialu nie moze przekroczyc szesnastej
      potegi dwojki wliczajac wen dowodzacego hetmana, czy tez
      ow hetman moze byc jedna osoba przewyzszajaca maxymalny
      dozwolony stan liczebny oddzialu?
      Nie wiem czy ma to jakikolwiek wplyw na tok rozumowania
      przy rozwiazaywaniu problemu, aczkolwiek pewne zalozenia
      poczatkowe nalezaloby poczynic.... ;-)))
      • kopperek dobre pytanie 10.02.03, 15:31
        Gość portalu: Baton napisał(a):

        > Koncepcyi nijakiej nie mam, azaliz dreczy mnie pytanie.....
        > .... czy liczebnosc oddzialu nie moze przekroczyc
        szesnastej
        > potegi dwojki wliczajac wen dowodzacego hetmana, czy tez
        > ow hetman moze byc jedna osoba przewyzszajaca maxymalny
        > dozwolony stan liczebny oddzialu?
        > Nie wiem czy ma to jakikolwiek wplyw na tok rozumowania
        > przy rozwiazaywaniu problemu, aczkolwiek pewne zalozenia
        > poczatkowe nalezaloby poczynic.... ;-)))

        Ha, słusznie! Rzecz nie wydaje się krytyczna, ale -
        należy ją uściślić. Pisząc zagadkę miałem w głowie
        sytuację, gdy cały oddział łącznie z hetmanem liczy
        najwyżej 2^16, chociaż z treści wynika raczej co
        innego:). OK, przyjmijmy wersję, że hetman wlicza się do
        liczebności oddziału (a więc maksymalna liczba
        szeregowców to 65535).
        Podobnie - mówiąc o jak najmniejszej liczbie żołnierzy,
        którzy wrócą do domów, nie wprowadzam rozróżnienia między
        szeregowcem i hetmanem - to znaczy: łączna ilość
        szeregowców i hetmanów, którzy na wojnę nie pójdą,
        powinna być minimalizowana.

        pozdrawiam - Kopperek
        • Gość: Baton Re: dobre pytanie IP: *.apex / 192.168.10.* 10.02.03, 15:43
          Wobec powyzszego ja jeszcze pomarudze.... ;-)))

          Czy w tej sytuacji przyjmujemy iz krol NIE jest
          jednym z hetmanow i w efekcie liczebnosc
          calego krolestwa wynosi 2^32+1 (ten 1 to krol)?
          Czy tez moze liczba szeregowcow i hetmanow
          lacznie wynosi 2^32-1 (ten 1 to znowu krol
          bedacy ostatnia osoba do uzupelnienia maxymalnej
          liczby nmieszkancow krolestwa)? ;-)))

          Dodam, ze chodzi mi po glowie jakas koncepcja,
          ale ile (jesli w ogole) jest cos warta sprawdze
          i ewentualnie ja przedstawie.... :-))
          • kopperek Re: dobre pytanie 10.02.03, 16:03
            Gość portalu: Baton napisał(a):

            > Wobec powyzszego ja jeszcze pomarudze.... ;-)))
            >
            > Czy w tej sytuacji przyjmujemy iz krol NIE jest
            > jednym z hetmanow i w efekcie liczebnosc
            > calego krolestwa wynosi 2^32+1 (ten 1 to krol)?
            > Czy tez moze liczba szeregowcow i hetmanow
            > lacznie wynosi 2^32-1 (ten 1 to znowu krol
            > bedacy ostatnia osoba do uzupelnienia maxymalnej
            > liczby nmieszkancow krolestwa)? ;-)))
            >
            > Dodam, ze chodzi mi po glowie jakas koncepcja,
            > ale ile (jesli w ogole) jest cos warta sprawdze
            > i ewentualnie ja przedstawie.... :-))

            Hehehe:))) Bardzo zacnie marudzisz, Batonie. Król jest z
            importu. I nie jest hetmanem:). On jest w ogóle "ponad
            wszystko", i - ha! - potrafi dowodzić 65536 hetmanami,
            więc jednak - jest od nich odrobinę zdolniejszy:). Albo -
            po prostu sam nie bierze udziału w walce (a hetmani
            tak), więc tak czy inaczej martwi się tylko o hetmanów,
            oni tymczasem zarówno o podkomendnych jak i o samych
            siebie:).

            Schodząc na ziemię: obydwie liczby tego rozkładu (patrz
            post Mes, nawiasem mówiąc jakoś umknęła mi tam ta
            wątpliwość odnośnie liczebności oddziału) mogą wynosić aż
            do 2^16.

            Kopperek
      • the_ladybird Re: wojenko, wojenko... 10.02.03, 16:40
        Ja rozumiem to tak:

        X = a * (Y + 1) + b

        gdzie X to całkowita liczba żołnierzy (<= 2 ^ 32),
        Y - liczebność oddziału (<= 2 ^ 16),
        a - liczba oddziałów (takoż od 2 ^ 16 mniejsza lub równa)
        b - ma być jak najmniejsze.

        "Bezmyślny" algorytm to pętla po Y:
        - Y - startujemy od Y równego 2^16 z krokiem -1
        - dzieląc kolejno X/Y dostajemy a i b, aż do momentu, w którym a > 2^16
        - b = X - a * (Y + 1) - zapamiętujemy lub odrzucamy
        - po ostatnim kroku zostajemy przy najmniejszym b
        wada: w przypadku Y bliskiego 2 ^ 32 potrzeba 2 ^ 16 kroków. Godzina nie
        starczy....

        Algorytm "od końca", czyli od b
        - zakładamy b = 0
        - dzielimy X na czynniki pierwsze.
        - jeśli KAŻDY z nich jest <= 2 ^ 16 to trzeba sprawdzić, czy te czynniki da się
        poskładać w dwie liczby, każda <= 2 ^ 16 (a niekoniecznie musi się dać!)
        - jeśli się udało - stop!
        - jeśli nie - b = b + 1

        zatrzymałam się na etapie sprawdzania, czy te liczby da się poskładać - wyszło
        mi, że to jest kluczowy i wcale niełatwy moment...

        • mesquaki Re: wojenko, wojenko... 10.02.03, 17:42
          the_ladybird napisała:

          >
          > Algorytm "od końca", czyli od b
          (..)
          > zatrzymałam się na etapie sprawdzania, czy te liczby da się poskładać -
          > wyszło mi, że to jest kluczowy i wcale niełatwy moment...
          >

          Witaj Ladybird
          Trafiłam w to samo miejsce :). Na przeszukiwanie kombinacji tych czynników
          pierwszych nie widzę jakoś algorytmu o rozsądnym czasie.

          Tymczasem jednak, jako że urlopy, świerki i palmy to dla mnie czysta
          abstrakcja, oddeleguję się lepiej do zadań własnych, eh...

          pozdrawiam (z wędzidłem w pysku ;)
          m

        • kopperek Re: wojenko, wojenko... 10.02.03, 20:33
          the_ladybird napisała:

          >
          > Algorytm "od końca", czyli od b
          > - zakładamy b = 0
          > - dzielimy X na czynniki pierwsze.
          > - jeśli KAŻDY z nich jest <= 2 ^ 16 to trzeba
          sprawdzić, czy te czynniki da
          > się
          > poskładać w dwie liczby, każda <= 2 ^ 16 (a
          niekoniecznie musi się dać!)
          > - jeśli się udało - stop!
          > - jeśli nie - b = b + 1
          >
          > zatrzymałam się na etapie sprawdzania, czy te liczby da
          się poskładać - wyszło
          > mi, że to jest kluczowy i wcale niełatwy moment...
          >


          Witaj ladybird, Ciebie też już dawno nie było:)

          Mam parę uwag, a jako pierwszą - stwierdzenie, że ja nie
          znam rozwiązania i tym samym występuję tutaj z tej samej
          pozycji co inni userzy.
          Do rzeczy: postawiony przez Ciebie problem "poskładania"
          jest faktycznie niebanalny, ciekawe czy ktoś znajdzie tu
          jakąś sprytną drogę. Warto natomiast wspomnieć, że to
          oczywiscie tylko fragment całości, bo być może rozkład na
          liczby mniejsze od 2^16 możliwy nie będzie, a wtedy też
          istnieje rozwiązanie, które jest lepsze od innych i także
          trzeba go umieć znaleźć. No ale - po kolei:), to chyba
          dobry pomysł żeby zacząć od prostszego przypadku.

          Uwaga ogólna: oczywiście, algorytm "bezmyślny" daje dobry
          wynik, ale jak słusznie zauważyłaś - jest zbyt złożony. W
          gruncie rzeczy nasz problem jest zagadnieniem
          optymalizacji - jak znaleźć ten optymalny podział
          możliwie najprostszą drogą. Przecież każda chwila
          dodatkowej zwłoki może drogą królestwo kosztować...:)
          Trzeba to mieć na uwadze także przy analizowaniu tego
          problemu "składania" z czynników pierwszych - też w końcu
          możnaby sprawdzić wszystkie możliwości, pytanie czy można
          to zrobić szybciej.

          pozdrawiam - Kopperek
          • mesquaki Re: wojenko, wojenko... 10.02.03, 21:35
            kopperek napisał:

            > Warto natomiast wspomnieć, że to
            > oczywiscie tylko fragment całości, bo być może rozkład na
            > liczby mniejsze od 2^16 możliwy nie będzie, a wtedy też
            > istnieje rozwiązanie, które jest lepsze od innych i także
            > trzeba go umieć znaleźć. No ale - po kolei:), to chyba
            > dobry pomysł żeby zacząć od prostszego przypadku.
            >

            Wtedy przyjmujemy resztę równą 1, czyli rozkładamy na czynniki pierwsze
            liczbę (X-1), ..i tak dalej do skutku względnie śmierci, cokolwiek nastąpi
            wcześniej :).
            m
            • the_ladybird Re: wojenko, wojenko... 11.02.03, 09:20
              Witam wszystkich, miło mi usłyszeć ciepłe słowa na dzień dobry :)
              Wiecie, jak to jest - tu się nie da wpaść na pięć minut.

              pomysł nr3:

              polega on na niepodważalnej prawdzie, że każda liczba z przedziału (2^16+1,
              2^32) ma lub nie ma swojego niezmienialnego rozkładu - to my wstrzeliwujemy się
              gdzieś i odległość od tej, która ów rozkład posiada da nam minimalną liczbę
              odesłanych do domu żołnierzy.

              robimy tabelę (ma wspomóc poglądowość):

              X 2^16+1 2^16+2 ... 2^32
              2^16+1
              2^16+2
              ...
              2^32

              Tabela jest symetryczna
              Wyciągamy pierwiastek z liczby żołnierzy (L, ok?), którzy się stawili na
              wojenkę i zaokrąglamy go w dół (nazwę tą liczbę SQ_X), podnosimy ją do
              kwadratu. Trafiamy w ten sposób w miejsce na przekątnej.
              Reszta (R = L - SQ_X^2) powie nam o ile miejsc w tabeli przesunąć się w prawo.
              Aby się tego dowiedzieć dzielimy resztę R przez pierwiastek SQ_X i zaokrąglamy
              w dół:
              delta_X = Floor[ R / SQ_X^2 ]

              Nowa liczba startowa to SQ_X*(SQ_X + delta_X).

              Pozostaje do sprawdzenia przekątna (prostopadła do osi symetrii tabeli) o jeden
              w prawo od startowej liczby.

              Sprawdzamy więc pary (aż trafimy na taką, której iloczyn jest mniejszy od L):
              x1 = SQ_X - 1
              x2 = SQ_X + delta_X + 2

              następnie:

              x1 = SQ_X - 2
              x2 = SQ_X + delta_X + 3

              aż x2 osiągnie 2^16

              Ponieważ SQ_X + delta_X może być znacznie mniejsze od 2^16 x2 można wybierać
              losowo. Znacznie szybciej dojdziemy do poprawnego wyniku....

              Mam nadzieję, że wyjaśniłam a nie zaciemniłam... ufff....

              pozdrawiam
              • the_ladybird Re: wojenko, wojenko... 11.02.03, 09:26
                the_ladybird napisała:

                > Pozostaje do sprawdzenia przekątna (prostopadła do osi symetrii tabeli) o
                > jeden w prawo od startowej liczby.
                >
                > Sprawdzamy więc pary (aż trafimy na taką, której iloczyn jest mniejszy od L):
                > Ponieważ SQ_X + delta_X może być znacznie mniejsze od 2^16 x2 można wybierać
                > losowo. Znacznie szybciej dojdziemy do poprawnego wyniku....

                Ten etap można zresztą dopracować - znamy bowiem L i SQ_X*(SQ_X + delta_X) -
                ich różnica może podpowiedzieć z grubsza, (a może dokładnie? co? ktoś wie tak
                od razu?) gdzie strzelać...
                • the_ladybird Re: wojenko, wojenko... 11.02.03, 09:40
                  Wyszło mi, że A (A to ta liczba odejmowana od SQ_X) jest najmniejszą liczbą
                  taką, że:

                  a ^ 2 + a*(delta_X) > SQ_X * (SQ_X + delta_X + 1) - L

                  trzeba więc rozwiązać równanie zamiast nierówności i zaokrąglić a w górę (tak?)


                  czy to, że pozbyłam się wszystkich iteracji a zostawiłam kilka prościutkich
                  równań zadowoli Kopperka? ;)
                  • the_ladybird Re: wojenko, wojenko... 11.02.03, 09:56
                    Dokończę, żeby było idealnie.
                    Z równania kwadratowego dostajemy dwie liczy A - mniejszą od zera odrzucamy -
                    większą od zera sprawdzamy:

                    jeśli SQ_X + delta_X + A + 1 > 2^16 to A = 0
                    jeśli SQ_X + delta_X + A + 1 < 2^16 to A = A (zaokrąglone w górę)

              • andy._ Re: wojenko, wojenko... 11.02.03, 09:53
                Oj gęsty ten pomysł nr3. Niestety nie mam czasu aby go trawić (niestety trzeba
                też czasem trochę popracować). Zajrzę tu za jakiś czas, może coś się rozwinie

                Pozdr. A.
              • the_ladybird Re: wojenko, wojenko... 11.02.03, 10:54
                znowu błąd w pisaniu :(

                > robimy tabelę (ma wspomóc poglądowość):
                >
                > X 2^16+1 2^16+2 ... 2^32
                > 2^16+1
                > 2^16+2
                > ...
                > 2^32
                >
                > Tabela jest symetryczna

                Tabela ma wyglądać tak:
                X 1 2 ... 2^16
                1
                2
                ...
                2^16

                w jej komórki wpisujemy iloczyn liczb. Tabela jest symetryczna

    • andy._ Re: wojenko, wojenko... 11.02.03, 09:13
      Wygląda na to, że panuje zgoda co do startu optymalnego algorytmu. Mam tu na
      myśli iteracyjny algorytm "od końca" Ladybird, zbliżony zresztą do mojego
      pierwszego niewypału - za bardzo poszedłem na skróty. Dalszy postępowanie
      sprowadza się do grupowania czynników pierwszych i sprawdzania czy otrzymane
      dwie liczby (iloczyny w grupach) spełniaja ograniczenie <=2^16.
      Nasuwa mi się prosty schemat, ale nie potrafię udowodnić jego poprawności ani
      podać kontrprzykładu - może komuś to sie uda:
      Zakładam, że mamy już posortowane czynniki pierwsze sprawdzanej liczby
      żołnierzy.
      Jeżeli największy ɮ^16 to kolejna iteracja (1 żołnierz do domu).
      Jeżeli nie to mamy pierwszą grupę z jednym czynnikiem i
      POWRÓT: obliczamy iloczyn pozostałych. Jeśli <=2^16 to sukces!
      (To wszystko już było, a teraz hipoteza)
      Jeżeli nie (iloczyn drugiej grupy ɮ^16) to mnożymy pierwszą grupę przez
      kolejne największe czynniki.
      Jesli iloczyn przekrocza 2^16 to próbujeny kolejny mniejszy czynnik, jesli nie
      to wracamy do POWRÓT. Jeśli wyczerpały sie czynniki to kolejna duża iteracja (1
      żołnierz do domu).
      Patrzę na napisany teskt i nie wygląda mi on zbyt jasno, ale może wytrwałym uda
      się przez ten opis przedrzeć.
      Jeśli nikomu nie uda się wyszukać kontrprzykładu to zacznę wierzyć, że podana
      hipoteza jest poprawnym algorytmem - a może komuś uda się to udowodnić?

      Pozdr. A.
      • andy._ Re: wojenko, wojenko... 11.02.03, 09:21
        Powtarzam tekst bo znowu zapomniałem, że znak > trzeba otoczyć spacjami aby był
        czytelny w niektórych przegladarkach:

        Wygląda na to, że panuje zgoda co do startu optymalnego algorytmu. Mam tu na
        myśli iteracyjny algorytm "od końca" Ladybird, zbliżony zresztą do mojego
        pierwszego niewypału - za bardzo poszedłem na skróty. Dalszy postępowanie
        sprowadza się do grupowania czynników pierwszych i sprawdzania czy otrzymane
        dwie liczby (iloczyny w grupach) spełniaja ograniczenie <=2^16.
        Nasuwa mi się prosty schemat, ale nie potrafię udowodnić jego poprawności ani
        podać kontrprzykładu - może komuś to sie uda:
        Zakładam, że mamy już posortowane czynniki pierwsze sprawdzanej liczby
        żołnierzy.
        Jeżeli największy > 2^16 to kolejna iteracja (1 żołnierz do domu).
        Jeżeli nie to mamy pierwszą grupę z jednym czynnikiem i
        POWRÓT: obliczamy iloczyn pozostałych. Jeśli <=2^16 to sukces!
        (To wszystko już było, a teraz hipoteza)
        Jeżeli nie (iloczyn drugiej grupy > 2^16) to mnożymy pierwszą grupę przez
        kolejne największe czynniki.
        Jesli iloczyn przekrocza 2^16 to próbujeny kolejny mniejszy czynnik, jesli nie
        to wracamy do POWRÓT. Jeśli wyczerpały sie czynniki to kolejna duża iteracja (1
        żołnierz do domu).
        Patrzę na napisany teskt i nie wygląda mi on zbyt jasno, ale może wytrwałym uda
        się przez ten opis przedrzeć.
        Jeśli nikomu nie uda się wyszukać kontrprzykładu to zacznę wierzyć, że podana
        hipoteza jest poprawnym algorytmem - a może komuś uda się to udowodnić?

        Pozdr. A.
      • the_ladybird Re: wojenko, wojenko... 11.02.03, 09:22
        andy._ napisał:

        > Wygląda na to, że panuje zgoda co do startu optymalnego algorytmu.

        a figa! :D

        > Mam tu na
        > myśli iteracyjny algorytm "od końca" Ladybird, zbliżony zresztą do mojego
        > pierwszego

        aha. masz rację. ale zobaczyłam to dopiero, gdy wysłałam mój - przepraszam za
        mimowolny plagiat :)
        • marchewa4 Do the_ladybird - pytanie 11.02.03, 13:52
          Nie mam tu w pracy niestety tyle swobnody, zeby spokojnie przeanalizowac
          proponowany przez Ciebie algorytm, ale sprobuje na przykladzie.

          Niech L = 2 ^ 17 = 131072.
          SQ_X = 362, SQ_X ^ 2 = 131044, R = 28, delta_X = 0

          A: min(a) (a^2 > 362 * 363 - 131072) -> A = 19

          O ile zrozumialem, to x1 = SQ_X - A, x2 = SQ_X + delta_X + A + 1.
          Zatem x1 = 344, x2 = 383, a ich iloczyn wynosi 131752, czyli wiecej niz L.

          Czy ktorys krok zle zrozumialem?

          Pozdrawiam serdecznie

          M.
          • the_ladybird Re: Do the_ladybird - pytanie 11.02.03, 14:05
            > Czy ktorys krok zle zrozumialem?
            Dobrze zrozumiałeś. To ja znowu źle przepisałam :(

            w równaniu powinno być:
            a ^ 2 + a*(delta_X + 1) > SQ_X * (SQ_X + delta_X + 1) - L

            wtedy a wychodzi 18 a nie 19, czyli ok, największa jest 18 - 19 daje już za
            duże rozwiązania
            • marchewa4 Re: Do the_ladybird - pytanie 11.02.03, 14:20
              the_ladybird napisała:

              > > Czy ktorys krok zle zrozumialem?
              > Dobrze zrozumiałeś. To ja znowu źle przepisałam :(
              >
              > w równaniu powinno być:
              > a ^ 2 + a*(delta_X + 1) > SQ_X * (SQ_X + delta_X + 1) - L
              >
              > wtedy a wychodzi 18 a nie 19, czyli ok, największa jest 18 - 19 daje już za
              > duże rozwiązania

              Ale jesli a = 18, to x1 = 345, x2 = 382, a ich iloczyn 131790, czy cos
              poplatalem?

              M.
              • the_ladybird Re: Do the_ladybird - pytanie 11.02.03, 15:09
                marchewa4 napisał:
                > Ale jesli a = 18, to x1 = 345, x2 = 382, a ich iloczyn 131790, czy cos
                > poplatalem?

                SQ_X = 362 (tyle Ci wyszło przecież?)
                a = 18

                x1=362-18=344
                x2=362+0+18+1=381

                x1*x2=131064
                L=131072
                L-x1*x2=8

                ok?
                • marchewa4 Czesciowo OK ;-) 12.02.03, 08:49
                  the_ladybird napisała:

                  > marchewa4 napisał:
                  > > Ale jesli a = 18, to x1 = 345, x2 = 382, a ich iloczyn 131790, czy cos
                  > > poplatalem?

                  Tak, rzeczywiscie poplatalem oznaczenia we wzorach. Gratuluje spostrzegawczosci.

                  > SQ_X = 362 (tyle Ci wyszło przecież?)
                  > a = 18
                  >
                  > x1=362-18=344
                  > x2=362+0+18+1=381
                  >
                  > x1*x2=131064
                  > L=131072
                  > L-x1*x2=8
                  >
                  > ok?

                  Tylko czesciowo, co prawda x1*x2 < L, ale L da sie rozlozyc zgodnie z warunkami
                  zadania na 2 i 2^16 tak, zeby nikogo nie wysylac do domu.

                  M.
                  • the_ladybird Re: Czesciowo OK ;-) 12.02.03, 10:00
                    marchewa4 napisał:

                    > Tylko czesciowo, co prawda x1*x2 < L, ale L da sie rozlozyc zgodnie z warunk
                    > ami
                    > zadania na 2 i 2^16 tak, zeby nikogo nie wysylac do domu.

                    Jasssne, &$#!

                    też mi to wczoraj wyszło :( że bez pętli się jednak nie obejdzie :(

                    Podsumuję - mam nadzieję, że już bez błędów:

                    L = liczba losowa z przedziału {2^16 + 1, 2^32}
                    SQ_X = L^(1/2) - zaokrąglone w dół
                    r = L - SQ_X^2
                    dx = r/sqL - zaokrąglone w dół
                    x1 = SQ_X
                    x2 = XQ_X + dx
                    R = L - x1*x2

                    Dopóki R różne od 0 i x2 <= 2^16

                    rozwiązujemy równanie:

                    a^2 + a*(x2 - x1 + 1) == x1*(x2 + 1) - L

                    a = (to każdy potrafi)

                    Bierzemy rozwiązanie większe od zera

                    x1 = x1 - a,
                    x2 = x2 + a + 1,
                    Rnew = L - x1*x2
                    Jeżeli Rnew < R to {R = Rnew, x1t = x1, x2t = x2}

                    koniec pętli.

                    Średnia z dziesięciu losowo wybranych liczb (z przedziału 2^16+1;2^32) to 527
                    kroków. Im większa liczba (a raczej im bliższa górnej granicy) tym szybciej się
                    to liczy.
                    • the_ladybird Re: Czesciowo OK ;-) 12.02.03, 10:03
                      the_ladybird napisała:

                      > Średnia z dziesięciu losowo wybranych liczb (z przedziału 2^16+1;2^32) to 527
                      > kroków. Im większa liczba (a raczej im bliższa górnej granicy) tym szybciej
                      > się to liczy.

                      a niech to!

                      nie 527 a 5270 kroków
    • marchewa4 Eratostenes do pomocy? 11.02.03, 14:10
      W poscie uzywam oznaczen the_ladybird (dzieki za uporzadkowanie).

      Pewnie kazde z Was zna prosty algorytm sita Eratostenesa. Moze daloby sie go
      zaprzac do pracy i u nas. Dosc pamieciozerny, ale moze da efekty.

      Zbudujmy tablice (tab), w ktorej indeksami beda kolejne liczby od SQ_X do L.
      Wypelniamy tablice zerami.

      01. dla kazdego Y = SQ_X do min(L, 2^16) w petli
      02. __ jezeli tab[Y] = 0 to
      03. _____ h = Y
      04. _____ dopoki h < L w petli
      05. ________ tab[h] = Y
      06. ________ h = h + Y
      07. _____ koniec petli
      08. _____ jezeli h = L to
      09. ________ mamy rozwiazanie (Y, L/Y)
      10. ________ SUKCES
      11. ______koniec jezeli
      12. __ koniec jezeli
      13. koniec petli
      14. L_OK = L
      15. dopoki tab[L_OK] = 0 w petli
      16. __ L_OK = L_OK - 1
      17. koniec petli
      18. rozwiazanie (tab[L_OK], L_OK/tab[L_OK])
      19. SUKCES

      Przyznaje, ze jest to wstepny pomysl i dokladnie sobie tego nie przemyslalem,
      ale wrzucam tu, bo moze ktos znajdzie czas i chec, zeby skrytykowac i wracam
      chwilowo do zarabiania na chleb ;-)

      Pozdrawiam

      M.
      • marchewa4 Re: Eratostenes do pomocy? 11.02.03, 14:17
        Mala poprawka jeszcze. Ta tablica nie musi byc tak duza. Wiemy przeciez, ze w
        ostatecznosci liczba SQ_X^2 spelnia nasze warunki. Wystarczy, ze ta tablica
        bedzie od SQ_X^2 + 1 do L i odpowiednio zmodyfikowany algorytm.

        M.
          • marchewa4 Re: Eratostenes do pomocy? 12.02.03, 08:51
            mesquaki napisała:

            > Ładne :). 2^32-1 mi się wysypało jako iloczyn 2^16-1 i 2^16+1 ;) a poważną
            > krytyką niech się poważni krytycy zajmą, mi tam się podoba.
            > m

            A niech to. Moze trzeba zaczac petle od SQ_X + 1, jesli L nie jest pelnym
            kwadratem. Dzis chyba nie znajde czasu, ale jutro potestuje sobie ten algorytm.

            Pozdrowienia dla wszystkich

            M.
            • marchewa4 Re: Eratostenes do pomocy? 12.02.03, 10:49
              Wlasnie mialem w firmie zebranie i moglem sobie spokojnie zagadke przemyslec ;-)

              Tablica tab jest indeksowana od SQ_X^2+1 do L (realizacje techniczna zostawiam
              na razie na boku, zeby nie zaciemniac algorytmu)

              Mala poprawka do algorytmu:
              00. L_MIN = SQ_X^2 + 1
              01. dla kazdego Y = SQ_X do 2^16 w petli
              02. __ h = Y
              03. __ dopoki h < L_MIN
              04. _____ h = h + Y
              05. __ koniec petli
              06. __ L_MAX = Y * 2^16
              07. __ dopoki h <= L_MAX w petli
              08. _____ tab[h] = Y
              09. _____ h = h + Y
              10. __ koniec petli
              11. __ jezeli h = L to
              12. _____ mamy rozwiazanie (Y, L/Y)
              13. _____ SUKCES
              14. ___koniec jezeli
              15. koniec petli
              16. L_OK = L
              17. dopoki tab[L_OK] = 0 w petli
              18. __ L_OK = L_OK - 1
              19. koniec petli
              20. rozwiazanie (tab[L_OK], L_OK/tab[L_OK])
              21. SUKCES

              Postaram sie pozniej przetestowac skutecznosc.

              M.
              • marchewa4 Re: Eratostenes do pomocy? 12.02.03, 12:45
                Tak to jest jak sie nie testuje, tylko wysyla ;-)
                Jeszcze cos poprawiam:

                Tablica tab jest indeksowana od SQ_X^2+1 do L (realizacje techniczna zostawiam
                na razie na boku, zeby nie zaciemniac algorytmu)

                00. L_MIN = SQ_X^2 + 1
                01. dla kazdego Y = SQ_X do 2^16 w petli
                02. __ h = Y
                03. __ dopoki h < L_MIN w petli
                04. _____ h = h + Y
                05. __ koniec petli
                06. __ L_MAX = Y * 2^16
                07. __ jezeli L_MAX == L to
                08. _____ mamy rozwiazanie (Y, 2^16)
                09. _____ SUKCES
                10. ___koniec jezeli
                11. __ dopoki h <= L_MAX w petli
                12. _____ tab[h] = Y
                13. _____ h = h + Y
                14. __ koniec petli
                15. koniec petli
                16. L_OK = L - 1
                17. dopoki L_OK >= L_MIN i tab[L_OK] = 0 w petli
                18. __ L_OK = L_OK - 1
                19. koniec petli
                20. jezeli L_OK >= L_MIN to
                20. __ rozwiazanie (tab[L_OK], L_OK/tab[L_OK])
                21. __ SUKCES
                22. w przeciwnym razie
                23. __ rozwiazanie (SQ_X, SQ_X)
                24. __ SUKCES
                25. koniec jezeli

                M.
                • marchewa4 Re: Eratostenes do pomocy? 12.02.03, 13:05
                  I znowu cos pochrzanilem.
                  Jeszcze raz poprawiam:

                  00. L_MIN = SQ_X^2 + 1
                  01. dla kazdego Y = SQ_X do 2^16 w petli
                  02. __ h = Y
                  03. __ dopoki h < L_MIN w petli
                  04. _____ h = h + Y
                  05. __ koniec petli
                  06. __ L_MAX = min(L, Y * 2^16)
                  07. __ dopoki h <= L_MAX w petli
                  08. _____ tab[h] = Y
                  09. _____ h = h + Y
                  10. __ koniec petli
                  11. __ h = h - Y
                  12. __ jezeli h == L to
                  13. _____ mamy rozwiazanie (Y, L/Y)
                  14. _____ SUKCES
                  15. ___koniec jezeli
                  16. koniec petli
                  17. L_OK = L - 1
                  18. dopoki L_OK >= L_MIN i tab[L_OK] = 0 w petli
                  19. __ L_OK = L_OK - 1
                  20. koniec petli
                  21. jezeli L_OK >= L_MIN to
                  22. __ rozwiazanie (tab[L_OK], L_OK/tab[L_OK])
                  23. __ SUKCES
                  24. w przeciwnym razie
                  25. __ rozwiazanie (SQ_X, SQ_X)
                  26. __ SUKCES
                  27. koniec jezeli

                  M.
    • kopperek no-no! 11.02.03, 21:44
      Witam

      Sorry, ale dziś nie miałem czasu się tu poudzielać,
      spróbuję sobie to w domu przeczytać i jutro się poczepiać:)

      pozdrawiam walczących heroicznie! - Kopperek
      • the_ladybird Re: no-no! 12.02.03, 13:37
        Algorytm ten jest błyskawiczny.
        Oparłam go o pomysł nr4. tzn, że tak naprawdę to badamy funkcję hiperboliczną.

        Kroków może i robi trochę więcej, ale każdy z nich jest mnóstwo razy szybszy:

        L = liczba żołnierzy (2^16, 2^32}
        SQ_X = Pierwiastek [L]

        y = SX_Q - zaokrąglone w dół
        x = L / y - zaokrąglone w dół
        R = L - x y - reszta

        Pętla:
        dopóki (y >= L/(2^16) AND r != 0) !bo po co ma liczyć, jak znajdzie r = 0
        y = y - 1,
        x = L / y - zaokrąglone w dół
        Rnew = L - x y,
        Jeżeli
        rnew < R, {r = rnew, yt = y, xt = x} - zapamiętujemy x,y,R
        koniec

        wypisujemy {x,y,R}
        • kopperek Re: no-no! 12.02.03, 15:59
          the_ladybird napisała:

          > Algorytm ten jest błyskawiczny.
          > Oparłam go o pomysł nr4. tzn, że tak naprawdę to badamy
          funkcję hiperboliczną.
          >
          > Kroków może i robi trochę więcej, ale każdy z nich jest
          mnóstwo razy szybszy:
          >
          > L = liczba żołnierzy (2^16, 2^32}
          > SQ_X = Pierwiastek [L]
          >
          > y = SX_Q - zaokrąglone w dół
          > x = L / y - zaokrąglone w dół
          > R = L - x y - reszta
          >
          > Pętla:
          > dopóki (y >= L/(2^16) AND r != 0) !bo po co ma liczyć,
          jak znajdzie r = 0
          > y = y - 1,
          > x = L / y - zaokrąglone w dół
          > Rnew = L - x y,
          > Jeżeli
          > rnew < R, {r = rnew, yt = y, xt = x} - zapamiętujemy
          x,y,R
          > koniec
          >
          > wypisujemy {x,y,R}


          Dzięki za streszczenie. Cóż, algorytm broni się sam,
          trudno się czepić... Mój sposób myślenia jest praktycznie
          taki sam. Wciąż pozostaje pytanie o optymalność tego
          algorytmu. Ale - szczerze mówiąc zaczynam sie
          zastanawiać, czy tu w ogóle może być mowa o jednym,
          najlepszym sposobie postępowania, czyli takim, który
          będzie optymalny dla każdej wartości L. Kto wie, czy
          koniec końców nie będzie trzeba sięgnąć po symulacje...:(((
          Podstawowa wątpliwość: czy wartość Rnew jako funkcja y ma
          charakter przypadkowy, czy można w tym znaleźć jakąś
          regułę? Podejrzewam, że są tacy matematycy, którzy
          potrafiliby na to pytanie odpowiedzieć "od ręki", i
          zapewne odpowiedź byłaby negatywna (nie ma reguły). Ale
          mogę się mylić oczywiście.
          Na pewno jeszcze będę kombinował, do czego i innych zachęcam.

          z pozdrowieniami - Kopperek
          • the_ladybird Re: no-no! 13.02.03, 08:51
            kopperek napisał:

            > Mój sposób myślenia jest praktycznie
            > taki sam. Wciąż pozostaje pytanie o optymalność tego
            > algorytmu.

            Mój taki nie całkiem przecież nowej generacji komputerek potrzebował średnio
            sekundę na obliczenia - a wcale to a wcale nie żałowałam mu innych zadań.
            Maksymalny czas, jaki dostałam to 2.2 sekundy.
            Przy poprzednim algorytmie trwało to nawet kilka minut.

            Wg mnie to jest tak:

            Jeśli masz do wyznaczenia jedną parę w jednym wywołaniu programu - algorytm
            jest jak najbardziej ok,

            Szybciej (ale tylko w przypadku, gdy masz kilka takich par do obliczenia, bo
            przecież całą tablicę trzeba wczytać do pamięci) byłoby odczytać z tablicy,
            takiej że:

            x(t) = jeden z dzielników, jeśli istnieje lub
            x(t) = 0, jeśli nie istnieje
            dla każdego t z przedziału (2^16;2^32)

            ale pod warunkiem, że niezmienne pozostaje ograniczenie (dzielnik <= 2 ^ 16).
            Bo jeśli zmienia się dzielnik, zmienia się tablica.... w górę jest łatwo -
            trzeba rozszerzyć tablicę po prostu, ale w dół - same kłopoty :(

            > Podstawowa wątpliwość: czy wartość Rnew jako funkcja y ma
            > charakter przypadkowy, czy można w tym znaleźć jakąś
            > regułę?

            yh, jakbym swoje myśli słyszała :)
            Sądzę, że jest przypadkowa - per analogiam do znanego i szeroko opisywanego
            przykładu chaosu deterministycznego (odwzorowanie Bernoulliego):

            x(n) = x(n-1)*2(modulo 1) - nie wiem, czy dobrze to zapisałam. Chodzi o to, że
            liczbę z przedziału (0,1) mnożymy przez 2 i jeśli jest mniejsza od 1 - zostaje,
            a jeśli jest większa to odejmujemy od niej jeden i w ten sposób tworzymy
            następny wyraz.

            > Podejrzewam, że są tacy matematycy, którzy
            > potrafiliby na to pytanie odpowiedzieć "od ręki", i
            > zapewne odpowiedź byłaby negatywna (nie ma reguły). Ale
            > mogę się mylić oczywiście.
            > Na pewno jeszcze będę kombinował, do czego i innych zachęcam.

            aha. dobrze wiedziałam, że robię błąd wchodząc tutaj :D

            pozdr.
            • kopperek Re: no-no! 13.02.03, 12:43
              witaj ladybird:)

              the_ladybird napisała:

              > Mój taki nie całkiem przecież nowej generacji
              komputerek potrzebował średnio
              > sekundę na obliczenia - a wcale to a wcale nie
              żałowałam mu innych zadań.
              > Maksymalny czas, jaki dostałam to 2.2 sekundy.
              > Przy poprzednim algorytmie trwało to nawet kilka minut.


              Rozumiem, że dla pojedynczego przypadku (konkretne L).
              Nawet wtedy - na pewno zdążą wysłać armię na czas:).


              >
              > Wg mnie to jest tak:
              >
              > Jeśli masz do wyznaczenia jedną parę w jednym wywołaniu
              programu - algorytm
              > jest jak najbardziej ok,
              >
              > Szybciej (ale tylko w przypadku, gdy masz kilka takich
              par do obliczenia, bo
              > przecież całą tablicę trzeba wczytać do pamięci) byłoby
              odczytać z tablicy,
              > takiej że:
              >
              > x(t) = jeden z dzielników, jeśli istnieje lub
              > x(t) = 0, jeśli nie istnieje
              > dla każdego t z przedziału (2^16;2^32)
              >
              > ale pod warunkiem, że niezmienne pozostaje ograniczenie
              (dzielnik <= 2 ^ 16)
              > .
              > Bo jeśli zmienia się dzielnik, zmienia się tablica....
              w górę jest łatwo -
              > trzeba rozszerzyć tablicę po prostu, ale w dół - same
              kłopoty :(


              Algorytm jest chyba taki jak powinien, o ile mamy rację w
              następnej kwestii:

              >
              > > Podstawowa wątpliwość: czy wartość Rnew jako funkcja y ma
              > > charakter przypadkowy, czy można w tym znaleźć jakąś
              > > regułę?
              >
              > yh, jakbym swoje myśli słyszała :)
              > Sądzę, że jest przypadkowa - per analogiam do znanego i
              szeroko opisywanego
              > przykładu chaosu deterministycznego (odwzorowanie
              Bernoulliego):
              >
              > x(n) = x(n-1)*2(modulo 1) - nie wiem, czy dobrze to
              zapisałam. Chodzi o to, że
              > liczbę z przedziału (0,1) mnożymy przez 2 i jeśli jest
              mniejsza od 1 - zostaje,
              >
              > a jeśli jest większa to odejmujemy od niej jeden i w
              ten sposób tworzymy
              > następny wyraz.


              Zgoda, to faktycznie dowodzi, że taki ciąg będzie
              wyglądał chaotycznie, co nie znaczy, że nie można znaleźć
              tu jakiejś reguły. Oczywiście - Twoje rozumowanie też
              jest jakąś regułą, ale pozwalającą obliiczyć bezpośrednio
              tylko jeden wyraz w danym momencie (kolejny), nie da sie
              stworzyć wzoru na n-ty wyraz. Zresztą wiesz co mam na
              myśli:).


              >
              > > Podejrzewam, że są tacy matematycy, którzy
              > > potrafiliby na to pytanie odpowiedzieć "od ręki", i
              > > zapewne odpowiedź byłaby negatywna (nie ma reguły). Ale
              > > mogę się mylić oczywiście.
              > > Na pewno jeszcze będę kombinował, do czego i innych
              zachęcam.
              >
              > aha. dobrze wiedziałam, że robię błąd wchodząc tutaj :D
              >
              > pozdr.

              No-no, tylko bez takich:))).

              pozdrawiam - Kopperek
              • the_ladybird Re: no-no! 13.02.03, 13:51
                kopperek napisał:
                > Zgoda, to faktycznie dowodzi, że taki ciąg będzie
                > wyglądał chaotycznie, co nie znaczy, że nie można znaleźć
                > tu jakiejś reguły.

                eno! Jak chaotyczne to chaotyczne (tylko czy na pewno chaotyczne?) - możliwość
                przewidzenia w chaosie? Tak, ale tylko na poziomie zespołów, nie pojedynczych
                trajektorii!
                No chyba że w mylnym tkwię błędzie :)

                > tylko jeden wyraz w danym momencie (kolejny), nie da sie
                > stworzyć wzoru na n-ty wyraz. Zresztą wiesz co mam na
                > myśli:).

                aha. rozwiązanie stricte analityczne. nie wyszło.
                a próbowałam, oj jak próbowałam.

                > > aha. dobrze wiedziałam, że robię błąd wchodząc tutaj :D
                > No-no, tylko bez takich:))).

                Jak bez takich, jak od trzech dni myślę o żołnierzach na wojnie, zamiast skupić
                się na zarabianiu na chleb (...z odrobiną dom perignon)?
                • kopperek Re: no-no! 13.02.03, 14:20
                  the_ladybird napisała:

                  > kopperek napisał:
                  > > Zgoda, to faktycznie dowodzi, że taki ciąg będzie
                  > > wyglądał chaotycznie, co nie znaczy, że nie można znaleźć
                  > > tu jakiejś reguły.
                  >
                  > eno! Jak chaotyczne to chaotyczne (tylko czy na pewno
                  chaotyczne?) - możliwość
                  > przewidzenia w chaosie? Tak, ale tylko na poziomie
                  zespołów, nie pojedynczych
                  > trajektorii!
                  > No chyba że w mylnym tkwię błędzie :)


                  To może jako mały przykładzik przytoczę tu przetwornik
                  analogowo-cyfrowy i zasadę jego działania. Powiedzmy, że
                  mamy daną funkcję sinusoidalną, o amplitudzie np.1000 i
                  okresie powiedzmy 53.7 Hz (celowo taka złożona liczba).
                  Co 0.001 sekundy pobieramy jej wartość i zaokroąglamy do
                  najbliższej liczby całkowitej (próbkowanie i
                  kwantowanie). Każdej tak otrzymanej próbce przypisujemy
                  liczbę będącą różnicą pomiędzy wartością dokładną, a tą
                  przybliżoną - czyli po prostu część ułamkową wartości tej
                  funkcji sinusoidalnej (błąd kwantyzacji). Jeśli
                  narysujemy teraz przebieg błędu kwantyzacji jako funkcję
                  czasu, otrzymamy coś bardzo przypominającego przebieg
                  przypadkowy, a jednak jest to funkcja w pełni
                  deterministyczna i co więcej - możemy od ręki policzyć
                  jej wartość dla dowolnej chwili t (czasu). Sprawa się
                  komplikuje, gdy amplituda jest mała, np równa 5, ale dla
                  dużych amplitud to naprawdę prawie szum. A jeśli jeszcze
                  zamiast jednego sinusa stworzymy funkcję wielu takich
                  składowych (np. kilkadziesiąt - czemu nie?), to tym
                  bardziej.
                  Ten przypadek jest oczywiście inny, nie twierdzę że
                  występuje tu pełna analogia. Po prostu gdzieś tam siedzi
                  we mnie diabełek i cały czas jątrzy - a może jednak, może
                  jednak...:)


                  Zresztą wiesz co mam na
                  > > myśli:).
                  >
                  > aha. rozwiązanie stricte analityczne. nie wyszło.
                  > a próbowałam, oj jak próbowałam.
                  >
                  > > > aha. dobrze wiedziałam, że robię błąd wchodząc tutaj :D
                  > > No-no, tylko bez takich:))).
                  >
                  > Jak bez takich, jak od trzech dni myślę o żołnierzach
                  na wojnie, zamiast skupić
                  >
                  > się na zarabianiu na chleb (...z odrobiną dom perignon)?


                  Hehe:))), a ja nawet wyrzutów sumienia mieć nie
                  zamierzam:PPP.

                  Kopperek_wrednie_uśmiechnięty:)
                  • andy._ Posumowanie? 13.02.03, 14:30
                    Wojenka powoli jakby wygasa. Przydałoby się jakieś podsumowanie
                    efektywności/optymalności proponowanych rozwiązań. W zasadzie pada na Kopperka,
                    który wojenkę rozpetał, ale zdaję sobie sprawę, że żeby zrobić to w miarę
                    porządnie trzeba sporego nakładu pracy. Mnie problem naprawdę zainteresował,
                    ale zagłebię sie w niego dopiero chyba w wakacje,
                    Pozdr. A.
                    • kopperek Re: Posumowanie? 13.02.03, 15:25
                      andy._ napisał:

                      > Wojenka powoli jakby wygasa. Przydałoby się jakieś
                      podsumowanie
                      > efektywności/optymalności proponowanych rozwiązań. W
                      zasadzie pada na Kopperka,
                      >
                      > który wojenkę rozpetał, ale zdaję sobie sprawę, że żeby
                      zrobić to w miarę
                      > porządnie trzeba sporego nakładu pracy. Mnie problem
                      naprawdę zainteresował,
                      > ale zagłebię sie w niego dopiero chyba w wakacje,
                      > Pozdr. A.


                      Wstyd się przyznać, ale póki co nie znalazłem nawet czasu
                      na porządne przemyślenie propozycji marchewy:(((. Myślę,
                      że na podsumowanie będzie jeszcze czas, może po
                      weekendzie, gdy trochę odetchnę czasowo, a przy okazji -
                      może jeszcze pojawi się jakaś idea. Postaram sie
                      wcześniej, ale nic na siłę.
                      Zupełnie natomiast nie wodzę powodu, dla którego kto inny
                      nie miałby dokonać takich porównań. Ja tu od początku
                      pisałem, że rozwiązania nie znam:).

                      pozdrawiam Kopperek

                      PS Andy - też czekam na wakacje. I trzymam za słowo;).
    • cardemon Re: wojenko, wojenko... 25.02.03, 03:26
      Witam serdecznie na tym wątku. W zasadzie nie zabierałbym tu głosu, gdybym nie
      został zaproszony i zachęcony przez Kopperka. Wątek obecnie urósł do sporych
      rozmiarów i - jak zdążyłem pobieżnie przejrzeć - wiele osób przedstawiło już
      swoje gotowe algorytmy rozwiązania.
      Zdaję sobie doskonale sprawę, że prochu nie wymyślę i jedyne, co mogę w chwili
      obecnej zaproponować to "przetłumaczenie" łamigłówki na język graficzny, co
      właśnie w pierwszej kolejności zrobiłem:

      Dla pewnej liczby N poszukiwane są dwie liczby x i y takie, że:

      1) N=x*y
      2) N,x,y są liczbami naturalnymi
      3) Dana jest pewna liczba naturalna Max taka, ze x i y < Max < N
      4) gdyby nie istniały zdefiniowane wyżej liczby x i y dla danej liczby N i Max,
      wtedy należy zmniejszyć zadaną liczbę N o jeden (N=N-1)i wrócić do punktu 1)

      Mamy więc N=x*y. Istnieje tu wyraźna zależność x od y i vice versa (lub vice
      Wersal :)). Przyjmijmy, ze y jest funkcją x. Mamy więc:

      y=N/x lub f(x)=N/x

      Wykresem takiej funkcji dla liczb rzeczywistych (ograniczmy sie dla dodatnich)
      jest hiperbola. Narysujmy więc dwie osie i hiperbolę między nimi. Oczywiscie
      tam gdzie jest 1 na osi iksów tam na osi igreków jest N, a tam gdzie na osi
      igreków 1 tam N na osi iksów. Na obu osiach, w tej samej odległości od początku
      układu współrzędnych, można nanieść liczbę Max. Prowadząc prostopadłe z obu osi
      od dwóch punktów Max otrzymamy w przecięciu z hiperbolą punkty A i B. Między
      punktami A i B znajduje się pewien wycinek hiperboli. I właśnie na tym wycinku
      mieszczą się punkty będące rozwiązaniem naszego problemu, o ile dadzą się one
      przedstawić za pomocą współrzędnych x i y będących liczbami naturalnymi.
      Wiadomo, że jeśli N jest liczba pierwszą, to takie dwie liczby x i y nie
      istnieją o ile Max nie jest równe 1. :)

      Taki jest mój początek. Teraz zacznie się głębsza analiza, ale juz widzę, że
      jest to ciężki orzech do zgryzienia i pewnie trzeba będzie sięgnąć do "sfer
      wyższych".
      Sorry, jeśli potórzyłem tu czyjeś myśli, analizy lub część rozwiązania, ale
      jeszcze nie przebrnąłem przez wszystkie posty.

      Pozdrowienia,
      CdM
      • kopperek Re: wojenko, wojenko... 26.02.03, 15:00
        cardemon napisał:

        > Dla pewnej liczby N poszukiwane są dwie liczby x i y
        takie, że:
        >
        > 1) N=x*y
        > 2) N,x,y są liczbami naturalnymi
        > 3) Dana jest pewna liczba naturalna Max taka, ze x i y
        < Max < N
        > 4) gdyby nie istniały zdefiniowane wyżej liczby x i y
        dla danej liczby N i Max,
        >
        > wtedy należy zmniejszyć zadaną liczbę N o jeden
        (N=N-1)i wrócić do punktu 1)


        Nie do konca rozumiem w tym momencie, co opisuje liczba
        Max. Ciekaw jestem rozwiniecia Twojego pomyslu!

        pozdrawiam Kopperek

      • kopperek Re: wojenko, wojenko... 26.02.03, 15:00
        cardemon napisał:

        > Dla pewnej liczby N poszukiwane są dwie liczby x i y
        takie, że:
        >
        > 1) N=x*y
        > 2) N,x,y są liczbami naturalnymi
        > 3) Dana jest pewna liczba naturalna Max taka, ze x i y
        < Max < N
        > 4) gdyby nie istniały zdefiniowane wyżej liczby x i y
        dla danej liczby N i Max,
        >
        > wtedy należy zmniejszyć zadaną liczbę N o jeden
        (N=N-1)i wrócić do punktu 1)


        Nie do konca rozumiem w tym momencie, co opisuje liczba
        Max. Ciekaw jestem rozwiniecia Twojego pomyslu!

        pozdrawiam Kopperek

        • cardemon Re: wojenko, wojenko... 27.02.03, 05:23
          kopperek napisał:

          > Nie do konca rozumiem w tym momencie, co opisuje liczba
          > Max. Ciekaw jestem rozwiniecia Twojego pomyslu!

          Mam juz całkiem skrystalizowane przemyślenia niniejszego problemu, ale nie
          wydaje mi się, jak już z resztą napisałem, bym wymyślił tu proch, bo przede mną
          zrobiła to juz, jak widzę, Ladybird (ale jeszcze nie przegryzłem się do końca!).

          Tym niemniej zanim coś zapodam na tym forum chciałbym wpierw zadać kilka
          zasadniczych pytań, ale najsamprzód kilka objaśnień: liczba Max jest to
          maksymalna ilość oddziałow = ilość hetmanów = 2^16 w Twojej pierwotnej wersji
          zagadki; N = łączna liczebność wojsk najchętniej równa całkowitej populacji; x
          i y poszukiwane mnożniki. Mamy więc piękną hiperbolę y=N/x z punktami A i B,
          gdzie A ma koordynaty (N/Max, Max), a B (Max, N/Max). Między punktami A i B na
          hiperboli znajdują sie punkty bedące rozwiązaniem problemu, o ile ich
          współrzędne są liczbami naturalnymi i o ile oczywiście N<Max^2, bo jeśli nie,
          to trzeba by zmniejszyć N, czyli odrzucić ileś tam wojaków... (trzymam się tej
          hiperboli, jak pijany ściany, bo uwielbiam graficzne odwzorowanie problemu :))

          A teraz zasadnicze pytania do problemu:

          1) Odnośnie liczby Max. Czy zawsze maxymalna liczba oddziałów będzie równa max
          liczbie hetmanów? Jeśli nie, to jak te liczby mają się wzajemnie kształtować?
          2) Czy łączna liczebność wojsk, a w zasadzie pierwotna populacja to liczba
          rzędu 10^7 czy może 10^1000000 lub 10^10^10? (to drastycznie zmienia sposób
          podejścia!)
          3) Co optymalizować? Czy to, żeby "odrzut" (czyli ta reszta żołnierzy, jaka
          pozostanie w domu) był jak najmniejszy, czy raczej chodzi o jak najkrótszy czas
          znalezienia obu mnożników x i y?
          4) Pragnę zauważyć również, że dla pewnych relatywnie małych liczb N i liczb
          Max spełniających zależność: Max~Sqr(N) (Max w przybliżeniu równe pierwiastek z
          N) odległość na hiperboli między punktami A i B jest stosunkowo mała, co
          oznacza, że niewiele jest tam do sprawdzenia punktów na warunek, czy mają
          współrzędne naturalne, czyli za pomocą programu komputerowego dałoby się to
          wtedy łatwo i szybko policzyć. Jak więc kształtuje się liczba Max w stosunku do
          N? Istnieje jakaś zależność?

          To chyba tyle pytań na dziś, choć wydaje mi się, ze miałem ich więcej. :(
          Oczywiście najistotniejsze są pytania 2) i 3).

          Pozdr.
          CdM
Inne wątki na temat:

Popularne wątki

Nie pamiętasz hasła

lub ?

 

Nie masz jeszcze konta? Zarejestruj się

Nakarm Pajacyka