Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 Сокращение дробей(было: простые числа)   Evgeny Zhykh   15 Oct 2001 18:47:36 
 Сокращение дробей(было: простые числа)   Stanislav Shwartsman   15 Oct 2001 18:36:19 
 Сокращение дробей(было: простые числа)   Max Alekseyev   15 Oct 2001 15:26:08 
Архивное /ru.algorithms/17853bcb2cb1.html, оценка 1 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional