Массив пересечения в диагональных полосах

Ответ 1

Здесь вы можете использовать. Просто замените printfs тем, что вы действительно хотите сделать.

#include <stdio.h>

int main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int n = 3;
    for (int slice = 0; slice < 2 * n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z = (slice < n) ? 0 : slice - n + 1;
        for (int j = z; j <= slice - z; ++j) {
            printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

Вывод:

Slice 0: 1
Slice 1: 2 4
Slice 2: 3 5 7
Slice 3: 6 8
Slice 4: 9

Ответ 2

Я бы сдвинул строки так:

1  2  3  x  x
x  4  5  6  x
x  x  7  8  9

И просто итерации столбцов. Это можно сделать без физического переключения.

Ответ 3

Посмотрим, как индексируются матричные элементы.

(0,0)   (0,1)   (0,2)   (0,3)   (0,4)  
(1,0)   (1,1)   (1,2)   (1,3)   (1,4)  
(2,0)   (2,1)   (2,2)   (2,3)   (2,4)  

Теперь посмотрим на полосы:

Stripe 1: (0,0)
Stripe 2: (0,1)    (1,0)  
Stripe 3: (0,2)    (1,1)    (2,0)
Stripe 4: (0,3)    (1,2)    (2,1)
Stripe 5: (0,4)    (1,3)    (2,2)
Stripe 6: (1,4)    (2,3)
Stripe 7: (2,4)

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

public static void printSecondaryDiagonalOrder(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int maxSum = rows + cols - 2;

    for (int sum = 0; sum <= maxSum; sum++) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i + j - sum == 0) {
                    System.out.print(matrix[i][j] + "\t");
                }
            }
        }
        System.out.println();
    }
}

Это не самый быстрый алгоритм (выполняет операции (строки * cols * (rows + cols-2)), но логика, лежащая в ее основе, довольно проста.

Ответ 4

Я думаю, что это может быть решением для любого типа матрицы.

#include <stdio.h>

#define M 3
#define N 4

main(){
         int a[M][N] = {{1, 2, 3, 4}, 
                        {5, 6, 7, 8}, 
                        {9,10,11,12}};

         int i, j, t;
         for( t = 0; t<M+N; ++t)
              for( i=t, j=0; i>=0 ; --i, ++j)
                     if( (i<M) && (j<N) )
                             printf("%d ", a[i][j]);
         return 0;
}

Ответ 5

Я думал, что эта проблема имеет тривиальное решение, пару из циклов и некоторых причудливых счетчиков

Точно.

Важно отметить, что если вы укажете каждому элементу индекс (i, j), то элементы на одной и той же диагонали имеют одно и то же значение j + n-i, где n - ширина вашей матрицы. Поэтому, если вы перебираете матрицу обычным способом (т.е. Вложенные петли над я и j), вы можете отслеживать диагонали в массиве, который адресован вышеупомянутым способом.

Ответ 6

//Этот алгоритм работает для матриц всех размеров.;)

    int x = 0;
    int y = 0;        
    int sub_x;
    int sub_y;

    while (true) {

        sub_x = x;
        sub_y = y;

        while (sub_x >= 0 && sub_y < y_axis.size()) {

            this.print(sub_x, sub_y);
            sub_x--;
            sub_y++;

        }

        if (x < x_axis.size() - 1) {

            x++;

        } else if (y < y_axis.size() - 1) {

            y++;

        } else {

            break;

        }

    }

Ответ 7

Я нашел это здесь: Поперечная прямоугольная матрица в диагональных полосах

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = slice - z2; j >= z1; --j) {
                printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}

выход:

Slice 0: 1
Slice 1: 5 2
Slice 2: 9 6 3
Slice 3: 10 7 4
Slice 4: 11 8
Slice 5: 12

Я нашел это довольно элегантным способом сделать это, поскольку ему нужна только память для 2 дополнительных переменных (z1 и z2), которые в основном содержат информацию о длине каждого фрагмента. Внешний цикл перемещается по номерам срезов (slice), а внутренний цикл перемещается через каждый срез с индексом: slice - z1 - z2. Вся остальная информация вам нужна тогда, когда начинается алгоритм и как он перемещается по матрице. В предыдущем примере он сначала сдвинется вниз по матрице, а после того, как он достигнет дна, он будет двигаться вправо: (0,0) → (1,0) → (2,0) → (2,1) → (2,2) → (2,3). Опять же эта картина захватывается varibales z1 и z2. Строка увеличивается вместе с числом slice до тех пор, пока она не достигнет дна, затем z2 начнет увеличиваться, что может использоваться для поддержания константы индекса строки в ее позиции: slice - z2. Каждая длина среза известна следующим образом: slice - z1 - z2, используя следующее: (slice - z2) - (slice - z1 -z2) (минус по мере продвижения алгоритма в порядке возрастания m--, n ++) приводит к z1, который является критерием остановки для внутреннего цикла. Остается только индекс столбца, который удобно унаследован от того факта, что j является постоянным после достижения дна, после чего индекс столбца начинает увеличиваться.

Предшествующий алгоритм перемещается только в порядке возрастания слева направо, начиная с левого верхнего угла (0,0). Когда мне понадобился этот алгоритм, мне также нужно было искать матрицу в порядке убывания, начиная с левого нижнего (m, n). Поскольку я был сильно поражен алгоритмом, я решил дойти до конца и адаптировать его:

• длина фрагмента снова известна: slice -z1 - z2
• Исходное положение срезов: (2,0) → (1,0) → (0,0) → (0,1) → (0,2) → (0,3 )
• Движение каждого среза - m ++ и n ++

Мне было очень полезно изобразить его следующим образом:

• slice = 0 z1 = 0 z2 = 0 (2,0) (column index = rowindex - 2)
• slice = 1 z1 = 0 z2 = 0 (1,0) (2,1) (column index = rowindex - 1)
• slice = 2 z1 = 0 z2 = 0 (0,0) (1,1) (2,2) (column index = rowindex + 0)
• slice = 3 z1 = 0 z2 = 1 (0,1) (1,2) (2,3) (column index = rowindex + 1)
• slice = 4 z1 = 1 z2 = 2 (0,2) (1,3) (индекс столбца = rowindex + 2)
• slice = 5 z1 = 2 z2 = 3 (0,3) (индекс столбца = rowindex + 3)

Вывод следующего: j = (m-1) - slice + z2 (с j ++) используя выражение длины среза, чтобы сделать критерий остановки: ((m-1) - slice + z2)+(slice -z2 - z1) приводит к: (m-1) - z1 Теперь у нас есть аргументы для внутреннего оврага: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

Индекс строки известен по j, и снова мы знаем, что индекс столбца начинает увеличиваться, когда j начинает быть постоянным, и, следовательно, с j в выражении снова не является плохой идеей. Из различий между приведенным выше суммированием я заметил, что разница всегда равна j - (slice - m +1), проверяя это для некоторых других случаев, я был уверен, что это будет выполняться для всех случаев (я не математик; P) и, следовательно, алгоритм для нисходящего движения, начиная с левого нижнего положения, выглядит следующим образом:

#include <stdio.h>

int main()
{
    int x[3][4] = { 1,  2,  3,  4,
                    5,  6,  7,  8,
                    9, 10, 11, 12};
    int m = 3;
    int n = 4;
    for (int slice = 0; slice < m + n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z1 = slice < n ? 0 : slice - n + 1;
        int z2 = slice < m ? 0 : slice - m + 1;
        for (int j = (m-1) - slice + z2; j <= (m-1) - z1; j++) {
                printf("%d ", x[j][j+(slice-m+1)]);
        }
        printf("\n");
    }
    return 0;
}

Теперь я оставлю два других направления до вас ^^ (что важно только тогда, когда порядок действительно важен).

Этот алгоритм - довольно изгиб ума, даже если вы думаете, что знаете, как он работает, он все равно может укусить вас в заднице. Однако я думаю, что это довольно красиво, потому что буквально движется по матрице, как и следовало ожидать. Мне интересно, если кто-то знает больше об алгоритме, например, о имени, поэтому я могу посмотреть, действительно ли то, что я здесь сделал, имеет смысл и, возможно, есть лучшие решения.

Ответ 8

Ключ состоит в том, чтобы перебирать каждый элемент в первой строке, а от него идти по диагонали. Затем перебирайте каждый элемент в последнем столбце (без первого, на который мы шагнули на предыдущем шаге), а затем спустимся по его диагонали.

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

#define N 10
void diag_step(int[][] matrix) {
    for (int i = 0; i < N; i++) {
        int j = 0;
        int k = i;
        printf("starting a strip\n");
        while (j < N && i >= 0) {
            printf("%d ", matrix[j][k]);
            k--;
            j++;
        }
        printf("\n");
    }

    for (int i = 1; i < N; i++) {
        int j = N-1;
        int k = i;
        printf("starting a strip\n");
        while (j >= 0 && k < N) {
            printf("%d ", matrix[k][j]);
            k++;
            j--;
        }
        printf("\n");
    }   
}   

Ответ 9

Псевдокод:

N = 2 // or whatever the size of the [square] matrix
for x = 0 to N
  strip = []
  y = 0
  repeat
     strip.add(Matrix(x,y))
     x -= 1
     y -= 1
  until x < 0
  // here to print the strip or do some' with it

// And yes, Oops, I had missed it... 
// the 2nd half of the matrix...
for y = 1 to N    // Yes, start at 1 not 0, since main diagonal is done.
   strip = []
   x = N
   repeat
      strip.add(Matrix(x,y))
      x -= 1
      y += 1
   until x < 0
  // here to print the strip or do some' with it

(Предполагается, что x индексов строк, y индексов столбцов, отмените эти две, если матрица индексируется наоборот)

Ответ 10

На всякий случай кому-то нужно сделать это в python, очень просто использовать numpy:

#M is a square numpy array    
for i in range(-M.shape[0]+1, M.shape[0]):
    print M.diagonal(offset=i)

Ответ 11

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

for i in 0:n
    for j in 0:i +1
        A[i + j*(n-2)]

the other half can be done in a similar way, starting with:
for j in 1:n
    for i in 0:n-j
        ... each step is i*(n-2) ...

Ответ 12

Я бы, наверное, сделал что-то вроде этого (извиняюсь заранее за любые ошибки индекса, не отлаживал это):

// Operation to be performed on each slice:
void doSomething(const int lengthOfSlice,
                 elementType *slice,
                 const int stride) {
    for (int i=0; i<lengthOfSlice; ++i) {
        elementType element = slice[i*stride];
        // Operate on element ...
    }
}

void operateOnSlices(const int n, elementType *A) {
    // distance between consecutive elements of a slice in memory:
    const int stride = n - 1;

    // Operate on slices that begin with entries in the top row of the matrix
    for (int column = 0; column < n; ++column)
        doSomething(column + 1, &A[column], stride);

    // Operate on slices that begin with entries in the right column of the matrix
    for (int row = 1; row < n; ++row)
        doSomething(n - row, &A[n*row + (n-1)], stride);
}

Ответ 13

static int[][] arr = {{ 1, 2, 3, 4},
                      { 5, 6, 7, 8},
                      { 9,10,11,12},
                      {13,14,15,16} };

public static void main(String[] args) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i+1; j++) {
            System.out.print(arr[j][i-j]);
            System.out.print(",");
        }
        System.out.println();
    }

    for (int i = 1; i < arr.length; i++) {
        for (int j = 0; j < arr.length-i; j++) {
            System.out.print(arr[i+j][arr.length-j-1]);
            System.out.print(",");
        }
        System.out.println();
    }
}

Ответ 14

Более простая реализация:

//Assuming arr as ur array and numRows and numCols as what they say.
int arr[numRows][numCols];
for(int i=0;i<numCols;i++) {
    printf("Slice %d:",i);
    for(int j=0,k=i; j<numRows && k>=0; j++,k--)
    printf("%d\t",arr[j][k]);
}

Ответ 15

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() 
{
    int N = 0;
    cin >> N;

    vector<vector<int>> m(N, vector<int>(N, 0));

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> m[i][j];
        }
    }

    for (int i = 1; i < N << 1; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (j < N && i - j - 1 < N)
            {                          
               cout << m[j][i - j - 1];
            }
        }
        cout << endl;
    }
    return 0;
}

Ответ 16

public void printMatrix(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    for (int i = 0; i < m + n - 1; i++) {
         int start_row = i < m ? i : m - 1;
         int start_col = i < m ? 0 : i - m + 1;
         while (start_row >= 0 && start_col < n) {
               System.out.print(matrix[start_row--][start_col++]);
         }
         System.out.println("\n")
     }
}