wojenko, wojenko...

[kopperek]

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

[cardemon]

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]

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]

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]

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._]

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]

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]

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]

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]

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._]

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]

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.... ;-)))

dobre pytanie

[kopperek]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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._]

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]

błąd:

> delta_X = Floor[ R / SQ_X^2 ]

delta_X = Floor[ R / SQ_X ] oczywiście

[the_ladybird]

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._]

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._]

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]

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 :)

Do the_ladybird - pytanie

[marchewa4]

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]

> 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]

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]

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?

[the_ladybird]

aaaaa, już chyba widzę:

x1 = SQ_X - a
x2 = SQ_X +delta_X + a + 1

[the_ladybird]

A Ty używałeś SX_X + 1 zamiast SQ_X

Czesciowo OK ;-)

[marchewa4]

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]

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]

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

Eratostenes do pomocy?

[marchewa4]

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]

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.

[mesquaki]

Ł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

[marchewa4]

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]

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.

[the_ladybird]

W jakim języku programujesz? nic a nic nie umiem się połapać w Twoim
algorytmie :(

[marchewa4]

the_ladybird napisała:

> W jakim języku programujesz? nic a nic nie umiem się połapać w Twoim
> algorytmie :(

Troche tych jezykow by sie znalazlo. Ostatnio najchetniej w C. A ten algorytm
to mial byc w takim uniwersalnym jezyku wykladowym :-(

M.

PS. To co, podrzucic kod w C?

[the_ladybird]

marchewa4 napisał:

> Troche tych jezykow by sie znalazlo. Ostatnio najchetniej w C. A ten algorytm
> to mial byc w takim uniwersalnym jezyku wykladowym :-(

widać, jaki ze mnie pojętny uczeń ;)

> PS. To co, podrzucic kod w C?

e-e. może jeszcze nie. po prostu chciałam się zorientować, na czym polega sito
Eratostenesa - myślałam, że uda mi się z kodu

Sito Eratostenesa

[marchewa4]

www.republika.pl/dyniax/liczby/sito.htm
www.znak.com.pl/doxiadis/sito1.html
M.

[the_ladybird]

dziękuję :)
spodobało mi się.

Do the_ladybird

[marchewa4]

Jesli bedziesz miala chwilke, zajrzyj do swojej skrzynki pocztowej.

Pozdrowienia

M.

[the_ladybird]

odpisuję

[marchewa4]

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]

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.

no-no!

[kopperek]

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]

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]

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]

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]

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]

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]

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:)

Posumowanie?

[andy._]

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]

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]

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

[cardemon]

cardemon napisał:

> 3) Dana jest pewna liczba naturalna Max taka, ze x i y < Max < N

Przepraszam, drobny niuans, tu powinno być oczywiscie: x,y =< Max < N

[kopperek]

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]

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]

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