Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.89/47: Рейтинг темы: голосов - 47, средняя оценка - 4.89
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19

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

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

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

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

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

Добавлено через 12 минут
Можно с массивами
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
12.01.2020, 20:01
Ответы с готовыми решениями:

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

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

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

20
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:09
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
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  [ТС]
Если можете подскажите что не так
Правильны только 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
place status here
 Аватар для gunslinger
3186 / 2220 / 640
Регистрация: 20.07.2013
Сообщений: 6,010
12.01.2020, 20:17
http://algolist.manual.ru/maths/teornum/nod.php
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:18
Скинь ссылку на задачу т. к. не понятно. Ведь могло быть переполнение или не правильно константу max/min сделал
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:20  [ТС]
https://informatics.mccme.ru/m... rid=3023#1
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:25
Вот тест: 3 0 0 0 Найди ошибку сам)(Я её знаю)
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:32  [ТС]
Все равно 31
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:32
А ты пытался мое решение отправить?
0
-4 / 0 / 0
Регистрация: 27.11.2019
Сообщений: 19
12.01.2020, 20:35  [ТС]
Мне просто нельзя использовать твое решение т.к. мы не проходили ничего дальше вектора и массивов. И мне желательно нужно такое же оформление как у меня
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 20:42
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  [ТС]
Ошибка компиляции
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 21:07
Цитата Сообщение от 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  [ТС]
Спасибо, прошло
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 21:08
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
Вот решение с стандартной функцией и без алгоритма
__gdc() это что и где оно определено?
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 21:56
__gcd() находится в компиляторе gcc и считает нод двух чисел
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 22:03
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
__gcd() находится в компиляторе gcc
А если у ТС не gcc?
0
0 / 0 / 0
Регистрация: 04.11.2019
Сообщений: 12
12.01.2020, 22:23
Я не знаю, всегда пользуюсь gcc т.е. компилирует быстрее
0
653 / 466 / 183
Регистрация: 23.04.2019
Сообщений: 1,987
12.01.2020, 23:23
Цитата Сообщение от vitaminka1234 Посмотреть сообщение
Я не знаю, всегда пользуюсь gcc т.е. компилирует быстрее
Википедия: "Некоторые разработчики OpenBSD, например Тео де Раадт и Отто Мурбек (Otto Moerbeek), критикуют GCC, называя его «громоздким, глючным, медленным и генерирующим плохой код»"

И лучше не использовать особенности компилятора, допустим вам нужно будет перейти на другой компилятор и много чего нужно менять, а тем более на форуме, где новички просят помощи и не знают почему у них ошибка
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
12.01.2020, 23:23
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru