Специализни шаблонца!

Previous Entry Поделиться Next Entry
Дробная арифметика
Vash
udpn
Ребе [info]nicka_startcev задал любопытный вопрос:

Какое наименьшее общее кратное у 6 и 7.2 ?

"Хм" подумал я, и набросал следующее.

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

struct double_ {
    double val;
    double_(double val = 0) : val(val) {}
    operator double() { return val; }
};
double_ operator % (double_ x, double_ y) {
    return x - y * int(x / y);
}
const double eps = 1e-10;
double_ gcd(double_ x, double_ y) {
    while (fabs(y) > eps) {
        double r = x % y;
        x = y;
        y = r;
    } return x;
}
double_ lcm(double_ x, double_ y) {
    return x * y / gcd(x, y);
}

int main() {
    double_ a = 6.0, b = 7.2;
    cout << lcm(a, b) << endl;
    system("pause");
}

Внезапно, 36.

  • 1
А не проще было 7.2 представить в виде обычной дроби (72/10), сократить ее (36/5), привести 6 к тому же знаменателю (30/5), а затем спокойно (в уме) найти НОК числителей?

Да мне думать лень было. А определения (%) и GCD я наизусть помню, их писать легко.

Да и не подходит ваш метод для произвольных double'ов.

Ох, ну даблы это вообще не числа. Там операции неассоциативны, говорить дальше с ними не о чем.

Ну, что считать числами. Кольцо? Поле? Натуральных, целых, рациональных и вещественных чисел, как известно, в компьютере не бывает...

например, "числа произвольной точности" (натуральные, целые, рациональные) -- про них есть утверждение: если все промежуточные результаты помещаются в памяти, то все законы арифметики верны, в том числе, (a+b)-b == a. Про даблы даже такое неверно, а ведь всего-то сложение и вычитание.
Кроме того, есть символьные представления вещественных чисел, но про них не буду, ибо не компетентен.

Подходит. У даблов точность ограничена, так что к обыкновенным дробям они точно приводятся.

только вот результат будет не тот, что нужен. Если даже в точность впишется (вроде впишется gcd), то будет найден gcd (lcm) результата приближения входных дробей дробями вида n/2^m. Как думаешь, зачем автор птсо ввёл эпсилон -- не для 7.2 ли, случаем? :)

Да это-то как бэ понятно.
Только тут точность нипоцтрадает при вводе-выводе-переводе, а не при расчётах.

так а какой смысл вести рощот, если при вводе уже лажа, с которой дальше работает алгоритм?

На самом деле, тут нужна просто другая процедура ввода, которая вводила бы 7.2 без всяких double, напрямую во frac(72, 10). Что касается кода, то Страуструп давно предлагает ввести перегрузку литералов.

Да-да, я бы ещё процедуру приведения double к наиболее близко расположенному frac через деревья Штерна-Броко писал шолле?
Так, как здесь, проще всего. Можете оспорить.

Ну, на Project Euler не запрещено простые задачки брутфорсить.

(Удалённый комментарий)

Ох, ну прискипался

Ну по меньшей мере потому, что

mod, div, gcd :: Integral a => a -> a -> a.

(Удалённый комментарий)

Re: Ох, ну прискипался

Да ну на С++ по-прежнему быстрее. Синоним типа набросал и всё.

И вообще, кто из нас хаскеллист? )

  • 1
?

Log in