Tìm phần tử vị trí thứ n của hình xoắn ốc lát hình chữ nhật?

Question

Thuật toán để lấy phần tử thứ n của hình xoắn ốc lát hình chữ nhật là gì?

Đây là 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 ] 

và đây là tọa độ tương ứng cho 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] 

Nếu cho n, làm thế nào để tính toán tọa độ?

Answer 1

Đây là mã trong JavaScript. Nó tính toán vị trí cho ma trận 2D bắt đầu bằng số 1 ở giữa (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)]; 
} 

Answer 2

Đầu tiên, tìm vòng mà phần tử mong muốn của bạn nằm trong (gợi ý: cho đến khi bạn đến vòng ngoài, hình xoắn ốc của bạn được tạo thành từ ô vuông lồng nhau), sau đó bên nào (của 4) nó đang bật, sau đó bạn chỉ còn lại với vị trí của nó ở bên đó.

Answer 3

Câu hỏi tương tự đã tồn tại ... Xem non-looping version của tôi. Bạn có thể cần phải hoán đổi và/hoặc phủ nhận tọa độ X/Y và thay đổi các số 100 thành 0 tùy thuộc vào định hướng và nguồn gốc bạn muốn.

Còn kinh điển hơn looping versions.

Answer 4

Như không ai trả lời, có một giải pháp:

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 

này mô phỏng một đi bộ qua con đường mong muốn. Bạn bắt đầu ở vị trí (0,0), đi bộ 1 bước sang phải, 1 bước xuống, 3 bước bên trái, 3 bước lên, v.v., theo đường xoắn ốc. Để viết mã này, hãy lưu ý rằng chúng tôi đang thay đổi hướng của chúng tôi trên các bước số 1, 2, 4, 6, 9, 12, 16, 20 và cứ tiếp tục như vậy. https://oeis.org/ cho biết đây là chuỗi số nguyên dương. Vì vậy, tất cả chúng ta cần là một vòng lặp mà mỗi lần lặp mô phỏng một bước, thêm hướng đến vị trí và biến nó 90º khi đếm bước là một phần của chuỗi.

Answer 5

Đây là giải pháp của tôi trong javascript sử dụng tổng nghịch đảo của 8 và cạnh đánh số

phức tạp: vòng lặp O (1) không lặp

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

Answer 6

Dưới đây là một câu trả lời ngắn gọn và ngọt ngào chỉ sử dụng toán học đơn giản trong mã giả. Không có điều kiện và không lặp lại. Với tileNum cho số gạch:

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 để xem nó trong hành động.