Spirala algorytm

[AdirasOwns]

Witam, za pomocą jakiego wzoru mogę obliczyć liczbę znajdująca się w prawym dolnym rogu planszy o określonych wymiarach? Liczby w planszy układają się w spiralę, tzn. na środku jest jeden, nad nią dwójka, po prawo od niej trójka a pod trójką czwórka... Plansza posiada regularny kształt a liczna kratek z jakich składa się bok jest zawsze nieparzysta. Dla przykładku w planszy o boku 3 wynikiem będzie iczba 5.

Tutaj macie przykład:

 

 

 

 

[Jaca777]

Coś takiego udało mi się wykminić:

    public static int spiralCornerValue(int centerValue, int size){
        return centerValue + size * size * 4;
    }

[krulcelulozy]

 

Coś takiego udało mi się wykminić:

    public static int spiralCornerValue(int centerValue, int size){
        return centerValue + size * size * 4;
    }

no prawie, bo jakbys np. tu wziął sobię size jako 5 to by było 1 + 25*4 = 101.

size dla:

3x3 = 1,

5x5 = 2,

7x7 =3

czyli size ma być podzielone przez dwa i zaokrąglone do dołu (tak mi wychodzi z obliczeń)

 

@@

albo po prostu obliczyć wartość od środka do jakiejś krawędzi

[Jaca777]

@krulcelulozy

Nie rozumiesz tego... Przeanalizuj jeszcze raz ten algorytm. Wszystko dobrze działa.

Size jest liczony od środka do boku.

 

Albo nie rozumiesz o co facet pyta.

[krulcelulozy]

@krulcelulozy

Nie rozumiesz tego... Przeanalizuj jeszcze raz ten algorytm. Wszystko dobrze działa.

Size jest liczony od środka do boku.

 

Albo nie rozumiesz o co facet pyta.

 

 

planszy o określonych wymiarach

 

 

Dla przykładku w planszy o boku 3

 

autor wyraźnie napisał, że plansza(kwadrat) ma bok 3, a nie napisał że odległość od środka do krawędzi wynosi  1(no bo tyle wynosi), jednakże rozumiem o co ci chodzi

[Jaca777]

To trochę kiepskie rozwiązanie. Co mam zrobić w sytuacji gdy size = np 4? Nie ma takiej spirali.

Ale wystarczy dać coś takiego: size /= 2; Ale prawda, zapomniałem dopisać o tym.

[Sopelek997]

ciekawostka

http://danpearcymaths.wordpress.com/2012/09/30/infinity-programming-in-geogebra-and-failing-miserably/

 

i tak jak napisał @krulcelulozy ma być size/2

[krulcelulozy]

To trochę kiepskie rozwiązanie. Co mam zrobić w sytuacji gdy size = np 4? Nie ma takiej spirali.

Ale wystarczy dać coś takiego: size /= 2; Ale prawda, zapomniałem dopisać o tym.

dla autora to nie ma znaczenia

 

@@coś się zbugowało i nie moge nic z cytatem zrobić

@Jaca777 no to jak nigdy nie jest parzyste to nie rozumiem co napisałeś bo to trochę pytanie retoryczne

liczna kratek z jakich składa się bok jest zawsze nieparzysta

[Jaca777]

Ale nigdy nie jest parzyste.

 

@Sopelek997 W libach Scali jest taka kolekcja, nazywa się Stream. Ciekawe rzeczy można z tym robić.

 

@krulcelulozy Chodziło o to, że jakby było parzyste, to najlepszym rozwiązaniem jest wyrzucenie wyjątku, bo taka spirala nie istnieje. I dlatego też liczę od środka.

[AdirasOwns]

Liczba kratek boku zawsze jest nieparzysta. Podaję funkcji liczbę kratek w boku a ona wypluwa mi jaka cyfra znajduje się w prawym dolnym rogu.

[Jaca777]

Czyli kod wygląda tak:

    public static int spiralCornerValue(int centerValue, int size){
        size /= 2;
        return centerValue + size * size * 4;
    }

[Sopelek997]

może size-1 dla tego przypadku?

[krulcelulozy]

albo math.floor(size) ale to już mniej istotny wybór

[Jaca777]

@Sopelek997

Dla parzystego? Można by, ale przecież nie o to chodzi osobie wywołującej metodę. Chce ona otrzymać wynik ze spirali o parzystej długości boku. Czyli trzeba albo wyrzucić wyjątek, albo liczyć od środka.

 

@krulcelulozy - A na cóż Math.floor?

[krulcelulozy]

Dla parzystego? Można by, ale przecież nie o to chodzi osobie wywołującej metodę. Chce ona otrzymać wynik ze spirali o parzystej długości boku. Czyli trzeba albo wyrzucić wyjątek, albo liczyć od środka.

a gdzie jest środek parzystej spirali?

[Jaca777]

... Liczenie od środka wyklucza jej istnienie. Spirala o boku 1 - od środka 0, Spirala o boku 3 - od środka 1, itd.

Liczyć od środka i.e. argument określałby odległość od środka do boku.

 

No i kod jeśli chcesz bez center liczyć od 1:

    public static int spiralCornerValue(int size){
        size /= 2;
        return 1 + size*size*4;
    }

[AdirasOwns]

@Jaca777

Dzięki wielkie, właśnie o to mi chodziło.

[Jaca777]

Jeszcze Polish Civil wymyślił coś takiego: (kazał mi wkleić obrazek ;/)

 

Szybszy.

[Jaca777]

A po zastąpieniu dzielenia przesunięciem są sobie równe:

        return 1 + (size >> 1)*(size >> 1) * 4;

Mimo tego, że przy 2147483647 iteracjach poprzednie było 10 razy szybsze przed zamianą.

[Sopelek997]

 

return  (size-1)*(size-1)+1;

o to mi chodziło mówiąc 'size-1' i 'dla tego przypadku'

 

Dla parzystego? Można by, ale przecież nie o to chodzi osobie wywołującej metodę. Chce ona otrzymać wynik ze spirali o parzystej długości boku. Czyli trzeba albo wyrzucić wyjątek, albo liczyć od środka.
 

 
Dlatego napisałem 'dla tego przypadku'
 

nie ma co się przejmować takimi mikrooptymalizacjami. Jakby komuś było to potrzebne do bardzo dużej ilości testów to bardziej polecam zrobienie lookup table w tym przypadku.

[Vipper]

Zadanie na konkurs  

Mi zaliczyli:

#include <iostream>
#include <cstdlib>
using namespace std;
int n;
int64_t m;
int main()
{
    cin >> n;
    m = n-1;
    m = m*m;
    m = m +1;
    cout << m << endl;
    system("pause");
    return 0;
}