[tell_me_more]

#zagadkimatematyczne #zagadki #myslecmisieniechce #programowanie #wyzwanie

Mamy zeszyt w kratkę, w środkową kratkę (o współrzędnych 0,0) wpisujemy liczbę 0. Potem idziemy spiralnie - w kratkę o współrzędnych (0, -1) wpisujemy 1, w kratkę o współrzędnych ( 1, -1) wpisujemy 2, w kratkę o współrzędnych (1, 0) wpisujemy 3 i tak dalej.

Współrzędne kratek rosną w prawo (x) i do dołu (y).

Przykład dla pierwszych 9 liczb:

8 1 2

7 0 3

6 5 4

Trzeba wyprowadzić funkcję dwuargumentowa F(x,y) zwracającą dla kratki o współrzędnych (x,y) liczbę, którą trzeba do niej wpisać, oraz funkcję G(N) odwrotną do niej (zwracającą dla liczby N współrzędne kratki, w których wpiszemy tą liczbę).

Jak na razie wyprowadziłem x(N) i wiem, jak wyprowadzić y(N), tylko to dużo roboty :). Z tego będę miał G(N). Jak ktoś zrobi - stawiam piwo :) Potrzebne mi to do hobbystycznego projektu.

[noisy]

@tell_me_more: gotowego rozwiązania Ci nie dam, bo jeszcze nad nim pracuje, ale postaram się opisać jak na razie to rozwiązuje..

[noisy]

@tell_me_more: przede wszystkim dla lepszej wizualizacji dobrze na początek rozpisać sobie 4 kwadraty:

0

8 1 2

7 0 3

6 5 4

24 09 10 11 12

23 08 01 02 13

22 07 00 03 14

21 06 05 04 15

20 19 18 17 16

48 25 26 27 28 29 30

47 24 09 10 11 12 31

46 23 08 01 02 13 32

45 22

[noisy]

najpierw wyprowadzam sobie wzór na n-ty pierścień kwadraty, gdzie zerowy to

0

a pierwszy to:

8 1 2

7 3

6 5 4

drugi:

24 09 10 11 12

23 13

22 14

21 _ 15

20 19 18 17 16

[noisy]

w n-tym pierścieniu jest dokładnie: 4(2n-1) + 4 liczb

[tell_me_more]

@noisy: dzięki Ci :)

to ja podam x(i), które wyprowadziłem :)

pomocniczo Nx(i) = floor( (sqrt(5+4*i)-1)/2 )

x(i) = - floor( N(i)/2 ), gdy N(i) nieparzyste oraz i należy do < N(i)^2 - N(i); N(i^2) >

x(i) = floor( N(i)/2 ), gdy N(i) parzyste oraz i należy do < N(i)^2 - N(i); N(i^2) >

x(i) = - floor( N(i)/2 ), gdy N(i) nieparzyste oraz i należy do < N(i^2) +1; N(i)^2

[noisy]

@noisy: kwadrat n-tego stopnia ma, (2n+1)^2 liczb

[noisy]

@noisy: liczę sobie teraz maksimum po wartości bezwzględnej koordynatów, które zwraca mi n (stopień kwadratu)

n = max(abs(x), abs(y))

[noisy]

@noisy: teraz sprawdzam po której stronie od zera znajduje się nasz punkt, gdyż to determinuje jak należy liczyć wartość komórki..

[noisy]

@noisy:

48 25 26 27 28 29 30

47 24 09 10 11 12 31

46 23 08 01 02 13 32

45 22 07 00 03 14 33

44 21 06 05 04 15 34

43 20 19 18 17 16 35

42 41 40 39 38 37 36

x=3

y=1

n=3

liczba którą szukamy to 34

Tak naprawdę to na której ściance leży zależy od znaku przy współrzędnej, która

[tell_me_more]

@noisy: to z liczeniem n = max(abs(x), abs(y)) to w sumie klucz. Dzięki. Masz piwo jak będziesz w okolicy Lublina :)

[noisy]

@noisy:

gdy y ma maksymalną wartość bezwzględną, a y jest minusowe, to liczba ta znajduje się na północnej ściance.. (nazwijmy ją ścianą pierwszą)

gdy x ma maksymalną wartość bezwzględną, a x jest plusowe, to liczba ta znajduje się na wschodniej ściance.. (ściana nr 2, to nasz przypadek)

gdy y ma maksymalną wartość bezwzględną, a y jest plusowe, to liczba ta znajduje się na połódniowej ściance.. (ściana nr 3)

gdy x ma

[noisy]

@noisy: jesteśmy mniej więcej w połowie :)

[G.....n]

@tell_me_more: project Euler, poszukaj sobie, są dwa takie problemy. Jest jeden wzór nawet na wszystkie wierzchołki.

[noisy]

@Ginden: nie psuj zabawy.. ja sobie go wyprowadzam :P

[noisy]

@noisy: następną kwestią będzie wyliczenie, którą w kolejności największą liczbą na ściance jest nasza liczba..

34 jest piąta na drugiej ściance... a wyliczyć to można ze wzoru:

[G.....n]

Nie pomyśleliście, że najłatwiej wyznaczyć, gdzie jest najbliższy wierzchołek naszego kwadratowego pierścionka i sobie dodać/odjąć?

[noisy]

@Ginden: właśnie to próbuje zrobić.. tylko wiesz... ty to określiłeś słownie.. algorytmicznie jest trochę trudniej ;)

[tell_me_more]

@Ginden: nom, wierzchołki są zawsze dla abs(x)==abs(y)

[noisy]

@tell_me_more: tylko, że my potrzebujemy jego wartość..

[noisy]

@noisy: lewy górny to zawsze będzie (2n+1)^2-1