2012-04-10 15 views
8

Cos'è un algoritmo per ottenere l'ennesimo elemento di una spirale piastrellata rettangolare?Trova la posizione nesimo elemento di una spirale piastrellata rettangolare?

Ecco n:

[ 20 ][ 21 ][ 22 ][ 23 ][ 24 ] 
[ 19 ][ 6 ][ 7 ][ 8 ][ 9 ] 
[ 18 ][ 5 ][ 0 ][ 1 ][ 10 ] 
[ 17 ][ 4 ][ 3 ][ 2 ][ 11 ] 
[ 16 ][ 15 ][ 14 ][ 13 ][ 12 ] 

e qui ci sono le coordinate corrispondenti per n:

[-2,2 ][-1,2 ][ 0,2 ][ 1,2 ][ 2,2 ] 
[-2,1 ][-1,1 ][ 0,1 ][ 1,1 ][ 2,1 ] 
[-2,0 ][-1,0 ][ 0,0 ][ 1,0 ][ 2,0 ] 
[-2,-1][-1,-1][ 0,-1][ 1,-1][ 2,-1] 
[-2,-2][-1,-2][ 0,-2][ 1,-2][ 2,-2] 

Se dato n, come calcolare le coordinate?

+0

Dall'origine, sono i primi due gradini verso destra e poi verso il basso? –

+0

Quindi se l'input è 0, la risposta è (0,0) e se l'input è 9, la risposta è (2,1)? Sto calcolando questo correttamente? –

+0

Sì, lo sei. gbianchi okay, risponderò io stesso quando il codice sarà pronto. – MaiaVictor

risposta

3

Ecco un codice in JavaScript. Calcola la posizione per la matrice 2D iniziando con il numero 1 in mezzo (0, 0)

13 12 11 10 25 
14 3 2 9 24 
15 4 1 8 23 
16 5 6 7 22 
17 18 19 20 21 

/** 
* Finds coordinates (position) of the number 
* 
* @param {Number} n - number to find position/coordinates for 
* @return {Number[]} - x and y coordinates of the number 
*/ 
function position(n) { 
    const k = Math.ceil((Math.sqrt(n) - 1)/2); 
    let t = 2 * k + 1; 
    let m = Math.pow(t, 2); 

    t -= 1; 

    if (n >= m - t) { 
     return [k - (m - n), -k]; 
    } 

    m -= t; 

    if (n >= m - t) { 
     return [-k, -k + (m - n)]; 
    } 

    m -= t; 

    if (n >= m - t) { 
     return [-k + (m - n), k]; 
    } 

    return [k, k - (m - n - t)]; 
} 
+1

Tempo costante, leggibile e piacevole. Dal 2012 grazie mille! – MaiaVictor

2

Per prima cosa, scopri su quale anello è inserito l'elemento desiderato (suggerimento: finché non arrivi all'anello esterno, la tua spirale è composta da quadrati annidati), quindi su quale lato (del 4) è acceso, allora tu sei appena partito con la sua posizione su quel lato.

1

Domande simili esistono già ... Vedere il mio non-looping version. Potrebbe essere necessario scambiare e/o annullare le coordinate X/Y e modificare lo 100 a 0 in base all'orientamento e all'origine desiderati.

C'è anche altro canonico looping versions.

+0

Quindi possiamo dire che questo è dup di nessuno di loro? si riferiscono tutti allo stesso punto. – gbianchi

+0

Probabilmente, ma è una domanda comune che non sembra facile da cercare, quindi più ampia è la rete, più è probabile che catturerà le ricerche future. Non è affatto male.- anche se, lo ammetto, non sembra così difficile da cercare. – Kaganar

1

Come nessuno ha risposto, c'è una soluzione:

def square_spiral(total_steps): 
    position = (0,0) 
    direction = (1,0) 
    turn_steps = [floor(((x+2)**2)/4) for x in range(n+2)] 
    for step in range(total_steps): 
     if (step in turn_steps): 
      direction = (-direction[1],direction[0]) 
     position = tuple(a+b for a,b in zip(position,direction)) 
    return position 

Questo simula una passeggiata attraverso il percorso desiderato. Si inizia dalla posizione (0,0), si cammina 1 gradino verso destra, 1 passo verso il basso, 3 passi verso sinistra, 3 gradini verso l'alto e così via, seguendo la spirale. Per codificare questo, notiamo che stiamo cambiando la nostra direzione sui passi dei numeri 1, 2, 4, 6, 9, 12, 16, 20 e così via. https://oeis.org/ rivela che questa è la sequenza di numeri interi da un quarto di quadrato. Quindi tutto ciò di cui abbiamo bisogno è un ciclo in cui ogni iterazione simula un passo, aggiungendo la direzione alla posizione e ruotandola di 90 ° quando il conteggio dei passi fa parte della sequenza.

1

Ecco la mia soluzione in JavaScript utilizzando somma inverso di 8 e il bordo di numerazione

Complessità: anello O (1) senza iterazione

function spiral(n) { 
    // given n an index in the squared spiral 
    // p the sum of point in inner square 
    // a the position on the current square 
    // n = p + a 

    var r = Math.floor((Math.sqrt(n + 1) - 1)/2) + 1; 

    // compute radius : inverse arithmetic sum of 8+16+24+...= 
    var p = (8 * r * (r - 1))/2; 
    // compute total point on radius -1 : arithmetic sum of 8+16+24+... 

    en = r * 2; 
    // points by edge 

    var a = (1 + n - p) % (r * 8); 
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r) 
    // so square can connect 

    var pos = [0, 0]; 
    switch (Math.floor(a/(r * 2))) { 
     // find the face : 0 top, 1 right, 2, bottom, 3 left 
     case 0: 
      { 
       pos[0] = a - r; 
       pos[1] = -r; 
      } 
      break; 
     case 1: 
      { 
       pos[0] = r; 
       pos[1] = (a % en) - r; 

      } 
      break; 
     case 2: 
      { 
       pos[0] = r - (a %en); 
       pos[1] = r; 
      } 
      break; 
     case 3: 
      { 
       pos[0] = -r; 
       pos[1] = r - (a % en); 
      } 
      break; 
    } 
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, " --> ", pos); 
    return pos; 
} 

Demo: Fiddle

+0

Buon lavoro. Appena in tempo! – MaiaVictor

12

Ecco una risposta breve e dolce usando solo la matematica semplice in pseudocodice. Nessun condizionale e nessuna iterazione. Dato tileNum per il numero di piastrelle:

intRoot=int(sqrt(tileNum)); 

x=(round(intRoot/2)*(-1^(intRoot+1)))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)-abs((intRoot*(intRoot+1))-tileNum))/2); 

y=(round(intRoot/2)*(-1^intRoot))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)+abs((intRoot*(intRoot+1))-tileNum))/2); 

Here's a fiddle per vederlo in azione.

+3

Come hai fatto? – MaiaVictor

+1

Bello. Come @Viclib, mi piacerebbe anche vedere una spiegazione. –

+0

Dove guardi le dimensioni della matrice? –

Problemi correlati