БлогNot. НОД и НОК для массива

Помощь дата->рейтинг Поиск Почта RSS канал Статистика nickolay.info Домой

НОД и НОК для массива

Напомню, что НОД (наибольший общий делитель) для натуральных чисел A и B - максимальное из чисел, на которые A и B делятся без остатка, НОК (наименьшее общее кратное) - минимальное из чисел, которые делятся на 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);
}

теги: алгоритм числа c++

Здесь можно оставить коментарий, обязательны к заполнению только красные поля. Не пишите лишнего, и всё будет хорошо :)

Ваше имя:
Пароль (если желаете зарегистрировать имя):
Любимый URL (если указываете, то вставьте полностью):
Текст сообщения (до 1024 символов):
 
Введите код сообщения: 3877
 

03.12.2012, 08:46; рейтинг: 11135

  свежие записипоиск по блогукомментироватьстатистика

Наверх Яндекс.Метрика
© PerS
вход