Форум программистов, компьютерный форум CyberForum.ru

Нахождение наибольшего общего делителя для 6-и чисел - C++

Восстановить пароль Регистрация
 
filosof_77
 Аватар для filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
10.10.2011, 18:49     Нахождение наибольшего общего делителя для 6-и чисел #1
привет!
у меня есть задача на нахождение наибольшего общего делителя для 6-и чисел ...
нашел было алгоритм ..

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream.h>
int nod(int,int);
main()
{
int x,y,t;
cout<<"vvedite chisla\n";
cin>>x>>y;
t=nod(x,y);
cout<<"nod="<<t<<"\n";
return 0;
}
int nod(int a,int b)
{
while(a!=b)
{
if(a>b)
a=a-b;
else b=b-a;
}
return a;
}

но думаю что он немножко медленный ... возможно кто может подсказать оптимальнее решение?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.10.2011, 18:49     Нахождение наибольшего общего делителя для 6-и чисел
Посмотрите здесь:

C++ Нахождение наибольшего общего делителя для элементов массива целых чисел
C++ Расчет наибольшего общего делителя двух натуральных чисел используя алгоритм эвклида
C++ Написать подпрограмму нахождения наибольшего общего делителя двух чисел
Написать программу вычисления наибольшего общего делителя двух целых чисел Dev C++ 4.9.9.2 C++
C++ Нахождение наибольшего общего делителя
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.10.2011, 18:58     Нахождение наибольшего общего делителя для 6-и чисел #2
C++
1
2
3
4
5
6
7
8
9
unsigned int Nod(unsigned int n, unsigned int m)
{
    while (n && m) 
        if (n >= m) 
           n %= m; 
        else 
           m %= n; 
    return m + n;
}
filosof_77
 Аватар для filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
11.10.2011, 09:37  [ТС]     Нахождение наибольшего общего делителя для 6-и чисел #3
C++
1
2
3
4
5
6
7
unsigned int Nod(unsigned int n, unsigned int m)
{
    if (m == 0)
        return n;
    else
        return Nod(m,n%m);
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2011, 09:40     Нахождение наибольшего общего делителя для 6-и чисел #4
filosof_77, оправданно ли использовать рекурсию для данной задачи, вряд ли
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
11.10.2011, 11:20     Нахождение наибольшего общего делителя для 6-и чисел #5
На wikipedia есть оптимизированная реализация НОД
Она еще шустрее чем пункт 2
alexcoder
1438 / 652 / 86
Регистрация: 03.06.2009
Сообщений: 3,293
Завершенные тесты: 1
11.10.2011, 12:11     Нахождение наибольшего общего делителя для 6-и чисел #6
Называется Алгоритм Евклида.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.10.2011, 12:15     Нахождение наибольшего общего делителя для 6-и чисел #7
C++
1
2
3
4
5
int gcd( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2011, 12:52     Нахождение наибольшего общего делителя для 6-и чисел #8
Цитата Сообщение от alexcoder Посмотреть сообщение
Называется Алгоритм Евклида.
А в постаx 2 и 3 разве не алгоритм Евклида Просто здесь обычный, а там бинарный. Проблема с бинарным алгоритмом Евклида такая, что из него нельзя построить расширенный алгоритм Евклида, но если это не нужно, то бинарный, наверное, лучше.
filosof_77
 Аватар для filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
11.10.2011, 14:49  [ТС]     Нахождение наибольшего общего делителя для 6-и чисел #9
это лабораторное задание .. думаю быстродействие алгоритма не является очень важным.!
но спасибо за столько примеров!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2011, 14:52     Нахождение наибольшего общего делителя для 6-и чисел
Еще ссылки по теме:

C++ Нахождение наибольшего общего делителя - почему выводит неверный итог?
Написать алгоритм нахождения наибольшего общего делителя трех чисел C++
C++ Нахождение наибольшего общего делителя и наименьшего общего кратного двух натуральных

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

Или воспользуйтесь поиском по форуму:
LosAngeles
Заблокирован
11.10.2011, 14:52     Нахождение наибольшего общего делителя для 6-и чисел #10
compile-time нод
C++
1
2
3
4
5
6
7
8
9
template <int x, int y> struct gcd
{
    static const int value = gcd<y, x % y>::value;
};
 
template <int x> struct gcd<x, 0>
{
    static const int value = x;
};
Yandex
Объявления
11.10.2011, 14:52     Нахождение наибольшего общего делителя для 6-и чисел
Ответ Создать тему
Опции темы

Текущее время: 04:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru