3

Помогите как заполнить матрицу 3х3 такими же числами в таком же порядке. Умею заполнять двумерный массив, но вот такие правила заполнения не имею описывать.

Картинка в качестве примера:

матрица 3х3

Вот так заполняю и вывожу обычно, как это можно исправить?

int[] number = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        int[,] matrix = new int[3, 3];
        int index = 0;
        for (int i = 0; i < matrix.GetLength(0); i++)
            for (int j = 0; j < matrix.GetLength(1); j++)
            {
                matrix[i, j] = number[index];  
                    index++;                                       
            }

        for (int i = 0; i < matrix.GetLength(0); i++)
            for (int j = 0; j < matrix.GetLength(1); j++)
                if (j == matrix.GetLength(1) - 1)
                    Console.Write(matrix[i, j].ToString() + "\r\n");
                else Console.Write( matrix[i, j].ToString() + "\t");
2
  • Уточните вопрос: проблема составить алгоритм заполнения или запрограммировать его? 26 мар 2018 в 15:16
  • 2
    @MikhailGrebenev какая разница, это ж практически одно и тоже
    – tym32167
    26 мар 2018 в 15:19

5 ответов 5

4

Например, так:

const int max = 3;
int[,] matrix = new int[max, max];
int curr = 1;
for (int diff = 1 - max; diff <= max - 1; diff++)
{
    for (int i = 0; i < max; i++)
    {
        int j = i - diff;
        if (j < 0 || j >= max)
            continue;
        matrix[i, j] = curr++;
    }
}

Проверяем:

for (int i = 0; i < max; i++)
{
    for (int j = 0; j < max; j++)
        Console.Write(matrix[i, j] + "  ");
    Console.WriteLine();
}

Результат:

4  2  1
7  5  3
9  8  6

Пояснение: У клеток каждой диагонали разность координат y и x постоянна. Минимальная разность для «самой верхней» диагонали, в ней лишь клетка (max - 1, 0), разность равна 1 - max. Минимальная разность для «самой нижней» диагонали, в которой клетка (0, max - 1) равна, разумеется, max - 1. Внешний цикл по этим самым диагоналям. Одна разность — одна диагональ.

Затем, в каждой диагонали проводим цикл по x-координате (в коде обозначена как i). Она может быть от 0 до max - 1. Но например для первой диагонали не все x возможны, т. к. в ней только один элемент. Поэтому мы действуем так: вычисляем x, имея разность y - x == diff, вычисляем y (в коде j). Проверяем, чтобы y опадало в промежуток от 0 до max - 1.

В каждую найденную клетку записываем следующее число. Текущее число хранится, понятно, в переменной curr, и увеличивается на единицу после каждой записи в матрицу.

8
  • Чуть чуть опередили :)
    – tym32167
    26 мар 2018 в 15:26
  • @tym32167: Код по сути тот же, да?
    – VladD
    26 мар 2018 в 15:27
  • @tym32167: meta.stackexchange.com/q/18014/154101
    – VladD
    26 мар 2018 в 15:28
  • :) ну идея точно та же
    – tym32167
    26 мар 2018 в 15:29
  • @tym32167: У вас diff в другую сторону, а так идентично. Great minds think alike :)
    – VladD
    26 мар 2018 в 15:33
4

Как вариант

var matr = new int[3,3];    
var cnt = 0;
for(var y=2; y>=-2; y--)
    for(var x=0; x<3; x++)          
    if((y+x) >= 0 && (y+x)<3)
        matr[x, y+x] = ++cnt;

проверка

for (var i = 0; i < 3; i++)
{
    for (var j = 0; j < 3; j++)
        Console.Write($"{matr[i, j]} ");
    Console.WriteLine();
}   

Вывод

4 2 1 
7 5 3 
9 8 6 
3

Наивные реализации разобрали до меня, что ж... Если присмотреться, то можно заметить некоторое сходство искомого порядка заполнения массива с поиском в ширину, воспользуемся этим и получим такое решение:

class Program
{
    static void Main(string[] args) => new Program().Run();

    const int dim = 10;
    int[,] matrix = new int[dim, dim];
    Queue<(int, int)> queue = new Queue<(int, int)>();

    void Run()
    {
        Fill();
        Print();
    }

    void Fill()
    {
        int index = 0;
        queue.Enqueue((dim - 1, 0));
        while (queue.Count > 0)
        {
            var (x, y) = queue.Dequeue();
            matrix[x, y] = ++index;
            if (x > 0) EnqueueIfNotUsed(x - 1, y);
            if (y < dim - 1) EnqueueIfNotUsed(x, y + 1);
        }
    }

    void EnqueueIfNotUsed(int x, int y)
    {
        if (matrix[x, y] == 0 && !queue.Contains((x, y)))
            queue.Enqueue((x, y));
    }

    void Print()
    {
        var width = (dim * dim).ToString().Length + 1;
        for (int y = 0; y < dim; y++)
        {
            for (int x = 0; x < dim; x++)
                Console.Write(matrix[x, y].ToString().PadLeft(width));
            Console.WriteLine();
        }
        Console.ReadKey();
    }
}
0
3

Вот мой вариант. Он любопытен тем, что он реально заполняет змейкой и это особенно наглядно видно, если во входном массиве не хватает данных для полного заполнения квадрата ну и под отладкой:

0 0 0 10
0 0 0 0
0 0 0 0
0 0 0 0

0 0 20 10
0 0 0 0
0 0 0 0
0 0 0 0

0 0 20 10
0 0 0 31
0 0 0 0
0 0 0 0

0 44 20 10
0 0 0 31
0 0 0 0
0 0 0 0

0 44 20 10
0 0 55 31
0 0 0 0
0 0 0 0

Сам код:

void Main()
{
    const int max = 4;
    int[] numbers = { 10, 20, 31, 44, 55, 66, 77, 88, 90, 91, 92, 93, 94, 95, 96, 97 };
    var result = this.Putty(max, numbers);
    PrettyPrint(result, max);
}

// Define other methods and classes here

public int[,] Putty(int size, int[] numbers)
{
    int[,] matrix = new int[size, size];

    int x = 0;
    int y = size - 1;
    int turnAbove = 0;
    int turnBelow = 0;
    var iter = numbers.GetEnumerator();
    while (iter.MoveNext())
    {
        matrix[x, y] = (int)iter.Current;
        PrettyPrint(matrix, size);
        x++;
        y++;
        if (x >= size && y >= size)
        {
            turnBelow++;
            y = 0;
            x = turnBelow;
        }
        else if (y >= size)
        {
            turnAbove++;
            x = 0;
            y = size - 1 - turnAbove;
        }
        else if (x >= size)
        {
            turnBelow++;
            y = 0;
            x = turnBelow;
        }
    }

    return matrix;
}

public void PrettyPrint(int[,] matrix, int max)
{
    Console.WriteLine();
    for (int i = 0; i < max; i++)
    {
        for (int j = 0; j < max; j++)
            Console.Write(matrix[i, j] + "  ");
        Console.WriteLine();
    }
}

Если у вас входные числа идут не по порядку - самое то алгоритм, O(n)

Основа алгоритма - переход от текущей клетки x,y по диагонали через одновременное инкрементирование x и y.

Далее нужно написать условия определения того, что мы выскочили за край массива.

Я насчитал три варианта вылета: над диагональю, когда вылетели за вертиальную границу; под диагональю, когда вылетели за горизонтальную границу и на диагонали (вылетели одновременно за обе границы).

Вероятно, алгоритм можно попробовать оптимизировать (сократить число вспомогательных переменных или веток условий), оставляю место для творчества.

Так же я не стал учитывать вариант, когда у нас массив полностью заполнен, а входной IEnumerable ещё не кончился.

3

А давайте просто вычислим значение по данным индексам.

Над диагональю это просто: считаем элементы в предыдущих диагоналях (сумма арифметической прогрессии), и прибавляем номер в текущей диагонали. А чтобы не думать, что там под диагональю, воспользуемся симметричностью.

Итого:

static int GetValue(int i, int j, int max)
{
    if (i <= j)
    {
        int d = (i - j) + max - 1; // номер диагонали
        int s = d * (d + 1) / 2;   // сумма предыдущих диагоналей
        return s + i + 1;          // i = наш номер в диагонали
    }
    else
    {
        return max * max + 1 - GetValue(max - 1 - i, max - 1 - j, max);
    }
}

Основной код становится тривиальным:

const int max = 3;
int[,] matrix = new int[max, max];
for (int i = 0; i < max; i++)
    for (int j = 0; j < max; j++)
        matrix[i, j] = GetValue(i, j, max);

Результат, понятно, такой же.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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