Найти наименьшее общее кратное в массиве

Авторизуйтесь или зарегистрируйтесь, чтобы добавить комментарий
Evgeniy Chumakov
2636
Evgeniy Chumakov  

Если кому не трудно помочь написать код или может уже у кого есть (желательно что бы работал в MT4) нахождения наименьшего общего кратного в массиве.


Есть массив с числами (числа большие , от 20 000 до 200 000 примерно)

double ARRAY_NOK[];
ArrayResize(ARRAY_NOK,7,0);


Пробовал всякие методы перебора - считает долго 

Пробовал путём последовательного нахождения НОК - в результате получаю единицу.


На сайтах по расчёту ввожу данные , всё считается нормально и мгновенно.


Собственно хочется пример быстрой реализации нахождения НОК.


Спасибо!

Nikolai Semko
6569
Nikolai Semko  
Evgeniy Chumakov:

Пробовал путём последовательного нахождения НОК - в результате получаю единицу.

попробуйте поменять тип double на int

Evgeniy Chumakov
2636
Evgeniy Chumakov  
Nikolai Semko:

попробуйте поменять тип double на int


Не знаю в чем дело , получается 1. Может неправильно считаю

Вот ряд чисел

100000, 100000, 12500, 50000, 27051, 24893, 26673


Считаю на сайте выдаёт следущий результат


Georgiy Merts
9179
Georgiy Merts  
Evgeniy Chumakov:


Считаю на сайте выдаёт следущий результат


Евгений пишет правильно нельзя вычислять НОК у дробных значений.

А так... Стандартный алгоритм для группы чисел...

Evgeniy Chumakov
2636
Evgeniy Chumakov  
Georgiy Merts:

Евгений пишет правильно нельзя вычислять НОК у дробных значений.

А так... Стандартный алгоритм для группы чисел...


int пробовал , тоже не получается.

Nikolai Semko
6569
Nikolai Semko  
Evgeniy Chumakov:


int пробовал , тоже не получается.

еще необходимо вместо деления / использовать % - остаток от деления.

Не забывайте, что деление двух int дает тоже int. Например 7/2=3, а 7/2.0=3.5 или 7.0/2=3.5

Alexey Viktorov
25689
Alexey Viktorov  
Nikolai Semko:

еще необходимо вместо деления / использовать % - остаток от деления.

Не забывайте, что деление двух int дает тоже int. Например 7/2=3, а 7/2.0=3.5 или 7.0/2=3.5

Если не ошибаюсь, тоже вряд-ли поможет. % возвращает целое при делении целого на целое. Тут скорее всего надо использовать fmod() которое возвращает вещественный остаток от деления двух чисел.

Nikolai Semko
6569
Nikolai Semko  
Alexey Viktorov:

Если не ошибаюсь, тоже вряд-ли поможет. % возвращает целое при делении целого на целое. Тут скорее всего надо использовать fmod() которое возвращает вещественный остаток от деления двух чисел.

 В данной задаче не должно быть никаких double, поэтому эта функция никаким боком. 
Нужна только сортировка массива, удаление повторяющихся элементов, умножение и операция % для проверки 
ЗЫ просто не за компом. Написал бы уже давно. Здесь делов то на 5 минут
Georgiy Merts
9179
Georgiy Merts  

Ну, друзья даете...

Простейшая же функция !

ulong _LeastCommonMultiple(ulong ulA,ulong ulB) { return (ulA/_GreaterCommonDivisor(ulA,ulB) * ulB); }


// Функция _GreaterCommonDivisor - функция нахождения наибольшего общего делителя

Функция _GreaterCommonDivisor (cо служебными) :

// Проверка на нечетность
bool _IsOdd(ulong ulNumber) { return((bool)(ulNumber & 1));  };

// Проверка на четность
bool _IsEven(ulong ulNumber) { return(!_IsOdd(ulNumber)); };

// Основная функция нахождения общего делителя
ulong _GreaterCommonDivisor(ulong ulFirst,ulong ulSecond)
{
   if(ulFirst == 0) return(ulSecond);        // 1 

   if(ulSecond == 0) return(ulFirst);        // 1 

   if(ulFirst == ulSecond) return(ulFirst);  // 1 

   if(ulFirst == 1 || ulSecond == 1)   return(1);  // 2

   if(_IsOdd(ulFirst))  // Если нечетное
      if(_IsOdd(ulSecond)) // Если нечетное
         if(ulFirst > ulSecond)
            return(_GreaterCommonDivisor((ulFirst-ulSecond) >> 1,ulSecond)); // 7
         else
            return(_GreaterCommonDivisor(ulFirst,(ulSecond-ulFirst) >> 1)); // 6
      else
         return(_GreaterCommonDivisor(ulFirst,ulSecond >> 1)); // 5
   else   
      if(_IsOdd(ulSecond)) // Если нечетное
         return(_GreaterCommonDivisor(ulFirst >> 1,ulSecond)); // 4
      else
         return(_GreaterCommonDivisor(ulFirst >> 1,ulSecond >> 1) << 1); // 3
      
   return(0);      
};
Alexey Viktorov
25689
Alexey Viktorov  
Nikolai Semko:
 В данной задаче не должно быть никаких double, поэтому эта функция никаким боком. 
Нужна только сортировка массива, удаление повторяющихся элементов, умножение и операция % для проверки 

Ну, тады ой.

Evgeniy Chumakov
2636
Evgeniy Chumakov  
Georgiy Merts:

Ну, друзья даете...

Простейшая же функция !

Функция _GreaterCommonDivisor (cо служебными) :


Нужно найти НОК , а не НОД

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