求数组螺旋填充中角点数值与索引的对应公式

Let's break down how to derive formulas for the "corner" values in a spiral-filled array, starting with square spirals (the most regular case) and extending to rectangular ones like your example.

First: Define the Spiral Structure #

For consistency, let's start with a corner-started clockwise square spiral (like your example's logic, starting at (0,0) with increasing values). Each "layer" (loop) of the spiral reduces the square's side length by 2 (we remove the outer perimeter to get the inner spiral).

Key Definitions for Square Spirals #

• Let n = side length of the full square (e.g., 5 for a 5x5 grid).
• Layer k: The k-th inner loop (starts at 0 for the outermost layer). The side length of layer k is s_k = n - 2k.
• Start value of layer k: S(k) = 4k(n - k) (cumulative sum of perimeters of all outer layers).

Mapping Corner Indices to Values #

Corners are the points where the spiral changes direction. For square spirals, each layer has 4 corners (start, right end, down end, left end). We can index these corners sequentially starting from 0:

For any corner index t:

1. Calculate the layer it belongs to: k = floor(t / 4)
2. Calculate the corner type (0 = start, 1 = right end, 2 = down end, 3 = left end): m = t % 4

Closed-Form Formulas for Square Spiral Corners #

Using the above, here's the value of each corner:

• Start of layer k (m=0): 4k(n - k)
• Right end of layer k (m=1): n*(4k + 1) - (4k² + 2k + 1)
• Down end of layer k (m=2): n*(4k + 2) - (4k² + 4k + 2)
• Left end of layer k (m=3): n*(4k + 3) - (4k² + 6k + 3)

Example Test (5x5 Square)

• Corner 0 (k=0, m=0): 4*0*(5-0) = 0 → correct (start at (0,0)).
• Corner 1 (k=0, m=1): 5*(0+1) - (0+0+1) = 4 → correct (right end at (0,4)).
• Corner 3 (k=0, m=3): 5*(0+3) - (0+0+3) =12 → correct (left end at (4,0)).
• Corner4 (k=1, m=0): 4*1*(5-1)=16 → correct (start of inner 3x3 layer at (1,0)).

Extending to Rectangular Spirals (Like Your 3x5 Example) #

Rectangular spirals are less regular, but the derivation process follows the same logic:

1. Define layers: For a rectangle of R rows and C columns, layer k has dimensions R_k = R-2k rows and C_k = C-2k columns.
2. Calculate start values: The start value of layer k is S(k) = S(k-1) + perimeter of layer k-1. The perimeter of a full rectangle layer is 2*(R_{k-1} + C_{k-1} -2); for single-row/column layers, it's just the number of elements in that row/column.
3. Identify corners: Track direction changes (right → down → left → up) and compute the value at each turn using cumulative steps from the layer's start.

For your 3x5 example:

• Layer 0 (outer) has perimeter 2*(3+5-2)=12 elements (0-11). Corners are (0,0)=0, (0,4)=4, (2,4)=11, (2,0)=10.
• Layer1 (inner) is a single row with 3 elements (12-14). Corners are (1,0)=11, (1,3)=14.

General Derivation Steps #

1. Model the traversal: Write out the sequence of directions (right, down, left, up) and how many steps are taken in each direction before turning.
2. List corner values: Note the value at each direction change (these are your corners).
3. Find patterns: Look for relationships between corner indices, layer numbers, and values. For squares, this leads to clean closed-forms; for rectangles, use conditional logic based on layer dimensions.
4. Validate: Test your formulas against known spiral values to ensure accuracy.

Once you have these corner formulas, you can implement your approach: for any cell coordinate, find the nearest previous corner value, then compute the target value by adding the steps from that corner to the cell.

内容的提问来源于stack exchange，提问作者Alex Nekrasov