我已经开始阅读Cormen的Introduction to Algorithms,并遇到了斯特拉森算法的问题(第4.2章):
S-M x-M-R s(,)𝐴
1 𝑛 ==𝐴。𝑟𝑜𝑤𝑠
2 设𝐶是一个新的𝑛×𝑛矩阵
3 如果𝑛== 1
4 𝑐 11 =𝑎 11𝑏 11
5 elsepartition𝐴,𝐵和𝐶如等式(4.9)所示
6 𝐶 11 = S-M x-M-R s(𝐴11,𝐵11)
+ S-M x-M-R s(12, 21)𝐴
7 𝐶 12 = S-M x-M-R s(𝐴11,𝐵12)
+ S-M x-M-R s(12, 22)𝐴
8 𝐶 21 = S-M x-M-R s(𝐴21,𝐵11)
+ S-M x-M-R s(22, 21)𝐴
9 𝐶 22 = S-M x-M-R s(𝐴21,𝐵12)
+ S-M x-M-R s(22, 22)𝐴
10 返回𝐶
我决定像这样实现算法函数:
int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N);
在递归调用这个函数的过程中,我需要传递一个指向矩阵元素的指针。我不知道怎么做
实际代码:
#include <stdio.h>
#include <stdlib.h>
#define SIZE_STRING_A 2
#define SIZE_STRING_B 2
#define SIZE_COLUMN_A 2
#define SIZE_COLUMN_B 2
int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N);
int main (void)
{
int ** arr_a;
arr_a = (int**) calloc (SIZE_STRING_A, sizeof (int*));
for (int i = 0; i < SIZE_STRING_A; i++)
arr_a [i] = (int*) calloc (SIZE_COLUMN_A, sizeof (int));
for (int i = 0; i < SIZE_STRING_A; i++)
for (int j = 0; j < SIZE_COLUMN_A; j++)
arr_a [i] [j] = i + j;
for (int i = 0; i < SIZE_STRING_A; i++)
{
for (int j = 0; j < SIZE_COLUMN_B; j++)
printf ("%d ", arr_a [i] [j]);
printf ("\n");
}
int ** arr_b;
arr_b = (int**) calloc (SIZE_STRING_B, sizeof (int*));
for (int i = 0; i < SIZE_STRING_B; i++)
arr_b [i] = (int*) calloc (SIZE_COLUMN_B, sizeof (int));
for (int i = 0; i < SIZE_STRING_B; i++)
for (int j = 0; j < SIZE_COLUMN_B; j++)
arr_b [i] [j] = i + j;
for (int i = 0; i < SIZE_STRING_A; i++)
{
for (int j = 0; j < SIZE_COLUMN_B; j++)
printf ("%d ", arr_b [i] [j]);
printf ("\n");
}
int ** arr_c;
arr_c = (int**) calloc (SIZE_STRING_A, sizeof (int*));
for (int i = 0; i < SIZE_STRING_B; i++)
arr_c [i] = (int*) calloc (SIZE_COLUMN_B, sizeof (int));
square_matrix_multiply_recursive (arr_a, arr_b, arr_c, 2);
for (int i = 0; i < SIZE_STRING_A; i++)
{
for (int j = 0; j < SIZE_COLUMN_B; j++)
printf ("%d ", arr_c [i] [j]);
printf ("\n");
}
return 0;
}
int ** square_matrix_multiply_recursive (int ** arr_a, int ** arr_b, int ** arr_c, int N)
{
if (N == 1)
{
(**arr_c) = (**arr_b) * (**arr_a);
return arr_c;
}
else
{
arr_c [0] [0] = (**square_matrix_multiply_recursive (/*arr_a [0] [0]*/, /*arr_b [0] [0]*/, /*arr_c [0] [0]*/, N / 2)) + (**square_matrix_multiply_recursive (/*arr_a [0] [1]*/, /*arr_b [1] [0]*/, /*arr_c [0] [0]*/, N / 2));
}
return arr_c;
}
代码中有许多问题(这是测试版本),但致命的一个是传递一个指向矩阵元素的指针。
1条答案
按热度按时间6jjcrrmo1#
由于您的代码无法按原样编译,并且它只尝试分配给
arr_c[0][0]
,因此还有很多工作要做。至于这个问题,“如何传递一个指针到一个矩阵元素”,答案是你不应该。你的矩阵元素是整数,它们不应该是指针。事实上,在没有显式指针的情况下实现它可能更易读,因为您可以始终使用数组表示法。我还建议:
有很多方法可以做到这一点,这里只有一个:
此示例运行具有以下输出:
最后,请注意,这并没有完全实现斯特拉森的算法:分而治之的方法是相同的,但是该算法应用不同的矩阵运算集合,以便保存它们的数量。参见𝑀维基百科关于斯特拉森算法的文章中矩阵的用法。