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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.64
deepLulz
 Аватар для deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
09.04.2012, 14:42     Функция gcd для множества изначально неизвестных чисел. #1
Собственно вот изначальная задача:
Дано натуральное число 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 минут
Все еще актуально.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
09.04.2012, 15:03     Функция gcd для множества изначально неизвестных чисел. #2
deepLulz, Переменная nod у тебя не инициализируется
Лучше так
C
1
2
if (i==1) nod = x
else nod = gcd(x, nod);
Преподаватель, давая добро, этой плюхи, видимо, не заметил.
deepLulz
 Аватар для deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
09.04.2012, 15:05  [ТС]     Функция gcd для множества изначально неизвестных чисел. #3
Байт, спасибо, но все еще остается вопрос: что из себя представляет gcd? что она делает и как ее представить чисто математически?
Байт
 Аватар для Байт
13974 / 8805 / 1227
Регистрация: 24.12.2010
Сообщений: 15,949
09.04.2012, 15:07     Функция gcd для множества изначально неизвестных чисел. #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);
}
deepLulz
 Аватар для deepLulz
4 / 4 / 0
Регистрация: 12.02.2012
Сообщений: 46
09.04.2012, 15:14  [ТС]     Функция gcd для множества изначально неизвестных чисел. #5
Байт, извиняюсь, но у меня неизвестное множество чисел, которые я задаю на протяжении цикла. Прошу посмотреть на приложенный к теме код и на тот факт, что массивы использовать нельзя.
dr.curse
 Аватар для dr.curse
386 / 342 / 16
Регистрация: 11.10.2010
Сообщений: 1,907
09.04.2012, 15:26     Функция gcd для множества изначально неизвестных чисел. #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);
}
Yandex
Объявления
09.04.2012, 15:26     Функция gcd для множества изначально неизвестных чисел.
Ответ Создать тему
Опции темы

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