предполагая, что у меня $rows = 4 и $cols = 4; , Как создать массив с 16 элементами в спиральном порядке, например:
1, 2, 3, 4, 12,13,14,5, 11,16,15,6, 10,9, 8, 7,
Мое решение довольно многословное, потому что вы намерены изучить его и узнать, как он работает.
<?php /** * Creates a 2D array with the given dimensions, * whose elements are numbers in increasing order * rendered in a 'spiral' pattern. */ function createSpiral($w, $h) { if ($w <= 0 || $h <= 0) return FALSE; $ar = Array(); $used = Array(); // Establish grid for ($j = 0; $j < $h; $j++) { $ar[$j] = Array(); for ($i = 0; $i < $w; $i++) $ar[$j][$i] = '-'; } // Establish 'used' grid that's one bigger in each dimension for ($j = -1; $j <= $h; $j++) { $used[$j] = Array(); for ($i = -1; $i <= $w; $i++) { if ($i == -1 || $i == $w || $j == -1 || $j == $h) $used[$j][$i] = true; else $used[$j][$i] = false; } } // Fill grid with spiral $n = 0; $i = 0; $j = 0; $direction = 0; // 0 - left, 1 - down, 2 - right, 3 - up while (true) { $ar[$j][$i] = $n++; $used[$j][$i] = true; // Advance switch ($direction) { case 0: $i++; // go right if ($used[$j][$i]) { // got to RHS $i--; $j++; // go back left, then down $direction = 1; } break; case 1: $j++; // go down if ($used[$j][$i]) { // got to bottom $j--; $i--; // go back up, then left $direction = 2; } break; case 2: $i--; // go left if ($used[$j][$i]) { // got to LHS $i++; $j--; // go back left, then up $direction = 3; } break; case 3: $j--; // go up if ($used[$j][$i]) { // got to top $j++; $i++; // go back down, then right $direction = 0; } break; } // if the new position is in use, we're done! if ($used[$j][$i]) return $ar; } } /** * Assumes the input is a 2D array. */ function print2DGrid($array) { foreach ($array as $row) { foreach ($row as $col) { print sprintf("% 2d ", $col); } print "\n"; } } $width = 12; $height = 8; print2DGrid(createSpiral($width, $height)); ?>
Здесь он находится в действии, давая следующий результат:
0 1 2 3 4 5 6 7 8 9 10 11 35 36 37 38 39 40 41 42 43 44 45 12 34 63 64 65 66 67 68 69 70 71 46 13 33 62 83 84 85 86 87 88 89 72 47 14 32 61 82 95 94 93 92 91 90 73 48 15 31 60 81 80 79 78 77 76 75 74 49 16 30 59 58 57 56 55 54 53 52 51 50 17 29 28 27 26 25 24 23 22 21 20 19 18
Надеюсь это поможет.
Используйте векторные и логические значения. Итерацию по оси X начинать до тех пор, пока вы не достигнете конца строки. Установите значение true для каждой позиции при ее перемещении. Каждый раз, когда вы достигаете границы или логически верно, повернуть направо.
Таким образом, в первой строке ваш «вектор» изменит приращение X на ноль и приращение Y на 1. Затем вы проверите значение приращения на каждом шагу и разместите 4 сценария.
Это первый способ, о котором я думал.
Второй способ не будет использовать логические значения, но вместо этого просто будет отслеживать, сколько столбцов или строк осталось перед курсором на его пути, уменьшая X или Y, оставшиеся на каждом повороте. Остальная логика останется прежней.
Когда вы достигнете центра, вы попадете в петлю, где больше невозможных итераций. Вы можете поймать это, проверив количество возможностей вокруг квадрата или просто отсчитывая от N числа полных квадратов от того места, где вы начали, и остановитесь, когда число достигнет нуля.
Вы можете использовать вышеуказанный метод для квадрата любого размера.
Алгоритм не очень далек. Вам нужно перебирать от 1 до $rows*$cols . Во время итерации вам нужно вычислить положение текущего числа в матрице ($x,$y) . Первое будет, конечно, в (1,1) . Следующий будет ($x+1,$y) потому что вы направляетесь на восток. Таким образом, положение каждого числа основывается на положении предыдущего и на правильном направлении.
Сложная часть алгоритма заключается в вычислении направления. Но если вы посмотрите на это, вы увидите, что направление меняется по часовой стрелке каждый раз, когда вы сталкиваетесь с используемой ячейкой, или вы выходите за пределы.
В общем, это будет ~ 30 строк кода PHP.
Надеюсь, это поможет.
В PHP-гольф есть аналогичная задача: http://www.phpgolf.org/challenge/Spiral . Кто-то решил его всего за 130 символов!