刪除每個元素可以分隔數組中的另一個元素

我正在諮詢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

刪除每個元素可以分隔數組中的另一個元素

回答

相關問題