|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Stanislav Shwartsman 2:400/520 15 Oct 2001 18:36:19 To : Evgeny Zhykh Subject : Сокращение дробей(было: простые числа) -------------------------------------------------------------------------------- 15 Oct 01 18:47, you wrote to All: EZ> Как _оптимально_ можно сократить дробь? Есть идея - с помощью простых EZ> чисел - но не уверен что оптимально. Hайти GCD (greatest common divisor, HОК по русски) числителя и знаменателя с помощью алгоритма Эвклида и разделить обоих на это число. Время работы этого алгоритма O(log N), N = max(a,b). Пример: кусок кода из моего класса Rational. num, denum - чиститель и знаменатель соответственно. === Cut === #include <stdlib.h> #include "rational.hpp" void TRational :: reduce(void) { if(denum < 0) { num = -num; denum = -num; } if(num == 0) denum = 1; else { long bigdiv = gcd(abs(num), denum); if(bigdiv > 1) { num /= bigdiv; denum /= bigdiv; } } } long TRational :: gcd(long a, long b) const { while (b!=0) { int c = a % b; a = b; b = c; } return a; } === Cut === E-mail: gate@fidonet.org.il Voice Phones: 972-4-8330554 (home), 972-5-4481073 (cell) Bye ! Stanislav (AKA Night's Man) [Team Technion] --- * Origin: Gate From Another World ... From Haifa, Israel (2:400/520) Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/17853bcb2cb1.html, оценка из 5, голосов 10
|