0

我有数据文件 F_j,每个文件都包含一个小数位数未知的数字列表。每个文件都包含一些连续变量的离散化测量,我想找到文件 F_j 的离散化步骤 d_j

我可以想出的解决方案:对于每个 F_j,

  • 找到小数位数 (n_j);
  • 将 F_j 中的每个数字乘以 10^{n_j} 以获得整数;
  • 找到整个列表的最大公约数。

我正在寻找一种用 Matlab 找到 n_j 的优雅方法。

此外,找到一长串整数的 gcd 似乎很难——你有更好的主意吗?

4

2 回答 2

0

找到一长串数字的 gcd 并不。您可以在列表大小的时间内线性地做到这一点。如果你幸运的话,你可以在时间上比线性少得多。本质上这是因为:

gcd(a,b,c) = gcd(gcd(a,b),c)

并且a=1无论其他数字的大小b=1如何gcd(a,b)=1

所以如果你有一个数字列表,xs你可以做

g = xs(1);

for i = 2:length(xs)
  g = gcd(x(i),g);
  if g == 1
    break
  end
end

该变量g现在将存储列表的 gcd。

于 2012-07-24T13:18:18.130 回答
0

这是一些示例代码,我相信一旦您获得想要查看的数字,它们将帮助您获得 GCD。

A = [15 30 20];
A_min = min(A);
GCD = 1;
for n = A_min:-1:1
    temp = A / n;
    if (max(mod(temp,1))==0)
        % yay GCD found
        GCD = n;
        break;
    end
end

这里的基本概念是默认的 GCD 将始终为 1,因为每个数字都可以被自己整除1,当然 =)。GCD 也不能大于列表中的最小数字,因此我从最小数字开始,然后减 1。这是假设您此时已经将数字转换为整数形式。小数会扔掉这个!

通过使用 1 的模数,您正在测试该数字是否为整数,如果不是,您将留下大于 0 的小数余数。如果您预计必须处理负数,则必须进行调整这个测试!

除此之外,当您第一次找到列表的模数(mod 1)全为零时,您就找到了 GCD。

享受!

于 2012-07-24T13:20:29.937 回答