删除每个元素可以分隔数组中的另一个元素

我正在咨询StackOverflow的天才。我一直坚持使用我正在编写的算法返回两个或更多数字的最小公倍数（LCM）。删除每个元素可以分隔数组中的另一个元素

例如，LCM（3，4,6）= 24，LCM（2，2，2）= 2，LCM（8,9）= 72，等

这是我想要的程序使用（除非你有更好的想法）：

（1）阵列复制到一个向量（因为我们需要它是动态的步骤3）

（2）排序向量（这将使步3更容易）

（3）删除每个元素被分成另一个元素（例如，如果你想要计算LCM（3,4,6），3是多余的，因为LCM（3，4,6）= LCM（4,6））

（4）的阵列中的每个元件的计算机产品

步骤3是其中我无法写入优雅过程，因为所有的删除操作都会改变向量的大小和等等。

int LCM(int* numsPtr, size) { 
    assert(size > 1); 
    std::vector<int> numsVec(numsPtr, numsPtr + size); // need to work with copy of the array 
    for (int k = 0; k < size; ++k) 
     numsVec[k] = numsPtr[k]; 
    std::sort(numsVec, numsVec + size); 
    // What now???? 
}

顺便说一句，这是我努力的一部分，在项目欧拉Problem 5

我已经做了蛮力方式

// -------------------- Brute force -------------------- 
int n = 20; 
int k = n; 
while (true) { 
// divisors to cross off: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
    if ( (k % 20 == 0) // 3 6 7 8 9 11 12 13 14 15 16 17 18 19 
     && (k % 19 == 0) // 3 6 7 8 9 11 12 13 14 15 16 17 18 
     && (k % 18 == 0) // 7 8 11 12 13 14 15 16 17 
     && (k % 17 == 0) // 7 8 11 12 13 14 15 16 
     && (k % 16 == 0) // 7 11 12 13 14 15 
     && (k % 15 == 0) // 7 11 12 13 14 
     && (k % 14 == 0) // 11 12 13 
     && (k % 13 == 0) // 11 12 
     && (k % 12 == 0) // 11 
     && (k % 11 == 0) ) 
     break; 
    ++k; 
} 
std::cout << "The smallest number divisible by 1, 2, ..., " << n << " is " << k << std::endl;

和我试图改善它。

来源

2014-01-24 user3178285

这也许不是最有用的答案，但考虑到计算一系列整数的LCM问题，我会以不同的方式处理问题。

从高中数学，你可能还记得，

GCD(m, n) * LCM(m, n) = m*n

因此，对于两个整数，我们有办法来计算最大公约数方面的LCM。 GCD使用众所周知的欧几里得算法很容易计算。

所以，现在我们有一个LCM算法的fundementals为整数的任意序列：

让m和n是序列
的前两个元素集m = m * n/GCD(m, n)
设置n作为该序列的下一个元素并转到2.
返回米

即我们计算第一对的LCM，则该搜索结果的LCM和序列的下一元素，依此类推。

我不知道这是否是最佳的，但它不需要动态存储或排序元素，所以它应该比上面的解决方案更快。

（另外，顺便说一句，我敢肯定，LCM（3，4，6）= 12，而不是24 :-)）

编辑：我发现这个问题很有趣，足以破解一个解决办法，所以我也不妨分享...

#include <iostream> 
#include <vector> 

template <typename T> 
inline T gcd(T a, T b) 
{ 
    while (b != 0) { 
     T t = b; 
     b = a % b; 
     a = t; 
    }  
    return a; 
} 

template <typename Iter> 
inline auto 
lcm(Iter start, Iter end) 
    -> typename std::iterator_traits<Iter>::value_type 
{ 
    using value_type = typename std::iterator_traits<Iter>::value_type; 

    if (start == end) return 0; // empty sequence 

    value_type m{*start}; 

    while (++start != end) { 
     value_type n{*start}; 
     m = m * n/gcd(m, n); 
    } 
    return m; 
} 

int main() 
{ 
    std::vector<int> v{3, 4, 20, 5, 12, 15}; 
    std::cout << lcm(v.begin(), v.end()) << std::endl; // prints 60 
}

注释和更正欢迎当然:-)

来源

2014-01-24 05:27:25

删除每个元素可以分隔数组中的另一个元素

回答

相关问题