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

Найти НОД для всех элементов массива - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
CityFix
0 / 0 / 0
Регистрация: 27.01.2010
Сообщений: 5
27.01.2010, 09:37     Найти НОД для всех элементов массива #1
Подскажите как найти наибольший общий делитель всех элементов массива?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.01.2010, 09:37     Найти НОД для всех элементов массива
Посмотрите здесь:

Найти сумму всех элементов массива, кратных 4 C++
найти среднее арифметическое всех элементов массива, кроме элементов... C++
Найти элемент массива, наиболее близкий к среднему значению всех элементов массива C++
C++ Массивы в C++: найти сумму всех элементов массива
Найти количество элементов превышающих среднее арифметическое всех элементов массива C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2010, 09:48     Найти НОД для всех элементов массива #2
CityFix, Берете значение самого маленького элемента, и проверяете все элементы массива на делимость без остатка на это значение. Если нет, то уменьшаете это значение на 1, и снова проверяете. В конце концов как максимум на 1 остановитесь.
CityFix
0 / 0 / 0
Регистрация: 27.01.2010
Сообщений: 5
27.01.2010, 09:58  [ТС]     Найти НОД для всех элементов массива #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
CityFix, Берете значение самого маленького элемента, и проверяете все элементы массива на делимость без остатка на это значение. Если нет, то уменьшаете это значение на 1, и снова проверяете. В конце концов как максимум на 1 остановитесь.
А наброски кода какие нибудь у Вас есть?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.01.2010, 10:19     Найти НОД для всех элементов массива #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream> 
using namespace std; 
int main()
{
    const int N=5;
    int mas[N]={12,3,15,21,18};
    int max_NOD=mas[0], i;
    for(i=1; i<N; i++)
        if(max_NOD>mas[i])
            max_NOD=mas[i];
    int fl=1;
    while(fl)
    {
        fl=0;
        for(i=0; i<N; i++)
            if(mas[i]%max_NOD!=0)
                fl=1;
        max_NOD--;
    }
    max_NOD++;
    cout<<max_NOD<<endl;
    return 0;
}
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
27.01.2010, 18:12     Найти НОД для всех элементов массива #5
Ерунда все это.
Алгоритм неэффективный.
А если самое маленькое значение - 1000000, а NOD всего массива при этом равен 1 ?
Будем цикл 999999 раз перебирать ?

Как известно NOD(a1,a2,a3,a4)=NOD(NOD(NOD(a1,a2),a3),a4)
Отсюда следует простой код:
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/* 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( "%d\n", 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() */
CityFix
0 / 0 / 0
Регистрация: 27.01.2010
Сообщений: 5
26.03.2010, 05:14  [ТС]     Найти НОД для всех элементов массива #6
Спасибо всем откливнушимся
Yandex
Объявления
26.03.2010, 05:14     Найти НОД для всех элементов массива
Ответ Создать тему
Опции темы

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