НОД и НОК для массива
Напомню, что НОД (наибольший общий делитель, GCD) для натуральных чисел A и B - максимальное из чисел, на которые A и B делятся без остатка, НОК (наименьшее общее кратное, LCM) - минимальное из чисел, которые делятся на A и B без остатка. Можно реализовать простой и удобный алгоритм поиска НОД и НОК для пары чисел, а для массива натуральных чисел у народа почему-то вызвало затруднения. Между тем, вот такое решение кажется мне простым и правильным:
#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) или nod(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); }
03.12.2012, 08:46; рейтинг: 14429