Вычислить LCM 2 чисел с помощью шаблонов

Question

Программы ниже вычисляет LCM из 2-х номеров, ожидаемый выход 216 с входом 54 и 24, но я получаю 57.

Может кто-то помочь с тем же, и дайте мне знать, что случилось с фрагментом кода ниже.

/* ***********/
*** LCM ******/ 
/**************/ 
template<bool cond, int V1, int V2> 
struct IfCond 
{ 
    enum 
    { 
     value = V1 
    }; 
}; 

template<int V1, int V2> 
struct IfCond<0, V1, V2> 
{ 
    enum 
    { 
     value = V2 
    }; 
}; 

template<int V1, int V2> 
struct findMax 
{ 
    enum 
    { 
     result = V1 > V2, 
     value = IfCond<result, V1, V2>::value 
    }; 
}; 

template<int V1, int V2, int max> 
struct findLCM 
{ 
    enum 
    { 
     result = findLCM<max % V1, max % V2, max+1>::result 
    }; 
}; 

template<int V2, int max> 
struct findLCM<0, V2, max> 
{ 
    enum 
    { 
     result = findLCM<0, max % V2, max+1>::result 
    }; 
}; 

template<int V1, int max> 
struct findLCM<V1, 0, max> 
{ 
    enum 
    { 
     result = findLCM<max % V1, 0, max+1>::result 
    }; 
}; 

template<int max> 
struct findLCM<0, 0, max> 
{ 
    enum 
    { 
     result = max 
    }; 
}; 

int main() 
{ 
    std::cout<< findLCM<54, 24, findMax<54, 24>::value>::result << std::endl; 
} 

Answer 1

Что вам нужно:

template<int V1, int V2> 
struct findGCD 
{ 
    enum { result = findGCD<V2, V1%V2>::result }; 
}; 

template<int V1> 
struct findGCD<V1,0> 
{ 
    enum { result = V1 }; 
}; 

template<int V1, int V2> 
struct findLCM 
{ 
    enum { result = (V1/findGCD<V1,V2>::result) * V2 }; 
}; 

int main() 
{ 
    std::cout<< findGCD<54, 24>::result << std::endl; // 6 
    std::cout<< findLCM<54, 24>::result << std::endl; // 216 
} 

Если вы хотите сделать это с помощью линейного поиска, вам нужно будет что-то вроде:

template <int V1, int V2, bool finished, int target> 
struct findLCMHelper 
{ 
    enum { result = findLCMHelper<V1, V2, 
         target%V1 == 0 && target%V2==0, 
         target+1>::result }; 
}; 

template<int V1, int V2, int target> 
struct findLCM<V1, V2, true, target> 
{ 
    enum { result = target-1 }; // Correct overshoot 
}; 

template<int V1, int V2> 
struct findLCM 
{ 
    enum { target = findMax<V1,V2>::value, 
      result = findLCMHelper<V1, V2, 
         target%V1 == 0 && target%V2==0, 
         target+1>::result }; 
}; 

мне не нравится, что двойной тест хоть. Должен быть способ реорганизовать это. Я ожидаю, что это сломает компилятор - это вызовет более 150 нечетных экземпляров шаблонов.

Поразительно, cpp.sh отказывается разорвать - даже с 5400,24

Answer 2

Я думаю, что вы coul'd сделать что-то вроде этого

#include <iostream> 

template <int X, int Y> 
struct findGDMH 
{ static int const result = findGDMH<Y, X%Y>::result; }; 

template <int X> 
struct findGDMH<X, 0> 
{ static int const result = X; }; 

template <int X, int Y> 
struct findGDM 
{ 
    static bool const largerIsX = (X > Y); 
    static int const A   = (largerIsX ? X : Y); 
    static int const B   = (largerIsX ? Y : X); 
    static int const result = findGDMH<A, B>::result; 
}; 

template <int X> 
struct findABS 
{ static int const result = (X > 0 ? X : -X); }; 

template <int X, int Y> 
struct findLCM 
{ static int const result = findABS<X*Y>::result 
/findGDM<findABS<X>::result, findABS<Y>::result>::result; }; 

template <int X> 
struct findLCM<X, 0> 
{ static int const result = 0; }; 

template <int X> 
struct findLCM<0, X> 
{ static int const result = 0; }; 

template <> 
struct findLCM<0, 0> 
{ static int const result = 0; }; 


int main() 
{ 
    std::cout<< findLCM<54, 24>::result << std::endl; 

    return 0; 
} 

Answer 3

С C++ 11 вы можете использовать constexpr функции:

constexpr unsigned abs(int const op) { 
    return op >= 0 ? op : -op; 
} 

constexpr unsigned gcd(unsigned const a, unsigned const b) { 
    return b ? gcd(b, a % b) : a; 
} 

constexpr unsigned lcm(int const a, int const b) { 
    return abs(a * b)/gcd(abs(a), abs(b)); 
} 

Если вы хотите использовать шаблоны:

template <int Op> 
struct abs { 
    static constexpr unsigned const value{Op >= 0 ? Op : -Op}; 
}; 

template <unsigned A, unsigned B> 
static gcd : gcd<B, A % B> {}; 

template <unsigned A> 
static gcd<A, 0> { 
    static constexpr unsigned const value{A}; 
}; 

template <int A, int B> 
static lcm { 
    static constexpr unsigned const value{ 
     abs<A * B>::value/gcd<abs<A>::value, abs<B>::value>::value 
    }; 
};