Найти наибольший общий делитель для заданной последовательности чисел - C (СИ)
Формулировка задачи:
Дано натуральное число n и натуральные числа a1, a2, ..., an. Найти наиболее больший общий делитель для заданной последовательности. Рекомендовано применение алгоритма Евклида.
Решение задачи: «Найти наибольший общий делитель для заданной последовательности чисел»
textual
Листинг программы
#include<stdio.h>
int NOD(int,int);
int main(){
int n,i,a[120],delytel;
delytel=NOD(a[0],a[1]);
for(i=2;i<n;i++)
delytel=NOD(a[i],delytel);
printf("delytel=%d",delytel);
return 0;
}
int NOD(int x,int y){
metka:
if(x==0) return y;
if(y==0) return x;
(x>y)? x%=y: y%=x;
goto metka;
}
Объяснение кода листинга программы
- Включаем стандартную библиотеку ввода-вывода
- Объявляем функцию
NOD, которая принимает два целых числа и находит их наибольший общий делитель - В функции
mainобъявляем переменные: —n- количество чисел в массивеa—i- счётчик для цикла —a- массив для чисел —delytel- временная переменная для хранения НОД - Вызываем функцию
NODдля первых двух чисел из массиваaи сохраняем результат вdelytel - В цикле от 2 до
n-1проходим по всем элементам массиваa - Для каждого числа в массиве вызываем функцию
NODс этим числом и текущим значениемdelytel - Выводим значение
delytelна экран - Возвращаем 0 из функции
main, чтобы указать, что программа успешно завершилась