Как найти нод массива - Сайт, где вы сможете решить свои вопросы

odip

7175 / 3234 / 81

Регистрация: 17.06.2009

Сообщений: 14,164

27.01.2010, 18:12

Ерунда все это.
Алгоритм неэффективный.
А если самое маленькое значение – 1000000, а NOD всего массива при этом равен 1 ?
Будем цикл 999999 раз перебирать ?

Как известно NOD(a1,a2,a3,a4)=NOD(NOD(NOD(a1,a2),a3),a4)
Отсюда следует простой код:

/* Thread 90039 */
 
#include <stdio.h>
 
 
/********************************************************************/
int gcd( int a, int b );
int arr_gcd( int n, const int *pa );
 
 
/********************************************************************/
int main( void ) {
 
int g;
int a[6]= { 12000, 300, 1500, 2100, 18000, 291 };
 
 
g= arr_gcd( 6, a );
printf( "%dn", g );
 
return 0;
 
} /* main() */
 
 
/********************************************************************/
int gcd( int a, int b ) {
 
int c;
 
while (b!=0) {
    c= a%b; a= b; b= c;
}
return ((a>=0) ? a : -a);
 
} /* gcd() */
 
 
/********************************************************************/
int arr_gcd( int n, const int *pa ) {
 
int i, g;
 
 
if ( n<1 ) { return 1; }
g= pa[0];
for ( i= 1; i<n; i++ ) { g= gcd( g, pa[i] ); }
return g;
 
} /* arr_gcd() */

Источник

Задача:

Найти наименьшее общее кратное для всех элементов массива — минимальное число, которое делится на все элементы массива без остатка. Также, найти НОД всех элементов массива.

Решение:

Вот тут приведены алгоритмы расчета НОК и НОД для двух чисел. Ясно, что наиболее эффективный алгоритм расчета НОК двух чисел — это произведение чисел поделить на их НОД. По содержимому статьи ясно что НОК(а1, а2, а3, ... аN) равен НОК(НОК(НОК(А1, А2), А3)..., АN). Таким образом, для расчета НОК массива чисел надо многократно расчитывать НОД двух чисел, реализация этой функции на С++ взята тут.

Реализация на Си (функции чуть-чуть изменены, так как добавлена самописная функция swap):

#include <stdio.h>
#include <stdlib.h>

void read_array(int n, int** values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = ", i);
        scanf("%d", &((*values)[i]));
    }
}

void print_array(int n, int* values) {
    for (int i = 0; i < n; ++i) {
        printf("values[%d] = %dn", i, values[i]);
    }
}

void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int gcd(int a, int b) {
    if (a < b) {
        swap(&a, &b);
    }
    while (a % b != 0) {
        a = a % b;
        swap(&a, &b);
    }
    return b;
}

int gcd_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int gcd_value = gcd(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        gcd_value = gcd(gcd_value, values[i]);
    }
    return gcd_value;
}

int lcm(int a, int b) {
    return (a*b)/gcd(a, b);
}

int lcm_n(int n, int* values) {
    if (n == 0)
        return -1;
    if (n == 1)
        return values[0];
    int lcm_value = lcm(values[0], values[1]);
    for (int i = 2; i < n; ++i) {
        lcm_value = lcm(lcm_value, values[i]);
    }
    return lcm_value;
}

int main() {
    int n;
    int *values;
    
    printf("n: ");
    scanf("%d", &n);
    
    values = malloc(sizeof(int) * n);
    
    read_array(n, &values);
    
    printf("lcm: %d", lcm_n(n, values));
    
    free(values);
    return 0;
}

Источник

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

In this article, we are given two or more numbers/array of numbers and the task is to find the GCD of the given numbers/array elements in JavaScript.

Examples:

Input  : arr[] = {1, 2, 3}
Output : 1

Input  : arr[] = {2, 4, 6, 8}
Output : 2

The GCD of three or more numbers equals the product of the prime factors common to all the numbers, but it can also be calculated by repeatedly taking the GCD of pairs of numbers.

gcd(a, b, c) = gcd(a, gcd(b, c))
            = gcd(gcd(a, b), c)
            = gcd(gcd(a, c), b)

For an array of elements, we do the following. We will also check for the result if the result at any step becomes 1 we will just return 1 as gcd(1, x) = 1.

result = arr[0]
For i = 1 to n-1
  result = GCD(result, arr[i])

Below is the implementation of the above approach.

Example: In this example, we will find the GCD of the elements of an array using Javascript.

Javascript

<script>

function gcd(a, b) {

if (a == 0)

return b;

return gcd(b % a, a);

}

function findGCD(arr, n) {

let result = arr[0];

for (let i = 1; i < n; i++) {

result = gcd(arr[i], result);

if (result == 1) {

return 1;

}

return result;

}

let arr = [2, 4, 6, 8, 16];

let n = arr.length;

console.log(findGCD(arr, n));

</script>

Output:

Last Updated :
03 Jan, 2023

Like Article

Save Article

Источник

Как найти НОК или НОД в python 3.9 в списке из n кол-ва чисел? (Ввод чисел пользователем)
(н: math.gcd([1 , 2 , 3])

задан 26 окт 2021 в 16:22

список из нескольких чисел можно получить следующим образом:

data = list(map(int, input().split()))

весь код таким образом будет выглядеть так:

import math

data = list(map(int, input().split()))

gcd = math.gcd(*data)
lcm = math.lcm(*data)

print(gcd, lcm)

ответ дан 26 окт 2021 в 16:42

ZhiharZhihar

36.8k4 золотых знака25 серебряных знаков66 бронзовых знаков

print ('a = ', end = '')

a = int (input ())

print ('b = ', end = '')

b = int (input ())

p = a * b

while a != 0 and b != 0:

    if a > b:

        a = a % b

    else:

        b = b % a

nod = a + b

nok = p // nod

print ('GCD:', nok)
print ('LDM:', nod)

ответ дан 26 окт 2021 в 16:29

Источник

НОД и НОК для массива

Напомню, что НОД (наибольший общий делитель, GCD) для натуральных чисел A и B – максимальное из чисел, на которые A и B делятся без остатка, НОК (наименьшее общее кратное, LCM) – минимальное из чисел, которые делятся на A и B без остатка. Можно реализовать простой и удобный алгоритм поиска НОД и НОК для пары чисел, а для массива натуральных чисел у народа почему-то вызвало затруднения. Между тем, вот такое решение кажется мне простым и правильным:

#include <stdio.h>

//Реализация для 2 чисел
long int nod (int x, int y) { return (x?nod(y%x,x):y); }
long int nok (int x, int y) { return x*y/nod(x,y); }
//и вернуть nok(x,y) или nod(x,y)

void main () {
 const int n=5;
 int a[n]={24,36,144,48,72},i;
 //НОД для массива:
 long int nd=a[0];
 for (i=1; i<n; i++) nd=nod((nd<a[i]?nd:a[i]),(nd<a[i]?a[i]:nd));
 printf ("nNOD=%ld",nd);
 //НОК для массива:
 long int nk=1;
 for (i=0; i<n; i++) nk=nok(nk,a[i]);
 printf ("nNOK=%ld",nk);
}

Или с выводом через <iostream>:

#include <iostream>
using namespace std;

long int nod(long int x, long int y) { return (x ? nod(y % x, x) : y); }
long int nok(long int x, long int y) { return x * y / nod(x, y); }

int main() {
 const int n = 5;
 long int a[n] = { 24, 36, 144, 48, 72 }, i;
 //НОД для массива:
 long int nd = a[0];
 for (i = 1; i < n; i++) nd = nod((nd < a[i] ? nd : a[i]), (nd < a[i] ? a[i] : nd));
 cout << "NOD = " << nd << endl;
 //НОК для массива:
 long int nk = 1;
 for (i = 0; i < n; i++) nk = nok(nk, a[i]);
 cout << "NOK = " << nk << endl;
 return 0; 
}

P.S. Начиная со стандарта C++17, можно воспользоваться стандартными средствами, смотрите в комментарии к программе как подключить компиляцию стандарта C++17 в консольном проекте Visual Studio 2019.

//Включить в свойствах проекта поддержку стандарта C++17:
// Project, Properties, C/C++, Language, C++ Language Standard, ISO C++17 (/std:c++17)
#include <iostream>
#include <numeric>
using namespace std;

int main() {
 int n = 24, m = 36;
 cout << gcd(n, m) << endl; //НОД, https://en.wikipedia.org/wiki/Greatest_common_divisor
 cout << lcm(n, m) << endl; //НОК, https://en.wikipedia.org/wiki/Least_common_multiple
 return 0;
}

03.12.2012, 08:46 [17042 просмотра]

К этой статье пока нет комментариев, Ваш будет первым

Источник

Javascript

НОД и НОК для массива

Вам также может понравиться

Как найти планеты на звездном небе

Скайрим проблемы с текстурами как исправить

Брюки провисают в паху как исправить

Добавить комментарий Отменить ответ