aly*_*lyx 31 c algorithm traversal matrix
我认为这个问题有一个简单的解决方案,几个for循环和一些花哨的计数器,但显然它更复杂.
所以我的问题是,你如何编写(在C中)对角线条中方形矩阵的函数遍历.
例:
1 2 3
4 5 6
7 8 9
必须按以下顺序遍历:
[1],[2,4],[3,5,7],[6,8],[9]
上面的每个条带都用方括号括起来.其中一个要求是能够区分条带.这意味着你知道什么时候开始新的条带.这是因为我必须为条带中的每个项目调用另一个函数,然后在新条带的开头之前调用.因此,没有代码重复的解决方案是理想的.
Mar*_*ers 62
这是你可以使用的东西.只需将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
Kug*_*gel 41
我会像这样移动行:
1 2 3 x x
x 4 5 6 x
x x 7 8 9
只需迭代列.实际上,这可以在没有物理移位的情
ior*_*vic 21
我们来看看矩阵元素是如何编入索引的.
(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();
}
}
它不是最快的算法(行(col*cols*(行+ cols-2))),但它背后的逻辑非常简单.
小智 5
我在这里找到了这个：Traverse Rectangular Matrix in Diagonal strips
#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)。这种模式再次被变量 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我发现将其描述如下非常有用：
推导以下内容：（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;
}
现在我把其他两个方向留给你 ^^（只有在顺序实际上很重要时才重要）。
这个算法非常令人费解，即使你认为你知道它是如何工作的，它仍然会咬你的屁股。但是我认为它非常漂亮，因为它确实像您期望的那样在矩阵中移动。如果有人对算法有更多了解，例如名称，我很感兴趣，所以我可以看看我在这里所做的是否真的有意义，也许有更好的解决方案。