-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
1

НОД нескольких чисел используя метод Евклида

12.01.2020, 20:01. Показов 5609. Ответов 20
Метки нет (Все метки)

Проходит только 14 тестов из 32. Без массивов пожалуйста
Напишите функцию для нахождения наибольшего общего делителя двух чисел с помощью алгоритма Евклида и используйте ее в программе для нахождения НОД уже n чисел.

Входные данные
На вход программе сначала подается значение n (2<n<100). В следующей строке находятся n целых неотрицательных чисел, не превосходящих 30000.

Выходные данные
Выведите НОД исходных чисел.

Добавлено через 12 минут
Можно с массивами
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2020, 20:01
Ответы с готовыми решениями:

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

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

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

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

20
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:09 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int n, a[100];
int gcd(int a, int b){
    while(b){
        a%=b;
        swap(a,b);
    }
    return a;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    int gcdans=a[0];    
    for(int i=1;i<n;i++){
        gcdans=gcd(gcdans,a[i]);
    }
    cout<<gcdans;
    return 0;
}
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 20:11 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
            a %= b;
        else
            b %= a;
    return a | b;
}
int main()
{
    size_t n;
    std::cin >> n;
    int nod;
    std::cin >> nod;
    for (size_t i = 1; i < n; i++)
    {
        int temp;
        std::cin >> temp;
        nod = Nod(temp, nod);
    }
    std::cout << nod;
}
Добавлено через 44 секунды
Цитата Сообщение от 1233211212 Посмотреть сообщение
Можно с массивами
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:14  [ТС] 4
Если можете подскажите что не так
Правильны только 31 теста из 32-ух


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    long long n, min1 = 999999999, max1 = 0;
    cin >> n;
    vector <int> a(n);
    for (int i = 0; i <= n - 1; i++) {
        cin >> a[i];
        if (a[i] < min1 && a[i] != 0)
            min1 = a[i];
        if (a[i] > max1)
            max1 = a[i];
        while (min1 != 0 && max1 != 0) {
            if (min1 > max1)
                min1 = min1 - max1;
            else max1 = max1 - min1;
        }
    }
    cout << min1 + max1;
 
}
0
случайный прохожий
2228 / 1468 / 503
Регистрация: 20.07.2013
Сообщений: 4,159
12.01.2020, 20:17 5
http://algolist.manual.ru/maths/teornum/nod.php
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:18 6
Скинь ссылку на задачу т. к. не понятно. Ведь могло быть переполнение или не правильно константу max/min сделал
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:20  [ТС] 7
https://informatics.mccme.ru/m... rid=3023#1
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:25 8
Вот тест: 3 0 0 0 Найди ошибку сам)(Я её знаю)
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:32  [ТС] 9
Все равно 31
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:32 10
А ты пытался мое решение отправить?
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:35  [ТС] 11
Мне просто нельзя использовать твое решение т.к. мы не проходили ничего дальше вектора и массивов. И мне желательно нужно такое же оформление как у меня
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:42 12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    long long n;
    cin>>n;
    vector<int> a(n);
    int gcd=-1;
    for (int i = 0; i <= n - 1; i++) {
        cin >> a[i];
        if( gcd == -1 ){
            gcd=a[i];
        }else{
            gcd=__gcd(gcd,a[i]);
        }
    }
    cout << gcd;
 
}
Вот решение с стандартной функцией и без алгоритма
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 21:02  [ТС] 13
Ошибка компиляции
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 21:07 14
Цитата Сообщение от 1233211212 Посмотреть сообщение
Мне просто нельзя использовать твое решение т.к. мы не проходили ничего дальше вектора и массивов. И мне желательно нужно такое же оформление как у меня
В чём проблема моего решения? Я не использую массивы, вектора, алгоритмы
Тут обычная рекурсия
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
            a %= b;
        else
            b %= a;
    return a | b;
}
int main()
{
    size_t n;
    std::cin >> n;
    int nod;
    std::cin >> nod;
    for (size_t i = 1; i < n; i++)
    {
        int temp;
        std::cin >> temp;
        nod = Nod(temp, nod);
    }
    std::cout << nod;
}
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 21:07  [ТС] 15
Спасибо, прошло
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 21:08 16
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
Вот решение с стандартной функцией и без алгоритма
__gdc() это что и где оно определено?
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 21:56 17
__gcd() находится в компиляторе gcc и считает нод двух чисел
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 22:03 18
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
__gcd() находится в компиляторе gcc
А если у ТС не gcc?
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 22:23 19
Я не знаю, всегда пользуюсь gcc т.е. компилирует быстрее
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 23:23 20
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
Я не знаю, всегда пользуюсь gcc т.е. компилирует быстрее
Википедия: "Некоторые разработчики OpenBSD, например Тео де Раадт и Отто Мурбек (Otto Moerbeek), критикуют GCC, называя его «громоздким, глючным, медленным и генерирующим плохой код»"

И лучше не использовать особенности компилятора, допустим вам нужно будет перейти на другой компилятор и много чего нужно менять, а тем более на форуме, где новички просят помощи и не знают почему у них ошибка
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2020, 23:23
Помогаю со студенческими работами здесь

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

НОД двух чисел алгоритм Евклида
Найти найбольший общий делитель двух чисел по алгоритму Евклида. Использовать рекурсию.

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

Найти НОД двух целых чисел по алгоритму Евклида.
задание: Найти НОД двух целых чисел по алгоритму Евклида.

Последовательность натуральных чисел, вычисление их НОД методом Евклида
Уважаемые форумчане, прошу помощи в решении задачи: Составьте программу, которая позволяет...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru