我正在寻找一种方法来划分某个矩阵元素及其最低公约数。
例如,我有向量
[0,0,0; 2,4,2;-2,0,8]
我可以看出最小公约数是2,所以除法后的矩阵就是
[0,0,0;1,2,1;-1,0,4]
可以计算这个的内置方法是什么?
提前致谢
附注我个人不喜欢在这个计算中使用循环,似乎有内置的计算可以执行矩阵元素除法。
最佳答案
既然不喜欢循环,那递归函数呢?
iif = @(varargin) varargin{2 * find([varargin{1:2:end}], 1, 'first')}();
gcdrec=@(v,gcdr) iif(length(v)==1,v, ...
v(1)==1,1, ...
length(v)==2,@()gcd(v(1),v(2)), ...
true,@()gcdr([gcd(v(1),v(2)),v(3:end)],gcdr));
mygcd=@(v)gcdrec(v(:)',gcdrec);
A=[0,0,0; 2,4,2;-2,0,8];
divisor=mygcd(A);
A=A/divisor;
第一个函数 iif
将定义一个内联条件结构。这允许定义递归函数 gcdrec
,以找到数组的最大公约数。这iif
工作原理如下:它测试第一个参数是否为 true
,如果是,则返回第二个参数。否则它会测试第三个参数,如果 that's true
,则返回第四个,依此类推。您需要使用 @()
保护递归函数和有时出现在其中的其他量,否则您可能会出错。
使用 iif
递归函数 gcdrec
的工作原理如下:
- 如果输入向量是标量,则返回它
- 否则如果向量的第一个分量是 1,则没有机会恢复,因此它返回 1(允许快速返回大矩阵)
- 否则,如果输入向量的长度为 2,则通过
gcd
返回最大公约数 - 否则它会用一个缩短的向量调用自己,其中前两个元素用它们的最大公约数代替。
函数 mygcd
只是为了方便起见的前端。
应该很快,而且我猜只有递归深度可能是非常大的问题的问题。我使用 A=randi(100,N,N)-50
和 N=100
进行了快速计时检查,以与 @Adriaan 的循环版本进行比较,N=1000
和 N=5000
和 tic
/toc
。
N=100
:- 循环 0.008 秒
- 递归 0.002 秒
N=1000
:- 循环0.46秒
- 递归0.04秒
N=5000
:- 循环 11.8 秒
- 递归0.6秒
更新:有趣的是,我没有超出递归限制(默认为 500)的唯一原因是我的数据没有公约数。设置一个随机矩阵并将其加倍将导致达到 N=100
的递归限制。所以对于大矩阵,这是行不通的。再一次,对于小矩阵,@Adriaan 的解决方案非常好。
我还尝试在每个递归步骤中将其重写为输入向量的一半:这确实解决了递归限制问题,但它非常慢(N=100< 2 秒
,N=1000
为 261 秒)。某处可能有一个中间地带,其中矩阵大小很大(大概)并且运行时还不错,但我还没有找到它。
关于matlab - 在 MATLAB 中找到矩阵的最大公约数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32684217/