如何编写代码，将偶数除以最大的奇数

Question

我有一组数字要核对。如果数字是偶数，程序将检查最大的奇数分频器相等。例如，如果数字是12，程序将返回类似[3，3，3，3]的数组，或者对于36，它将是[9，9，9，9]，对于54，[27，27]和56，[7，7，7，7，7，7，7]等等。我正在用ruby写我的代码。我不知道如何写出正确的算法。任何帮助都将不胜感激。

Answer 1

您可以分两步完成：

确定数字可被二整除的次数（假设 in 为正数） - 在伪代码中：

int divisors(int in):
    int divisor = 1
    for(; in % 2 == 0; divisor *= 2)
        in /= 2   //integer division!!!

    return divisor

除数将返回2的最大幂，中的可以被整除。这个想法是任何数字n都可以用它的素分解来表示，类似于：

n = 2^a * 3^b * 5^c * ...

我们只需要知道a，因为分解的其余部分必然是我们的最大奇数除数。或者更详细地说：

n = 2^a * 3^b * 5^c * ...
largest_odd_divisor = 3^b * 5^c * ...
largest_even_divisor = 2^a = divisors(n)

我们找不到任何更大的奇数除数，因为我们只消除了n中的所有偶数除数，所以我们只得到了可以添加到largest_odd_divisor中的偶数除数，但正因为如此，除数将变为偶数。

其余的都是微不足道的：
Geta（如上所示），创建一个大小为2^a的数组并将其填充为n/（2^a）。

Answer 2

试试这个

def fun(num)
  odd = num
  odd /= 2 while odd.even?
  [odd] * (num / odd)
end

这是如何工作的？

这会将数字除以 2，直到它是奇数。