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

НОД (наибольший общий делитель) n-го количества чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.73
Micki
227 / 3 / 0
Регистрация: 01.04.2010
Сообщений: 145
09.09.2012, 16:48     НОД (наибольший общий делитель) n-го количества чисел #1
Помогите, пожалуйста, написать программу на С++, которая бы находила НОД(наибольший общий делитель) n-го количества числа(n ввести с клавиатуры)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.09.2012, 16:48     НОД (наибольший общий делитель) n-го количества чисел
Посмотрите здесь:

C++ Описать функцию NOD2(A,B) целого типа,находящую наибольший общий делитель(НОД) двух целых положительных чисел А и В,используя алгоритм Евклида:....
Наибольший общий делитель (НОД) C++
наибольший общий делитель (НОД) двух целых положительных чисел A и B, используя алгоритм Евклида: C++
C++ Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида
C++ Написать функцию, определяющую НОД(наибольший общий делитель) двух целых чисел
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
09.09.2012, 20:16     НОД (наибольший общий делитель) n-го количества чисел #2
Micki, что есть "n-ое количество числа"?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
09.09.2012, 21:09     НОД (наибольший общий делитель) n-го количества чисел #3
NOD(a,b,c) = NOD(NOD(a,b),c),
NOD(a1,...,an) = NOD(NOD(...),an)
А про NOD можете здесь почитать
Самый быстрый алгоритм Евклида вычисления НОД
Micki
227 / 3 / 0
Регистрация: 01.04.2010
Сообщений: 145
10.09.2012, 07:05  [ТС]     НОД (наибольший общий делитель) n-го количества чисел #4
BumerangSP, n-го количества чисел
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
10.09.2012, 14:34     НОД (наибольший общий делитель) n-го количества чисел #5
Цитата Сообщение от Micki Посмотреть сообщение
BumerangSP, n-го количества чисел
Ясно. Ну, алгоритмы приведены, т.ч. нет смысла переписывать заново.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.09.2012, 21:58     НОД (наибольший общий делитель) n-го количества чисел #6
Еще можно разложить на простые множители, тогда можно будет искать НОД и НОК и еще много полезных фишек.
Micki
227 / 3 / 0
Регистрация: 01.04.2010
Сообщений: 145
12.09.2012, 10:37  [ТС]     НОД (наибольший общий делитель) n-го количества чисел #7
Цитата Сообщение от BumerangSP Посмотреть сообщение
Ясно. Ну, алгоритмы приведены, т.ч. нет смысла переписывать заново.
а не могли бы вы, если не сложно, написать программу? что-то у меня не выходит...
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.09.2012, 11:41     НОД (наибольший общий делитель) n-го количества чисел #8
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
26
27
28
29
30
#include<iostream>
#include<cmath>
 
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}
 
int main()
{
   long i, n, a, nod;
   std::cout << " n = "; std::cin >> n;
   if (n > 0)
   {
      std::cin >> a;
      nod = labs(a);
      for(i = 1; i < n && nod != 1; ++i)
      {
         std::cin >> a;
         nod = Nod(labs(a), nod);
      }
      std::cout << "nod = " << nod;
   }
   return 0;
}
Можно покороче код записать, но он уступает предыдущему варианту.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
 
 
long Nod(long a, long b)
{
   return a && b ? (a >= b ? Nod(a % b, b) : Nod(a, b % a)) : a + b;
}
 
long Nod_n(long *a, long *end)
{
   return a < end ? Nod(Nod_n(a + 1, end), *a) : 0;
}
 
int main()
{
   long a[] = {2, 6, 8, 10}, n;
   n = sizeof(a) / sizeof(*a);
   std::cout << "nod = " << Nod_n(a, a + n);
   return 0;
}
Micki
227 / 3 / 0
Регистрация: 01.04.2010
Сообщений: 145
12.09.2012, 17:11  [ТС]     НОД (наибольший общий делитель) n-го количества чисел #9
Цитата Сообщение от Thinker Посмотреть сообщение
long Nod(long a, long b)
а что значит эта строка? просто я только начал изучать энтонт язык...
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
12.09.2012, 17:17     НОД (наибольший общий делитель) n-го количества чисел #10
Micki, функция по имени Nod целочисленного типа long с двумя входными параметрами a и b (тоже типа long).
Micki
227 / 3 / 0
Регистрация: 01.04.2010
Сообщений: 145
12.09.2012, 17:34  [ТС]     НОД (наибольший общий делитель) n-го количества чисел #11
BumerangSP, Что эта функция делает?
П.с: вот эти две строчки тоже поясните, пожалуйста
Цитата Сообщение от Thinker Посмотреть сообщение
return a | b
Цитата Сообщение от Thinker Посмотреть сообщение
nod = Nod(labs(a), nod)
BumerangSP
12.09.2012, 17:37
  #12

Не по теме:

Micki, автор кода лучше объяснит, когда появится

MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.09.2012, 17:44     НОД (наибольший общий делитель) n-го количества чисел
Еще ссылки по теме:

C++ Вычислить НОД (наибольший общий делитель) двух натуральных чисел A и B
C++ Найти НОД (наибольший общий делитель) массива натуральных чисел
Написать программу, вычисляющую НОД (наибольший общий делитель) двух целых чисел C++

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
12.09.2012, 17:44     НОД (наибольший общий делитель) n-го количества чисел #13

Не по теме:

BumerangSP, да и у Вас хорошо это получается



return a | b;
Возвращает то из чисел a и b, которое не равно 0. Можно и так
return a + b;

nod = Nod(labs(a), nod)
labs(a) - модуль числа a. Функция вычисляет NOD у a и nod. Используется правило
http://www.cyberforum.ru/cgi-bin/latex.cgi?NOD(a_1,...,a_n) = NOD(NOD(a_1,...,a_{n-1}), a_n)
Yandex
Объявления
12.09.2012, 17:44     НОД (наибольший общий делитель) n-го количества чисел
Ответ Создать тему
Опции темы

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