Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
#1

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

10.10.2011, 18:49. Просмотров 872. Ответов 9
Метки нет (Все метки)

привет!
у меня есть задача на нахождение наибольшего общего делителя для 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;
}

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

Нахождение наибольшего общего делителя для элементов массива целых чисел - C++
Написать программу нахождения наибольшего общего делителя для элементов массива целых чисел буду признателен, если поможете. Написать...

Нахождение наибольшего общего делителя двух натуральных чисел - C++
1)Используя функцию NOD нахождения наибольшего общего делителя двух натуральных чисел, сократить данную обычную дробь M / N. / /...

Нахождение наибольшего общего делителя и наименьшего общего кратного двух натуральных - C++
Составить программу для нахождения наибольшего общего делителя и наименьшего общего кратного двух натуральных чисел (НОК(А,В)= А*В/ НОД...

Нахождение наибольшего общего делителя - C++
Borland C++ Найти наибольший общий делитель двух натуральных чисел a и b.

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

Нахождение наибольшего общего делителя - почему выводит неверный итог? - C++
Всем привет, что-то не могу понять:( Очень прошу помочь! int a, b; cin &gt;&gt; a &gt;&gt; b; while (b != 0) { a %= b; swap(a, b); } ...

9
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
10.10.2011, 18:58 #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;
}
1
filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
11.10.2011, 09:37  [ТС] #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);
}
0
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2011, 09:40 #4
filosof_77, оправданно ли использовать рекурсию для данной задачи, вряд ли
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.10.2011, 11:20 #5
На wikipedia есть оптимизированная реализация НОД
Она еще шустрее чем пункт 2
0
alexcoder
1549 / 694 / 93
Регистрация: 03.06.2009
Сообщений: 3,712
Завершенные тесты: 1
11.10.2011, 12:11 #6
Называется Алгоритм Евклида.
0
diagon
Higher
1932 / 1198 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
11.10.2011, 12:15 #7
C++
1
2
3
4
5
int gcd( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}
1
Thinker
Эксперт С++
4229 / 2203 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
11.10.2011, 12:52 #8
Цитата Сообщение от alexcoder Посмотреть сообщение
Называется Алгоритм Евклида.
А в постаx 2 и 3 разве не алгоритм Евклида Просто здесь обычный, а там бинарный. Проблема с бинарным алгоритмом Евклида такая, что из него нельзя построить расширенный алгоритм Евклида, но если это не нужно, то бинарный, наверное, лучше.
0
filosof_77
20 / 1 / 0
Регистрация: 16.12.2009
Сообщений: 36
11.10.2011, 14:49  [ТС] #9
это лабораторное задание .. думаю быстродействие алгоритма не является очень важным.!
но спасибо за столько примеров!
0
LosAngeles
Заблокирован
11.10.2011, 14:52 #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;
};
1
11.10.2011, 14:52
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2011, 14:52
Привет! Вот еще темы с ответами:

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

Написать подпрограмму нахождения наибольшего общего делителя двух чисел - C++
Написать подпрограмму нахождения наибольшего общего делителя двух чисел N и M по реккурентному соотношению: (N=23345 M=9135 =&gt;...

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

Написать программу вычисления наибольшего общего делителя двух целых чисел Dev C++ 4.9.9.2 - C++
Помогите написать программу! Написать программу вычисления наибольшего общего делителя двух целых чисел. Наибольший общий делитель...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.