Задача

Найти НОД (наибольший общий делитель ) $n$ чисел.

Входные данные

Первая строка содержит количество чисел [latex]n \left(1 < n < 101\right)[/latex]. Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает [latex]30000[/latex].

Выходные данные

НОД заданных чисел.

Тесты

#	Входные данные	Выходные данные
1	3 5 7 2	1
2	2 45 10	5
3	4 27 90 15 9	3
4	2 40 64	8
5	3 8 8 8	8

Код

#include <iostream>
using namespace std;
int gcd (int a, int b) {
    while (a!=0 && b!=0) {
        if (a>b) {
            a=a%b;
        }
        else b=b%a;
    }
    return a+b;
}

int main () {
    int t, a, b;
    cin>>t>>b;
    for (int i=2; i<=t; ++i) {
        cin>>a;
        b=gcd (a, b);
    }
    cout<<b;
    return 0;
}

#include <iostream>

using namespace std;

int gcd (int a, int b) {

while (a!=0 && b!=0) {

if (a>b) {

a=a%b;

}

else b=b%a;

}

return a+b;

}

int main () {

int t, a, b;

cin>>t>>b;

for (int i=2; i<=t; ++i) {

cin>>a;

b=gcd (a, b);

}

cout<<b;

return 0;

}

Решение задачи

Для решения данной задачи воспользуемся алгоритмом Евклида — алгоритмом нахождения наибольшего общего делителя (НОД) пары целых чисел, т.е. самого большого числа, на которое можно без остатка разделить оба числа, для которых ищется НОД.

Условие задачи на e-olymp
Код решения на ideone

Related Images:

Похожее

А зачем Вам так жонглировать res=gcd (a, b); b=res;? Сразу положить в нужную переменную нельзя?
Поставьте, пожалуйста, пробелы с обоих сторон знаков операций. Не так страшно, но раз всё равно переделывать…
Решение ничего не решает. Вы просто словами описали программу, а не алгоритм. И то с неточностями. Например, Вы находите не gcd(a, b, c), gcd(gcd(a, b), c). И это правильно. Но нужно же написать об этом и пояснить, почему результат будет тот же.
Там, где в программе используется какой-то не очевидный трюк (например, здесь return a+b;) обязательно должно быть пояснение.
Если в теле цикла или условного оператора присутствует только один оператор, его можно не брать в фигурные скобки. А можно и брать. Вы так и делаете — то берете, то нет. Определитесь.
Вы не рекурсивно реализовали алгоритм Евклида. Либо опишите алгоритм, либо дайте ссылку на него.

Когда человек пересказывает словами код, но не говорит об алгоритмах, которые реализованы, это производит плохое впечатление. Чаще всего преподаватель с этим сталкивается, когда студент-двоечник принес чужой код и ничего в нем не понимает. Это ведь не Ваш случай, правда?

2 thoughts on “e-olymp 571. НОД”

Мазурок Игорь Евгеньевич says: 27/12/2017 at 13:07
- А зачем Вам так жонглировать res=gcd (a, b); b=res;? Сразу положить в нужную переменную нельзя?
- Поставьте, пожалуйста, пробелы с обоих сторон знаков операций. Не так страшно, но раз всё равно переделывать…
- Решение ничего не решает. Вы просто словами описали программу, а не алгоритм. И то с неточностями. Например, Вы находите не gcd(a, b, c), gcd(gcd(a, b), c). И это правильно. Но нужно же написать об этом и пояснить, почему результат будет тот же.
- Там, где в программе используется какой-то не очевидный трюк (например, здесь return a+b;) обязательно должно быть пояснение.
- Если в теле цикла или условного оператора присутствует только один оператор, его можно не брать в фигурные скобки. А можно и брать. Вы так и делаете — то берете, то нет. Определитесь.
- Вы не рекурсивно реализовали алгоритм Евклида. Либо опишите алгоритм, либо дайте ссылку на него.
Когда человек пересказывает словами код, но не говорит об алгоритмах, которые реализованы, это производит плохое впечатление. Чаще всего преподаватель с этим сталкивается, когда студент-двоечник принес чужой код и ничего в нем не понимает. Это ведь не Ваш случай, правда?

Войдите, чтобы ответить
Мазурок Игорь Евгеньевич says: 13/05/2018 at 09:59

Зачтено.
Но почти 5 (пять!) месяцев между моим замечанием и Вашей реакцией на него это много.
Ну и для полноты стоит отметить, что есть рекурсивная реализация алгоритма Эвклида, которая выглядит лаконичнее, хотя не лишена недостатков всех рекурсивных функций

C++

int gcd(const int& a, const int& b) { return b? gcd(b, a % b): a; }

1
2
3

int gcd(const int& a, const int& b) {
return b? gcd(b, a % b): a;
}

Войдите, чтобы ответить