VPF::НОД и НОК.. - Форум программистов

Kurt

Дата 16.3.2004, 16:07 (ссылка)

(нет голосов)

Загрузка ...

Увлеченный

Профиль
Группа: Участник Клуба
Сообщений: 1662
Регистрация: 22.8.2003
Где: Краснодар

Репутация: нет
Всего: 36

Народ, мне срочнейше требуются алгоритмы для вычисления наибольшего общего делителя и наименьшего общего кратного для ТРЕХ чисел.
Плиз, кто знает, помогите - ОЧЕНЬ надо!!!
Заранее спасибо.

--------------------

Для корабля, который не знает куда плыть, нет попутного ветра... ((С) Архимед)
...
Все знают, что это невозможно. Но случайно находится невежда, который этого не знает. Он-то и делает открытие.. ((С) А. Эйнштейн)

Lan

Дата 16.3.2004, 16:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 159
Регистрация: 12.3.2004
Где: Владимир

Репутация: нет
Всего: 1

Иногда гугл помогает найти быстрее, чем просто самому придумывать и записывать алгоритм

http://ru.laser.ru/authors/rou/mk/1.htm#n7
Добавлено @ 16:25
Посмотрел на алгоритмы. Похожи на настоящие, работающие...

Это сообщение отредактировал(а) Lan - 16.3.2004, 16:26

Kurt

Дата 17.3.2004, 00:33 (ссылка)

(нет голосов)

Загрузка ...

Увлеченный

Профиль
Группа: Участник Клуба
Сообщений: 1662
Регистрация: 22.8.2003
Где: Краснодар

Репутация: нет
Всего: 36

Спасибо!
Этим и ограничимся..

Я уже переписал их на С++.
Вот только я думал, можь, есть какие хитрые алгоритмы?
Побыстрее, чем обычный перебор?

--------------------

Lan

Дата 17.3.2004, 02:03 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 159
Регистрация: 12.3.2004
Где: Владимир

Репутация: нет
Всего: 1

Я подумаю насчёт математического метода... Что-нибудь типа "алгоритма Евклида для трёх чисел". Если придумаю, напишу.

Но пока, можно сказать, что можно совместить перебор с алгоритмом Евклида для двух чисел. Искать НОД для двух чисел, потом "примерять" его к третьему числу.

По сути, получаем оптимизированный перебор.

sergejzr

Дата 12.10.2004, 17:46 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 4
Всего: 360

Не шедевр конечно, но всё же кое что..

Код

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
/*
НОД - ggT (groesster gemeinsamer Teiler)
НОК - kgV (kleinstes gemeinsames Vielfaches)
*/
int ggT(int a,int b);
int ggT(int a,int b,int c);

int kgV(int a,int b);
int kgV(int a,int b,int c);

//НОД(a, b, c)=НОД(a, НОД(b, c))
int ggT(int a,int b,int c)
{
 return ggT(a,ggT(b,c));
}

//Единственное, что пришло в голову
//НОК(a, b)  =  a·b / НОД(a, b)
//НОК(a, b,c)  =НОК(a, НОК(b, c) ) =
//a·b*c/НОД(b, c) / НОД(a, b*c/НОД(b, c) )
int kgV(int a,int b,int c)
{
int x=(b*c)/ggT(b,c);
return (a*x)/ggT(a,x);
}

int ggT(int x, int y)
{
    int rest;
    do
    {
      rest = x % y;
      x = y;
      y = rest;
    } while (rest!=0);

    return x;
  }

int kgV(int x, int y)
  {
   
    return (x*y) / ggT(x,y);
  }

int main(int argc,char**argv)
{
int a,b,c;
if(argc<4)
{
 printf("Use %s [a][b][c]\n",argv[0]);
 return 1;
}
a=atol(argv[1]);
b=atol(argv[2]);
c=atol(argv[3]);
    printf("NOD(%d,%d,%d)=%d\nNOK(%d,%d,%d)=%d\n",a,b,c,ggT(a,b,c),a,b,c,kgV(a,b,c));
return 0;
}

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Akina

Дата 19.10.2004, 14:18 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Обычная рекурсия.

НОД(А, В, С) = НОД(А, НОД(В, С))
НОК(А, В, С) = НОК(А, НОК(В, С))

Кстати.

НОК(А, В) * НОД(А, В) = А * В

Но это уже к слову...

Это сообщение отредактировал(а) Akina - 19.10.2004, 14:20

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Ailij

Дата 22.10.2004, 16:02 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Все очень просто:

Код



int NOD(int x, int y)
{
   while (x && y)
       if (x > y) x %= y; 
       else y %= x;

   return x > y ? x : y;
}

int NOK(int x, int y)
{
    return x * y / NOD(x, y);
}

int NOD(int x, int y, int z)
{
    return NOD(NOD(x, y), z);
}

int NOK(int x, int y, int z)
{
   return NOK(NOK(x, y), z);
}

Понятно, что все аргументы для NOD должны быть неотрицательны, а для NOK - положительны

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »