ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Denes Raskovalov                     2:5080/169.35  08 May 2001  04:48:35
 To : Aleksey Malov
 Subject : НОК
 -------------------------------------------------------------------------------- 
 

 
  AK>>> Каким образом можно найти сабж для N многочленов ?
  DR>> HОК(f, g) = f*g / HОД(f, g)
  DR>> HОД ищется банальным делением в столбик.
 
  AM>   Можно HОД вообще без деления найти:
  AM> int nod (int A, int B)
  AM> {
  AM>  while (A!=B)
  AM>  {
  AM>   if (A>B) A -= B
  AM>     else
  AM>    B -= A;
  AM>  }
  AM>  return A;
  AM> }
 
 Я бы хотел посмотреть, как ЭТО будет работать для многочленов.
 Hу а если сравнивать алгоритм Евклида и "твой", то сравнение, для маломальки
 больших чисел, будет явно не в твою пользу. Если числа, обрабатываемые
 алгоритмом Евклида, равны a и b, то
 
     Алгоритму Евклида требуется не более:
                 [log(sqrt(5*max(a,b)))] - 2,
 
 где [x] - наименьшее целое число, большее x
 log(x) - логарифм x по основанию (1+sqrt(5))/2
 
     А твой, фактически, каждый шаг алгоритма Евклида разворачивает в линейный по
 a и b алгоритм.
 
 Bye, Aleksey.
 
 --- Здесь будет город заложен. И тут же продан и сожжен...
  * Origin: Все равно MustDie не брошу, потому что он хороший... (2:5080/169.35)
 
 

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

Тема:    Автор:    Дата:    НОК   Denes Raskovalov   06 May 2001 01:01:25   НОК   Aleksey Malov   07 May 2001 12:11:03   Re: ОК   Yuriy Kaminskiy   08 May 2001 17:14:32   НОК   Denes Raskovalov   08 May 2001 04:48:35   НОК   Aleksey Malov   12 May 2001 15:58:59