#php #массивы #алгоритм
Закрыт. Этот вопрос не по теме. Ответы на него в данный
момент не принимаются.
Хотите улучшить этот вопрос? Update the question so it's
on-topic for Stack Overflow на русском.
Закрыт 4 года назад.
Задача на собеседовании была:
Нужно написать функцию, которая создаст двумерный массив NxN и заполнит его цифрами
1,2,..., NхN по кругу.
Для N = 3 должна получиться матрица:
1 2 3
8 9 4
7 6 5
Для N = 4 должна получиться матрица:
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
Ответы
Ответ 1
Что то вы все какие-то длинные. Да и комментарии явно не по делу. Рекурсия друзья, просто рекурсия. $w=5; $h=5; //Сюда размер матрицы function s($w,$h,$x,$y){return $y ? $w + s($h - 1, $w, $y - 1, $w - $x - 1) : $x;} for ($i = 0; $i < $h; $i++) { for ($j = 0; $j < $w; $j++) printf("%4d",s($w, $h, $j, $i)); echo "\n"; }Ответ 2
В первую очередь имеет смысл посмотреть красивые решения которые предложил @igumnov. Мне интересно было решить задачу без подсказок и здесь я просто оставлю своё решение. Идея состояла в том чтобы изменять переменные $destinationVerticalLevel и $destinationHorizontalLevel в зависимости от текущего направления. Если нарисовать на бумажке варианты то можно найти закономерность: через каждые две смены направления количество элементов которые изменятся в данном направлении уменьшаются на 1. За исключением первого направления, где первый элемент ещё пустой. Тест: public function testCircleArray() { $array = $this->createArray(2); expect('[0][1] array element should be correct', $array[0][1])->equals(1); expect('[0][2] array element should be correct', $array[0][2])->equals(2); expect('[1][2] array element should be correct', $array[1][2])->equals(3); expect('[1][1] array element should be correct', $array[1][1])->equals(4); $array = $this->createArray(3); expect('[0][1] array element should be correct', $array[0][1])->equals(1); expect('[0][2] array element should be correct', $array[0][2])->equals(2); expect('[0][3] array element should be correct', $array[0][3])->equals(3); expect('[1][3] array element should be correct', $array[1][3])->equals(4); expect('[2][3] array element should be correct', $array[2][3])->equals(5); expect('[2][2] array element should be correct', $array[2][2])->equals(6); expect('[2][1] array element should be correct', $array[2][1])->equals(7); expect('[1][1] array element should be correct', $array[1][1])->equals(8); expect('[1][2] array element should be correct', $array[1][2])->equals(9); } Код (жесть без рефакторинга): /** * @param int $dimension * * @return array */ public function createArray($dimension) { if ($dimension < 2) { throw new InvalidParamException('Dimension should be more or equal two'); } $finalArray = []; $destinations = [ 'right' => 'current', 'bottom' => null, 'left' => null, 'top' => null ]; $destinationVerticalLevel = 0; $destinationHorizontalLevel = 0; $destinationHasBeenChanged = false; $destinationSteps = $dimension; $destinationStepsNotChangeCount = 0; $currentLevel = 0; $maxCycleCount = $dimension * $dimension; for ($cycleCount = 1; $cycleCount <= $maxCycleCount; $cycleCount++) { foreach ($destinations as $destinationName => $destination) { if ($destination == 'current') { $currentDestination = $destinationName; } } if ($currentDestination == 'right') { $destinationHorizontalLevel = $destinationHorizontalLevel + 1; $currentLevel++; } elseif ($currentDestination == 'bottom') { $destinationVerticalLevel = $destinationVerticalLevel + 1; $currentLevel++; } elseif ($currentDestination == 'left') { $destinationHorizontalLevel = $destinationHorizontalLevel - 1; $currentLevel++; } elseif ($currentDestination == 'top') { $destinationVerticalLevel = $destinationVerticalLevel - 1; $currentLevel++; }; $finalArray[$destinationVerticalLevel][$destinationHorizontalLevel] = $cycleCount; /** * Если конец - меняем направление */ if (($currentLevel == $destinationSteps) || (($currentLevel == $destinationSteps + 1) && !$destinationHasBeenChanged)) { $currentLevel = 0; $destinationStepsNotChangeCount++; if ((!$destinationHasBeenChanged) || ($destinationStepsNotChangeCount == 2)) { $destinationSteps = $destinationSteps - 1; } if (!$destinationHasBeenChanged) { $destinationStepsNotChangeCount = 0; } $destinationHasBeenChanged = true; /** * Устанавливаем следующее направление */ { foreach ($destinations as $destinationName => $destination) { if ($destination == 'current') { $destinations[$destinationName] = null; $nextDestination = each($destinations)['key']; if ($nextDestination) { $destinations[$nextDestination] = 'current'; } else { $destinations['right'] = 'current'; } break; } } } } } return $finalArray; }Ответ 3
Обычно решение любой задачи начинается с подхода к ее решению "в лоб", то есть с прямолинейного подхода. Именно так лично я ее и сделал. Очевидно, что, во-первых, способов решения задачи может быть много, и самые оптимальные требуют серьезной траты времени и изучения вопроса, и, во-вторых, мое решение может быть далеко от оптимального и самого изящного (на самом деле это не так, и решение достаточно эффективное, а самое главное ясное и не использует рекурсии, что может привести к исчерпанию стека). Но тем не менее оно выполняет поставленную задачу. Так как я не имел дело с PHP, то я написал демонстрационную программу на C# просто потому, что у меня был открыт уже проект на C#.:) Вот сама программа using System; class Spiral { static void DisplayArray(int[,] a) { for (int i = 0; i < a.GetLength(0); i++) { for (int j = 0; j < a.GetLength(1); j++) Console.Write("{0,3} ", a[i, j]); Console.WriteLine(); } } static void Main(string[] args) { while (true) { Console.Write("Enter a non-negative number (0 - exit): "); int n; if (!Int32.TryParse(Console.ReadLine(), out n) || n <= 0) break; Console.WriteLine(); int[,] a = new int[n, n]; int i = 0, j = 0; int value = 1; while (n != 0) { int k = 0; do { a[i, j++] = value++; } while (++k < n - 1); for (k = 0; k < n - 1; k++) a[i++, j] = value++; for (k = 0; k < n - 1; k++) a[i, j--] = value++; for (k = 0; k < n - 1; k++) a[i--, j] = value++; ++i; ++j; n = n < 2 ? 0 : n - 2; } DisplayArray(a); Console.WriteLine(); } } } Вывод программы может выглядеть следующим образом: Enter a non-negative number (0 - exit): 10 1 2 3 4 5 6 7 8 9 10 36 37 38 39 40 41 42 43 44 11 35 64 65 66 67 68 69 70 45 12 34 63 84 85 86 87 88 71 46 13 33 62 83 96 97 98 89 72 47 14 32 61 82 95 100 99 90 73 48 15 31 60 81 94 93 92 91 74 49 16 30 59 80 79 78 77 76 75 50 17 29 58 57 56 55 54 53 52 51 18 28 27 26 25 24 23 22 21 20 19 Enter a non-negative number (0 - exit): 9 1 2 3 4 5 6 7 8 9 32 33 34 35 36 37 38 39 10 31 56 57 58 59 60 61 40 11 30 55 72 73 74 75 62 41 12 29 54 71 80 81 76 63 42 13 28 53 70 79 78 77 64 43 14 27 52 69 68 67 66 65 44 15 26 51 50 49 48 47 46 45 16 25 24 23 22 21 20 19 18 17 Enter a non-negative number (0 - exit): 8 1 2 3 4 5 6 7 8 28 29 30 31 32 33 34 9 27 48 49 50 51 52 35 10 26 47 60 61 62 53 36 11 25 46 59 64 63 54 37 12 24 45 58 57 56 55 38 13 23 44 43 42 41 40 39 14 22 21 20 19 18 17 16 15 Enter a non-negative number (0 - exit): 7 1 2 3 4 5 6 7 24 25 26 27 28 29 8 23 40 41 42 43 30 9 22 39 48 49 44 31 10 21 38 47 46 45 32 11 20 37 36 35 34 33 12 19 18 17 16 15 14 13 Enter a non-negative number (0 - exit): 6 1 2 3 4 5 6 20 21 22 23 24 7 19 32 33 34 25 8 18 31 36 35 26 9 17 30 29 28 27 10 16 15 14 13 12 11 Enter a non-negative number (0 - exit): 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 Enter a non-negative number (0 - exit): 4 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 Enter a non-negative number (0 - exit): 3 1 2 3 8 9 4 7 6 5 Enter a non-negative number (0 - exit): 2 1 2 4 3 Enter a non-negative number (0 - exit): 1 1 Enter a non-negative number (0 - exit): 0 Для продолжения нажмите любую клавишу . . .
Комментариев нет:
Отправить комментарий