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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.64
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
#1

Функция gcd для множества изначально неизвестных чисел. - C++

09.04.2012, 14:42. Просмотров 3441. Ответов 5
Метки нет (Все метки)

Собственно вот изначальная задача:
Дано натуральное число N и натуральные числа a1,a2,a3...aN. Найти наибольший общий делитель. Массивы использовать нельзя.
Задачу я решил следующим образом:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
main(){
    int i,n,x,nod;
    printf("N=");
    scanf("%u",&n);
    for(i=1;i<=n;i++){
        printf("a%u=",i);
        scanf("%f",&x);
        nod = gcd(x,nod);
    }
    getch();
    return 0;
}
Преподаватель дал добро, но сказал заменить функцию gcd математическими действиями.
Кто может разжевать что конкретно делает функция gcd с последовательностью чисел в моем случае? Желательно алгоритм ее работы, что бы я мог записать его и заменить саму функцию в программе.

Спасибо.

Добавлено через 16 часов 55 минут
Все еще актуально.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2012, 14:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Функция gcd для множества изначально неизвестных чисел. (C++):

Функция gcd, которая возвращает наибольший общий делитель двух целых чисел - C++
Наибольший общий делитель (НОД) двух целых чисел является самым большим числом, на которое делится каждое из двух чисел. Напишите функцию...

Есть ли функция gcd(нод) в STL - C++
Есть ли функция gcd(нод) в STL. Если да, то в каком заголовочном файле P.S. Проблем с её написанием вручную не возникает, но всё-таки...

Функция добавления для множества - C++
Как изменить функцию add, чтобы она не выполнялась для элемента, который уже существует в массиве (множестве)? class massiv { ...

Реализовать красно-черное дерево для хранения множества целых чисел - C++
Я не особо понял, как его реализовывать. Подскажите какие-нибудь книги по данной теме. Я нашел еще сайт http://algolist.ru/ds/rbtree.php ,...

для одномерного множества состоящей из целых n чисел 1.найти по модулю самый меньший элемент ; - C++
для одномерного множества состоящей из целых n чисел .найти по модулю самый меньший элемент ;

Реализуйте алгоритм сортировки для массива, содержащего указатели на объекты-множества целых чисел - C++
Помогите сделать лабу, Я даже не знаю с чего начинать. Пользователь вводит в программу текст произвольной длины, завершая ввод...

5
Байт
Эксперт C
16344 / 10620 / 1590
Регистрация: 24.12.2010
Сообщений: 20,258
09.04.2012, 15:03 #2
deepLulz, Переменная nod у тебя не инициализируется
Лучше так
C
1
2
if (i==1) nod = x
else nod = gcd(x, nod);
Преподаватель, давая добро, этой плюхи, видимо, не заметил.
2
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
09.04.2012, 15:05  [ТС] #3
Байт, спасибо, но все еще остается вопрос: что из себя представляет gcd? что она делает и как ее представить чисто математически?
0
Байт
Эксперт C
16344 / 10620 / 1590
Регистрация: 24.12.2010
Сообщений: 20,258
09.04.2012, 15:07 #4
А НОД считается так
C
1
2
3
4
5
6
7
8
9
10
11
int mygcd(int a, int b)
{ int t;
    if (a < b) { t = a; a = b; b = t; }
    while(a != b) {
      t = a % b;
      if (t==0) break;
      a = b;
      b = t;
    }
    return(b);
}
0
deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
09.04.2012, 15:14  [ТС] #5
Байт, извиняюсь, но у меня неизвестное множество чисел, которые я задаю на протяжении цикла. Прошу посмотреть на приложенный к теме код и на тот факт, что массивы использовать нельзя.
0
dr.curse
389 / 345 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.04.2012, 15:26 #6
Цитата Сообщение от Байт Посмотреть сообщение
А НОД считается так
C
1
2
3
4
5
6
7
8
9
10
11
int mygcd(int a, int b)
{ int t;
    if (a < b) { t = a; a = b; b = t; }
    while(a != b) {
      t = a % b;
      if (t==0) break;
      a = b;
      b = t;
    }
    return(b);
}
или так

C
1
2
3
4
int gcd(int a,int b)
{
    return (b ? gcd(b,a%b) : a);
}
0
09.04.2012, 15:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.04.2012, 15:26
Привет! Вот еще темы с ответами:

Из множества целых чисел получить множество чисел, являющихся квадратами нечетных чисел - C++
Из множества целых чисел получить множество чисел, являющихся квадратами нечетных чисел.

Функция для простых чисел - C++
Найти все трехзначные простые числа, определив функцию, позволяющую распознавать простые числа.

Функция для вычисления трех целых чисел - C++
Помогите написать две функции вычисления суммы трех целых чисел. Использовать в первой функции передачу параметров по значению, во второй –...

Функция для поиска ближайших простых чисел - C++
Ув. товарищи программисты , нужна помощь. Требуется функция с помощью которой можно найти 2 ближайших ПРОСТЫХ числа к веденному числу. ...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

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