Рассчитайте 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;
}

c++ lcm
person Sid    schedule 29.03.2016    source источник
comment
какой алгоритм вы используете?   -  person max66    schedule 29.03.2016
comment
Если вы расширите шаблоны вручную, они: findLCM<54, 24, <findMax<54,s4>::value>> = findLCM<54,24,54> => findLCM<54%54, 54%24, 55> == findLCM<0,6,55> => findLCM<0,55%6, 56> == findLCM<0,1,56> => findLCM<0,56%1, 57> == findLCM<0,0,57> => 57 Две проблемы, которые я вижу: вы используете алгоритм Эйлера для GCD, и вы поняли его (немного) неправильно.   -  person Martin Bonner supports Monica    schedule 29.03.2016
comment
пожалуйста, выберите более описательный заголовок   -  person 463035818_is_not_a_number    schedule 29.03.2016
comment
Кстати, в C++14 все это можно реализовать в виде крошечной функции constexpr.   -  person Anton Savin    schedule 29.03.2016
comment
Упс. Вместо Эйлера читайте Евклида. Оба великие математики, но один немного раньше другого.   -  person Martin Bonner supports Monica    schedule 29.03.2016

Ответы (3)


arrow_upward
3
arrow_downward

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

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

person Martin Bonner supports Monica    schedule 29.03.2016
comment
Привет Мартин, спасибо за ваш ответ. На самом деле, я не основываю это на НОД, хотя знаю, что НОД можно вывести из НОД, как вы изобразили. - person Sid; 29.03.2016
comment
Все, что я хотел, это написать TMP на основе простой программы, как показано ниже, для вычисления LCM во время компиляции. - person Sid; 29.03.2016
comment
int main() { int n1, n2, max; cout ‹‹ Введите два числа: ; cin ›› n1 ›› n2; макс = (n1 › n2) ? п1 : п2; // максимальное значение между n1 и n2 хранится в max do { if (max%n1 == 0 && max%n2 == 0) { cout ‹‹ LCM = ‹‹ max; перемена; } иначе ++max; } пока (истина); вернуть 0; } - person Sid; 29.03.2016
comment
В этом случае вам нужно где-то сделать умножение. Вы продолжаете брать модули (что уменьшит ваш аргумент, но увеличится только на единицу). - person Martin Bonner supports Monica; 29.03.2016

arrow_upward
0
arrow_downward

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

#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;
}
person max66    schedule 29.03.2016

arrow_upward
0
arrow_downward

С С++ 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
    };
};
person kamikaze    schedule 29.03.2016