Nickolay.info. Алгоритмы. Наибольший общий делитель (алгоритм Евклида) и Наименьшее общее кратное

Пожалуй, одна из самых классических задач: заданы значения X и Y, найти их наибольший общий делитель (алгоритм Евклида). Красивее всего из массовых языков выглядит, видимо, на Си.

#include <stdio.h>

void main () {
 int x=24, y=36; //Задание чисел X и Y, для которых ищется НОД
 while (x && y) {
  if (x>y) x%=y; else y%=x;
  }
  printf ("\n%d",x+y);
}

А можно сделать ещё красивее, написав рекурсивную функцию nod(x,y). Тогда главная программа сведётся к одному оператору печати.

#include <stdio.h>

int nod (int x, int y) {
 return (x==0 ? y : nod(y%x,x) );
}

void main () {
 int x=24, y=36;
 printf ("\n%d",nod(x,y));
}

Уместно вспомнить и о тесно связанной с определением НОД задаче поиска НОК - наименьшего общего кратного двух чисел. Постановка такая: для 2 натуральных чисел ищется наименьшее число, которое делится без остатка на исходные числа. К предыдущей программе понадобится дописать всего одну маленькую функцию.

#include <stdio.h>

int nod (int x, int y) {
 return (x==0 ? y : nod(y%x,x) );
}

int nok (int x, int y) {
 return x/nod(x,y)*y;
}

void main () {
 int x=24, y=36;
 printf ("\n%d",nok(x,y));
}

Легко ли найти НОД и НОК для массивов? Да, не многим сложнее, чем для пары чисел. Ниже предлагается соответствующая реализация. Функции nod и nok в ней ещё немного сокращены, проверки корректности данных не делаются, но результаты пишутся всё же в long int, т.к. НОК может оказаться достаточно велик и "вылезти" за диапазон int даже для небольших значений в исходных данных.

#include <stdio.h>

//Реализация для 2 чисел
long int nod (int x, int y) { return (x?nod(y%x,x):y); }
long int nok (int x, int y) { return x*y/nod(x,y); }
//и вернуть nok(x,y)

void main () {
 const int n=5;
 int a[n]={24,36,144,48,72},i;
 //НОД для массива:
 long int nd=a[0];
 for (i=1; i<n; i++) nd=nod((nd<a[i]?nd:a[i]),(nd<a[i]?a[i]:nd));
 printf ("\nNOD=%ld",nd);
 //НОК для массива:
 long int nk=1;
 for (i=0; i<n; i++) nk=nok(nk,a[i]);
 printf ("\nNOK=%ld",nk);
}

Рейтинг@Mail.ru

вверх гостевая; E-mail