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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
ArhangelM
0 / 0 / 0
Регистрация: 20.04.2010
Сообщений: 17
#1

Найти наибольший общий делитель всех элементов массива - C++

20.01.2012, 04:15. Просмотров 2333. Ответов 11
Метки нет (Все метки)

Такая задача: Найти наибольший общий делитель всех элементов массива (на который они все делятся без остатка).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.01.2012, 04:15     Найти наибольший общий делитель всех элементов массива
Посмотрите здесь:

C++ Найти наибольший общий делитель всех элементов массива
В массиве найти наибольший общий делитель его второго максимального и минимального по абсолютной величине элементов C++
Найти наибольший общий делитель чисел C++
[Qt 5] Задание:Найти наибольший общий делитель n и m C++
C++ Найти НОД (наибольший общий делитель) массива натуральных чисел
C++ Найти НОД (наибольший общий делитель)
C++ Найти NOD(a, b, c), (наибольший общий делитель)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
HackSign
33 / 33 / 13
Регистрация: 23.11.2006
Сообщений: 113
20.01.2012, 08:46     Найти наибольший общий делитель всех элементов массива #2
Достаточно одного исходника написанного на любом С++ компилляторе. Подожди немного, сейчас накидаю программку.
diagon
Higher
1921 / 1187 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
20.01.2012, 09:57     Найти наибольший общий делитель всех элементов массива #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <algorithm>
 
int main()
{
    int arr[] = { 12, 16, 28 };
    
    std::cout << std::accumulate( arr, arr + sizeof( arr ) / sizeof( *arr ), 0,
    [] ( int a, int b ) -> int
    {
        while ( b ^= a ^= b ^= a %= b );
        return a;
    } );
}
HackSign
33 / 33 / 13
Регистрация: 23.11.2006
Сообщений: 113
20.01.2012, 11:02     Найти наибольший общий делитель всех элементов массива #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
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream.h> 
 
int main() 
{ 
int mass[10]; 
int NOD, count, i, j, k, x, y, g, h; 
float ost;
//ââîä Г¬Г*Г±Г±ГЁГўГ* âðó÷Г*ГіГѕ 
cout<<"Vvedite kolichestvo elementov massiva ot 3 do 10"<<"\n"; 
cin>>x; cout<<"\n"; 
 
if((x>10)||(x<3)) 
{ 
 cout<<"Error! Nepravilno vvedennoe kolichestvo elementov massiva!!!"<<"\n"; 
 cout<<"Press any key to exit programm"<<"\n"; 
 getch(); 
 exit(0); 
 } 
 else 
 { 
      //ââîä Г¬Г*Г±Г±ГЁГўГ* âðó÷Г*ГіГѕ 
 
   for(i=0;i<=x; i++) 
   { 
    cout<<"Vvedite "<<i<<" element massiva "; 
    cin>>mass[i]; cout<<"\n"; 
    }  
    //Г*Г*Г·Г*ëüГ*ûé ГЅГІГ*ГЇ âû÷èñëåГ*ГЁГ© Г*Г*èáîëüøåãî îáùåãî äåëèòåëÿ
    if(mass[0]<mass[1]) 
    { 
     g=mass[1]; 
     h=mass[0]; 
     }
     if(mass[0]>mass[1]) 
     { 
      g=mass[0]; 
      h=mass[1];
      } 
    while(g%h!=0) 
     {
     ost=g%h;  //NOD 
       
     if(ost==0) 
     { 
      NOD=h; 
      break;
      } 
      else{ 
          count=h;
          h=g%h;
          g=count; 
          NOD=h;
          } 
      }     
       
             
    //âû÷èñëåГ*ГЁГҐ Г*Г*èáîëüøåãî îáùåãî äåëèòåëÿ Г¬Г*Г±Г±ГЁГўГ* 
   for(i=x+2;i<=x;i++) 
   { 
     if(NOD<mass[i])  
      { 
       g=mass[i];
       h=NOD;
       }
      else 
       { 
        g=NOD;
        h=mass[i]; 
        }
       while (g%h!=0)
         { 
       if(g%h==0)
       {NOD=h; 
        break; 
         }
       else 
        { 
           count=h;
           h=g%h;
           g=count;
           NOD=h;
           }
         }
       }
     }
   
 
   cout<<"Naibolhiy obshiy delitel massiva"<<" "<<NOD;
   cout<<"Press any key to exit"; 
   getch();
return 0 ;
}
ArhangelM
0 / 0 / 0
Регистрация: 20.04.2010
Сообщений: 17
20.01.2012, 12:07  [ТС]     Найти наибольший общий делитель всех элементов массива #5
Ребят.Подскажите,как создать новый проэкт..чуть я запутался((
co6ak
Кошковед
407 / 500 / 29
Регистрация: 12.04.2010
Сообщений: 1,392
20.01.2012, 12:28     Найти наибольший общий делитель всех элементов массива #6
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
#include <iostream>
#include <limits.h>
 
int main()
{
    int size;
    std::cout << "Enter size: ";
    std::cin  >> size;
    int *arr = new int [size];
    int NOD = INT_MIN;
 
    std::cout << "\nEnter array elements: \n";
    for ( int i = 0; i < size; i ++ )
    {
            std::cin >> arr[i];
            if ( NOD < arr[i] ) NOD = arr[i];
    }
 
 
    while ( NOD > 1 )
    {
        bool flag = true;
        for ( int i = 0; i < size; i ++ )
            if ( arr[i] % NOD != 0 )
            {
                flag  = false;
                break;
            }
        if ( !flag ) --NOD;
        else
            break;
    }
 
    std::cout << "The answer is : " << NOD;
    std::cin.get();
    std::cin.get();
    return 0;
}
HackSign
33 / 33 / 13
Регистрация: 23.11.2006
Сообщений: 113
20.01.2012, 13:13     Найти наибольший общий делитель всех элементов массива #7
Дык в Visual studio 2008 довольно просто. выбираешь язык программирования, открывается среда разработки, далее, в меню Файл, создаешь проект, как только проект у тебя открылся, добавляешь в него исходник и компилишь. файловый обозреватель там чтоли, file browser. я уж давно использую Dev-C++. может подзабыл чуток. ну, в общем как-то так.
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
25.05.2012, 13:02     Найти наибольший общий делитель всех элементов массива #8
HackSign, что вычисляет первый цикла вашей программы?
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
 //начальный этап вычислений наибольшего общего делителя
    if(mass[0]<mass[1]) 
    { 
     g=mass[1]; 
     h=mass[0]; 
     }
     if(mass[0]>mass[1]) 
     { 
      g=mass[0]; 
      h=mass[1];
      } 
    while(g%h!=0) 
     {
     ost=g%h;  //NOD 
       
     if(ost==0) 
     { 
      NOD=h; 
      break;
      } 
      else{ 
          count=h;
          h=g%h;
          g=count; 
          NOD=h;
          } 
      }
Оссобенно интересует цикл:
C++
1
2
3
4
5
6
7
8
9
10
11
  while(g%h!=0) // Пока остаток от деления g и h элементов станет не равным 0 выполнять цикл.
   { ostatok=g%h;  // находим остаток от деления элементов.
     if(ostatok == 0) // если остаток равен 0, тогда...
      { NOD=h; // НОД - это элемент h.
        break; }  // Прекратить цикл.
     else
     { count=h;
       h=g%h;
       g=count; 
       NOD=h; } 
    }
Если заполнить массив размером 5 чисами: 1, 2, 3, 4, 5. , то НОД = 8, что ест-но неверно. Так зачем этот цикл нужен? Что он делает?

Добавлено через 1 час 6 минут
Пытался что-то придумать сам. Дальше не могу сообразить что делать, помогите!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>  
#include <conio.h> 
#include <stdlib.h> // Модуль для генератора псевдослучайных чисел.
#include <time.h> // Модуль для работы с датой и временем.
#define N 5 // Размер массива.
int main()
{
 int mass[N]; 
 int i, max, nod; 
 
 srand(unsigned(time(NULL))); // Запуск генератора случайных чисел.
 printf("\n Massiv iz chisel ot 1 do 5: \n");
  for(i=0; i<N; i++)
  {
   mass[i]=rand()%10+1; // Генерируем случайные элемены массива от 1 до 10...   
   printf("\n Mass[%d] = %d. ", i, mass[i]); // и выводим их.
  }
  max=mass[0]; // Первый элемент назначаем за максимальный
MrGluck
Ворчун
Эксперт CЭксперт С++
6327 / 3572 / 445
Регистрация: 29.11.2010
Сообщений: 9,456
25.05.2012, 13:23     Найти наибольший общий делитель всех элементов массива #9
Цитата Сообщение от diagon Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <algorithm>
 
int main()
{
    int arr[] = { 12, 16, 28 };
    
    std::cout << std::accumulate( arr, arr + sizeof( arr ) / sizeof( *arr ), 0,
    [] ( int a, int b ) -> int
    {
        while ( b ^= a ^= b ^= a %= b );
        return a;
    } );
}
Не верно с отрицательными числами.
Наверное надо модуль брать.
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
25.05.2012, 14:27     Найти наибольший общий делитель всех элементов массива #10
Еще вариант:
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
#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h> 
#include <time.h> 
#define N 4 // Размер массива.
int main()
{
 /* int mass[N]; */
 int mass[N]={8, 6, 4, 2}; // Объявляем массив.
 int i, g, h, x, temp, NOD; 
 bool flag;
 /* srand(unsigned(time(NULL))); // Запуск генератора случайных чисел. */
 printf("\n Massiv iz chisel ot 1 do 4: \n"); 
  for(i=0; i<N; i++)
  {
   /* mass[i]=rand()%10+1;  */
   printf("\n Mass[%d] = %d. ", i, mass[i]);
  }
 
  if(mass[0]<mass[i]) // Если первый элемент массива меньше второго, тогда...
   { g=mass[i]; h=mass[0]; }  // запомининаем след. элемент в перем-ой g, а первый в перем-ой h.
  if(mass[0]>mass[i]) // Если первый элемент массива больше второго, тогда...
   { g=mass[0]; h=mass[i]; } // запомининаем первый элемент в перем-ой g, а след. в перем-ой h.
 
 do // выполнять до тех пор...
   { 
    if(g%h == 0) // если большее число делится на меньшее без остатка, тогда...
     { NOD=h; } // меньшее число и есть НОД.
    else // Иначе.
     { temp=h; 
       h=g%h; // Второе станет остатком от деления.
       g=temp; // А первое число вторым, значения которого записываем во временную переменную.
       NOD=h; } // Пока НОДом будет второе число.
    }     
 while(g%h!=0); // ...пока остаток от деления g и h элементов не перестанет быть равным 0.
  
  if (NOD != 1) // Если НОД не равен 1...
   { printf("\n \n NOD = %d. \n", NOD); } // Выводим результат на экран.
  else 
   { printf("\n \n Chisla ne imeut obschih deliteley \n"); } // Числа не имеют общих делителей.
              
 getch(); 
 return 0;
}
Разультат: 8. Однако неверно, т.к. 8 не делится на 6 без остатка. Поогите найти ошибку.
PS: Генератор случайных чисел временно отключил, чтобы проверить программу на конкретных числах.
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
27.05.2012, 11:15     Найти наибольший общий делитель всех элементов массива #11
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
#include <stdio.h> 
#include <conio.h> 
#include <stdlib.h> 
#include <time.h> 
#define N 5 
int main()
{ /* int mass[N]; */
 int mass[N]={2, 4, 8, 16, 32}; // Объявляем массив.
 int i, g, h, x, temp, NOD; 
 /* srand(unsigned(time(NULL))); // Запуск генератора случайных чисел. */
 printf("\n Massiv iz 5 elementov: \n"); 
  for(i=0; i<N; i++)
  {
   /* mass[i]=rand()%10+1;  */
   printf("\n Mass[%d] = %d. ", i, mass[i]);
  }
 
  if(mass[0]<mass[i]) // Если первый элемент массива меньше второго, тогда...
   { g=mass[i]; h=mass[0]; }  // запомининаем след. элемент в перем-ой g, а первый в перем-ой h.
  if(mass[0]>mass[i]) // Если первый элемент массива больше второго, тогда...
   { g=mass[0]; h=mass[i]; } // запомининаем первый элемент в перем-ой g, а след. в перем-ой h.
 
 do // выполнять до тех пор...
   { 
    if(g%h == 0) // если большее число делится на меньшее без остатка, тогда...
     { NOD=h; } // меньшее число и есть НОД.
    else // Иначе.
     { temp=h; 
       h=g%h; // Второе станет остатком от деления.
       g=temp; // А первое число вторым, значения которого записываем во временную переменную.
       NOD=h; } // Пока НОДом будет второе число.
    }     
 while(g%h!=0); // ...пока остаток от деления g и h элементов не перестанет быть равным 0.
  
  if (NOD != 1) // Если НОД не равен 1...
   { printf("\n \n NOD = %d. \n", NOD); } // Выводим результат на экран.
  else 
   { printf("\n \n Chisla ne imeut obschih deliteley \n"); } // Числа не имеют общих делителей.
              
 getch(); 
 return 0;
}
Программа выдает, что общих делителей не найдено, хотя здесь НОД = 2. Где допущена ошибка?
Генератор случайных чисел временно отключил, чтобы проверить программу на конкретных числах.

Интересно, что когда я уменьшаю массив до 3 элементов и ввожу 2, 4, 8, то НОД находится верно (НОД=2).
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.05.2012, 21:07     Найти наибольший общий делитель всех элементов массива
Еще ссылки по теме:

Найти наибольший общий делитель для элементов произвольного одномерного массива C++
Найти наибольший общий делитель многочленов C++
Вывести наибольший общий делитель всех элементов заданной последовательности целых чисел C++
C++ Найти наибольший общий делитель
найти наибольший общий делитель массива натуральных чисел C++

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

Или воспользуйтесь поиском по форуму:
Shman
3 / 3 / 2
Регистрация: 30.04.2012
Сообщений: 212
31.05.2012, 21:07     Найти наибольший общий делитель всех элементов массива #12
Кажется нашел в этом форуме решение другими словами .
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
const int N = 5; // Размер массива.
int main()
{
 int mass[N]={2, 16, 64, 32, 2};
 int NOD, i, flag;
 printf("\n Massiv iz 5 elementov \n"); 
  for(i=0; i<N; i++)
  {
   printf("\n Mass[%d] = %d ", i, mass[i]);
  }
 NOD = mass[0]; // Предпологаем, что первый элемент массива - это НОД.
 for(i=1; i<N; i++) 
  if(NOD > mass[i]) // Если предполгаемый НОД больше след. элемент массива, 
     { NOD = mass[i]; } // тогда след.элемент - НОД.
    flag=1; // Флаг на true
    while(flag==1) // Пока флаг = true делаем.
    {
     flag=0; // Флаг = false.
     for(i=0; i<N; i++)
      if(mass[i]%NOD!=0) // Если след. элемент массива делится на предпологаемый НОД без остатка,
         { flag=1; }  // тогда ставим флаг на true.
         NOD--; // Здесь уменьшаем значение НОД. 
    }
  NOD++; // Здесь увеличиваем значение НОД.   
  printf("\n \n NOD = %d. \n", NOD);  
  
 getch(); 
 return 0;
}
 
 
}
Вот только надо подумать как прикрутить работу с отрицательными числами и обойти деление на 0.
Yandex
Объявления
31.05.2012, 21:07     Найти наибольший общий делитель всех элементов массива
Ответ Создать тему
Опции темы

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