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

@Artishok · Регистрация: 27.12.2009

Author24 — интернет-сервис помощи студентам

не проблема найти НОД для двух чисел.
но как найти Нод для массива чисел(нескольких чисел)?просто находить НОД между парами чисел?

@grizlik78 · 01.09.2011, 21:40

Между текущим НОД и очередным числом. До тех пор, пока числа не кончатся или очередной НОД не станет равным единице.

@Artishok · 01.09.2011, 22:18 **[ТС]**

C++

#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 · 01.09.2011, 22:28

Artishok, вполне можно так (интуитивно понятней)

C++

int k = a[0];
 
for (int i = 1; i < a.size(); i++)
  k = lcs(k, a[i]);

@Thinker · 01.09.2011, 22:33

Либо через факторизацию, если она уже известна

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

C++

for(int i = 0; i <3 & (n != 1); i++)
{
        n=nod(n, ax[i]);
}

А, iama уже так заметил

@odip · 02.09.2011, 18:13

как найти Нод для массива чисел(нескольких чисел)?

NOD(a1,a2,a3)= NOD( NOD(a1,a2), a3 )
NOD(a1,a2,a3,a4)= NOD( NOD( NOD(a1,a2), a3 ), a4 )
и так далее ...

@ANTON NEZIN · 17.05.2019, 14:31

Нахождение НОД n чисел

Croessmah · 17.05.2019, 14:59

ANTON NEZIN, бро, красава. Восемь лет ждали тебя, не могли эту ссылку найти.

@Artishok ЧакЭ одобряЭ 285 / 284 / 86 Регистрация: 27.12.2009 Сообщений: 1,767
		1
	НОД для нескольких чисел 01.09.2011, 21:36. Показов 21700. Ответов 7 Метки нет (Все метки) не проблема найти НОД для двух чисел. но как найти Нод для массива чисел(нескольких чисел)?просто находить НОД между парами чисел? 0

@grizlik78 2382 / 1666 / 279 Регистрация: 29.05.2011 Сообщений: 3,402
	01.09.2011, 21:40	2
	Между текущим НОД и очередным числом. До тех пор, пока числа не кончатся или очередной НОД не станет равным единице. 2

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	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 ) и так далее ... 0

@ANTON NEZIN 0 / 0 / 0 Регистрация: 17.05.2019 Сообщений: 2
	17.05.2019, 14:31	7
	Нахождение НОД n чисел 0

Croessmah Неэпический 18109 / 10696 / 2062 Регистрация: 27.09.2012 Сообщений: 26,939 Записей в блоге: 1
	17.05.2019, 14:59	8
	Сообщение было отмечено Toshkarik как решение Решение ANTON NEZIN, бро, красава. Восемь лет ждали тебя, не могли эту ссылку найти. 8

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

Решение