[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

[noisy]

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

0

a pierwszy to:

8

[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

[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

[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

[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