대각선 스트립의 다각측량 행렬
저는 이 문제가 루프와 멋진 카운터를 위한 사소한 해결책이 있다고 생각했지만, 분명히 그것은 오히려 더 복잡합니다.
그래서 제 질문은 (C) 대각선으로 정사각형 행렬의 함수 횡단을 어떻게 쓰시겠습니까?
예:
1 2 3
4 5 6
7 8 9
다음 순서로 횡단해야 합니다.
[1],[2,4],[3,5,7],[6,8],[9]
위의 각 스트립은 대괄호로 둘러싸여 있습니다.요구 사항 중 하나는 스트립을 구별할 수 있는 것입니다.새 스트립을 시작할 때 알 수 있다는 뜻입니다.스트립의 각 항목에 대해 그리고 새 스트립의 시작 전에 호출해야 하는 다른 기능이 있기 때문입니다.따라서 코드 중복이 없는 솔루션이 이상적입니다.
여기 당신이 사용할 수 있는 것이 있습니다.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
다음과 같이 행을 이동합니다.
1 2 3 x x
x 4 5 6 x
x x 7 8 9
그리고 열을 반복합니다.이것은 실제로 물리적인 변화 없이 수행될 수 있습니다.
행렬 요소가 인덱싱되는 방식을 살펴보겠습니다.
(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();
}
}
가장 빠른 알고리즘은 아니지만(행 * 콜 * (행 + 콜 - 2)) 그 뒤에 있는 논리는 매우 간단합니다.
여기서 이걸 찾았습니다.대각선 스트립의 다각형 행렬 이동
#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)에 대한 메모리만 필요하기 때문에 매우 우아한 방법이라고 생각했습니다. 번호바깥다동루슬번통스이호해니합를라프이가쪽(▁(▁the다▁through니바▁the▁moves)를 통해 이동합니다.slice는 인덱스가 각 합니다.slice - z1 - z2그러면 알고리즘이 시작되는 위치와 알고리즘이 매트릭스를 통해 이동하는 방식에 필요한 다른 모든 정보가 표시됩니다.앞의 예에서, 그것은 먼저 행렬 아래로 이동하고, 그것이 아래에 도달한 후에 오른쪽으로 이동할 것입니다: (0,0) -> (1,0) -> (2,1) -> (2,2) -> (2,3).다시 이 패턴은 변수 z1 및 z2에 의해 캡처됩니다.은 행다음값과증니다합가함께은과 합니다.slice를 매기고, 그 다음에 에닿때번호매를기나고서지까을바닥,▁number나▁unt서고▁then,▁bottom기매▁the.z2할 수 있는 를 시작합니다. 행 인 덱 스 해 위 유 사 수 있 증 는 을 분 합 시 작 니 다 할 용 데 는 하 를 지 게 당 하 일 정 치 에 서 ▁which ▁will ▁constant ▁start 니 ▁to 합 다 ▁increment ▁index ▁be 행 작 ▁to ▁can ▁row 시 ▁keep '▁atslice - z2각 조각의 길이는 다음을 통해 알 수 있습니다.slice - z1 - z2합니다.(slice - z2) - (slice - z1 -z2) 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)(열 인덱스=행 인덱스 - 2)
- slice=1 z1=0 z2=0 (1,0) (2,1) (열 인덱스= 행 인덱스 - 1)
- slice=2 z1=0 z2=0(0,0)(1,1)(2,2)(열 인덱스=행 인덱스 + 0)
- slice=3 z1=0 z2=1(0,1)(1,2)(2,3)(열 인덱스=행 인덱스 + 1)
- 슬라이스=4 z1=1 z2=2(0,2)(1,3)(열 인덱스=행 인덱스+2)
- slice=5 z1=2 z2=3 (0,3) (열 인덱스= 행 인덱스 + 3)
합니다.j = (m-1) - slice + z2로) 하여 중지 (j++로) 슬라길식사정여하기만다듭지니준.((m-1) - slice + z2)+(slice -z2 - z1) 대상: 결과:(m-1) - z1루프에 . 이제내부루대한인있수습가다니프에있▁we다gum습.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;
}
이제 나머지 두 가지 방향은 ^^(주문이 실제로 중요할 때만 중요함)에게 맡깁니다.
이 알고리즘은 꽤나 마음을 편안하게 해줍니다. 어떻게 작동하는지 안다고 생각할 때도 여전히 여러분을 괴롭힐 수 있습니다.하지만 저는 그것이 문자 그대로 여러분이 기대하는 것처럼 매트릭스를 통해 움직이기 때문에 꽤 아름답다고 생각합니다.예를 들어, 저는 알고리즘에 대해 더 많이 알고 있는 사람이 있는지 관심이 있습니다. 그래서 제가 여기서 한 일이 실제로 말이 되는지 그리고 더 나은 해결책이 있는지 볼 수 있습니다.
저는 이것이 어떤 형태의 매트릭스에 대해서도 해결책이 될 수 있다고 생각합니다.
#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;
}
저는 이 문제에 사소한 해결책이 있다고 생각했습니다. 루프 몇 개와 고급 카운터 몇 개.
그렇고말고.
각 항목에 인덱스(i, j)를 지정하면 동일한 대각선에 있는 항목의 값 j+n-i가 같고 여기서 n은 행렬의 너비입니다.따라서 일반적인 방법(즉, i 및 j에 대한 중첩 루프)으로 행렬 위에서 반복하면 위에서 언급한 방법으로 처리되는 배열에서 대각선을 추적할 수 있습니다.
이 알고리즘은 모든 크기의 행렬에 적용됩니다. ;)
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;
}
}
첫 번째 행에 있는 모든 항목을 반복하고 대각선 아래로 내려가는 것이 핵심입니다.그런 다음 마지막 열의 모든 항목(이전 단계에서 설명한 첫 번째 항목 제외)을 반복한 다음 대각선 아래로 이동합니다.
다음은 행렬이 사각 행렬(테스트되지 않고 작동하는 파이썬 코드에서 변환됨)이라고 가정하는 소스 코드입니다.
#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");
}
}
유사 코드:
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개의 인덱스 열, 행렬이 반대로 인덱스되면 이 두 행을 반대로 한다고 가정합니다.)
만약 누군가가 파이썬에서 이것을 해야 한다면, numpy를 사용하는 것은 매우 쉽습니다.
#M is a square numpy array
for i in range(-M.shape[0]+1, M.shape[0]):
print M.diagonal(offset=i)
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")
}
}
행렬을 상위 부분과 하위 부분으로 나누고 각 부분을 먼저 반 행, 다른 열로 나누어 반복해야 합니다.행렬이 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) ...
아마 다음과 같은 작업을 수행할 것입니다(인덱스 오류에 대해 미리 사과드립니다. 디버깅하지 않았습니다).
// 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);
}
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();
}
}
훨씬 더 쉬운 구현:
//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]);
}
#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;
}
간단한 파이썬 솔루션
from collections import defaultdict
def getDiagonals(matrix):
n, m = len(matrix), len(matrix[0])
diagonals = defaultdict(list)
for i in range(n):
for j in range(m):
diagonals[i+j].append(matrix[i][j])
return list(diagonals.values())
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
assert getDiagonals(matrix) == [[1], [2, 4], [3, 5, 7], [6, 8], [9]]
언급URL : https://stackoverflow.com/questions/1779199/traverse-matrix-in-diagonal-strips
'programing' 카테고리의 다른 글
| HTML에서 한 이미지를 다른 이미지 위에 어떻게 배치합니까? (0) | 2023.07.31 |
|---|---|
| 테스트 중에 Spring Boot에서 /tmp/spring.log 파일을 사용 (0) | 2023.07.31 |
| 교차 오리진 요청 차단됨 (0) | 2023.07.31 |
| Asp.net Core의 Ajax 도우미 태그 설명서 (0) | 2023.07.31 |
| Null DATE 필드에 대한 MariaDB LOAD DATA INFILE (0) | 2023.07.31 |