Задача
Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.
Входные данные
Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.
Выходные данные
НОД заданных чисел.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | 2 15 25 |
5 |
| 2 | 3 99 358 2 |
1 |
| 3 | 5 81 99 72 108 36 |
9 |
| 4 | 2 25 50 |
25 |
| 5 | 4 132 36 66 18 |
6 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> using namespace std; int gcd(int a, int b) { return (a == 0) ? b: gcd(b % a, a); } int main() { int n, m = 0; cin >> n; for (int i = 0; i < n; i++) { int a; cin >> a; m = gcd(m, a); } cout << m; return 0; } |
Решение
Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.
Запустить код (ideone) можно здесь
Задача на E-olymp
Не существенно, конечно, но возможно лучше было бы в функции «nod» сделать одно ветвление через тернарную операцию. По сути, оно у вас там итак имеется. Вы возвращаете либо значение переменной, либо значение функции. Предлагаю просто это оформить несколько понятнее
Спасибо, воспользовался вашим предложением)
Вы полагаете, что название функции nod() лучше, чем stipendija?