5

Задача на собеседовании была:
Нужно написать функцию, которая создаст двумерный массив 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
6
  • 5
    Я голосую за закрытие этого вопроса как не соответствующего теме, потому что это решение задачи за автора. 12 сен 2015 в 22:13
  • 12
  • 2
    Коллеги, это вопрос точно не надо закрывать.
    – avp
    13 сен 2015 в 10:50
  • 4
    Извините за пинг-понг, но это классический случай работы за автора. В вопросе отсутствует даже намёк на минимальное усилие автора в том, чтобы разобраться в проблеме.
    – VladD
    13 сен 2015 в 12:47
  • 5
    Я голосую за закрытие этого вопроса как не соответствующего теме, потому что это решение задачи за автора
    – user177221
    2 окт 2015 в 10:33

3 ответа 3

7

В первую очередь имеет смысл посмотреть красивые решения которые предложил @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;
}
1
  • 3
    Плюс за юнит-тесты )
    – Nick Volynkin
    13 сен 2015 в 14:20
3

Что то вы все какие-то длинные. Да и комментарии явно не по делу. Рекурсия друзья, просто рекурсия.

$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
  • 1
    Ценность вашего решения нулевая, так как любой может скопировать код с сайта, ссылку на который вы сами же дали. Операцией "copy and paste" владеют многие. Более того, это выглядет просто некрасиво. Интерес может лишь представлять собственное оригинальное решение. 13 сен 2015 в 13:57
  • 7
    Интерес представляет работающее и эффективное решение.
    – Nick Volynkin
    13 сен 2015 в 14:12
-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
Для продолжения нажмите любую клавишу . . .
1

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.