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

НОД для нескольких чисел - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 24, средняя оценка - 4.71
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
01.09.2011, 21:36     НОД для нескольких чисел #1
не проблема найти НОД для двух чисел.
но как найти Нод для массива чисел(нескольких чисел)?просто находить НОД между парами чисел?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
 Аватар для grizlik78
1884 / 1416 / 102
Регистрация: 29.05.2011
Сообщений: 2,961
01.09.2011, 21:40     НОД для нескольких чисел #2
Между текущим НОД и очередным числом. До тех пор, пока числа не кончатся или очередной НОД не станет равным единице.
Artishok
ЧакЭ одобряЭ
 Аватар для Artishok
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
01.09.2011, 22:18  [ТС]     НОД для нескольких чисел #3
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>
 
int nod (int a, int b)  
{  
    if (b == 0) {
       if (a == 0)
           return -1; 
       else return a;}
    else abs(nod(b, a % b));
} 
 
int main()
{
    int n=0,n1=0;
    int ax[]={100,200,400};
    for(int i=0;i<3 & (n!=1);i++)
    {
        n1=n;
        n=nod(n1,ax[i]);
    }
    cout<<n<<endl;
}
так?
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
01.09.2011, 22:28     НОД для нескольких чисел #4
Artishok, вполне можно так (интуитивно понятней)
C++
1
2
3
4
int k = a[0];
 
for (int i = 1; i < a.size(); i++)
  k = lcs(k, a[i]);
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
01.09.2011, 22:33     НОД для нескольких чисел #5
Либо через факторизацию, если она уже известна

И можно без лишних переменных

C++
1
2
3
4
for(int i = 0; i <3 & (n != 1); i++)
{
        n=nod(n, ax[i]);
}
А, iama уже так заметил
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
02.09.2011, 18:13     НОД для нескольких чисел #6
как найти Нод для массива чисел(нескольких чисел)?
NOD(a1,a2,a3)= NOD( NOD(a1,a2), a3 )
NOD(a1,a2,a3,a4)= NOD( NOD( NOD(a1,a2), a3 ), a4 )
и так далее ...
Yandex
Объявления
02.09.2011, 18:13     НОД для нескольких чисел
Ответ Создать тему
Опции темы

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