Напишите функцию, вычисляющую НОД двух целых чисел

@ElemeNT · Регистрация: 27.10.2008

Студворк — интернет-сервис помощи студентам

Напишите функцию на языке Си, вычисляющую НОД двух целых чисел

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(void)
{
    int a,b,c,n,i;
    printf("vvedite 2 chisla cherez probel\n");
    scanf("%d%d",&a,&b);
    if ((a>b)&&(b==0)) {printf("net resheniya\n"); system("pause");return 1;}
    if ((a<b) &&(a==0)) {printf("net resheniya\n"); system("pause");return 1;}
    if ((a==0) &&(b==0)) {printf("net resheniya\n"); system("pause");return 1;}
    if (a<b)
    {c=a;
    a=b;
    b=c;
    n=a;}
    else
    { 
    n=b;}
    for (i=n; i>0; i--)
    {
    if (a%i==0)
    if (b%i==0)
    printf(" otvet %d\n",i);}
    system("pause");
    return 0;
}

Вот в принципе Тесты: 7 3:1 24 48:24 98 18:2
Проблема состоит в том если вести 24 и 48 чтоб он выводил только один ответ. Как это сделать?

accept · 27.12.2008, 00:57

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 <stdio.h>
#include <stdlib.h>
 
/* вычисляет НОД двух чисел */
main()
{
    unsigned getnod(int, int);
    
    printf("%d\n", getnod(-12, 16));
    return 0;
}
 
/* getnod:  возвращает НОД двух чисел */
unsigned getnod(int a, int b)
{
    unsigned nod, n1 = abs(a), n2 = abs(b);
    
    for (nod = (n1 < n2) ? n1 : n2; nod > 0; nod--)
        if (!(n1 % nod || n2 % nod))
            break;
    return nod;
}

16.02.2009, 22:37

Пипл, по этому же алгоритму, есть исходник C++ для трех целых чисел?
НОД(a, b, c)= НОД(НОД(a, b), c)

@Humanitis · 16.02.2009, 22:48

C++
1
2
3
4
5
6
7
int nod (int a, int b)
{
    if (b == 0)
        return a;
    else
        return nod (b, a % b);
}

16.02.2009, 22:52

Сообщение от Humanitis

C++
1
2
3
4
5
6
7
int nod (int a, int b)
{
    if (b == 0)
        return a;
    else
        return nod (b, a % b);
}

не понял.. это весь код?)

@Humanitis · 16.02.2009, 23:29

это для двух чисел

accept · 18.02.2009, 06:01

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
 
#include <stdio.h> 
 
int nod (int a, int b)  
{  
    if (b == 0)  
        return a;  
    else  
        return nod (b, a % b);  
}   
 
/* getnod:  возвращает НОД двух чисел */
unsigned getnod(int a, int b)
{
    unsigned nod, n1 = abs(a), n2 = abs(b);
    
    for (nod = (n1 < n2) ? n1 : n2; nod > 0; nod--)
        if (!(n1 % nod || n2 % nod))
            break;
    return nod;
}
 
/* вычисляет НОД двух чисел; в рекурсивной функции ошибка */
main()
{
    printf("%d\n", nod(-12, -16));
    printf("%d\n", getnod(-12, -16));
    return 0;
}

Code
1
2
3
4
[guest@station tmp]$ ./test
-4
4
[guest@station tmp]$

в курсе да, что знак для остатка зависит от реализации, если там делятся отрицательные

Добавлено через 3 минуты 40 секунд

Code
1
НОД(a, b, c)= НОД(НОД(a, b), c)

эта подойдёт, можно как макрос (не требует памяти), но тогда выражения будут вычисляться везде, где встретятся, можно как функцию (два раза вычисляешь НОД)

@Humanitis · 18.02.2009, 10:14

так ведь никто не мешает передавать числа в функцию со значениями по модулю

accept · 20.02.2009, 03:15

если объявлены как int - значит знаковые, обнаружил в своей косяк, не считает для нуля (когда писал думал нет наибольшего делителя)

@Humanitis · 20.02.2009, 10:16

Чтож сдаюсь, перебор лучше этой рекурсии.

accept · 23.02.2009, 18:43

не, можно наверное возвращать значение через abs, рекурсия вроде неглубокая

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h> 
 
int nod (int a, int b)  
{  
    return b == 0 ? (a == 0 ? EOF : abs(a)) : abs(nod(b, a % b));
}   
 
/* вычисляет НОД двух чисел; поправлена рекурсивная функция */
main()
{
    printf("%d\n", nod(-12, -16));
    return 0;
}

для двух нулей надо бы EOF возвращать

@grrrrr · 06.05.2009, 17:56

accept, Здравствуйте! Прокомментируйте пожалуйста вашу программа. Не могу понять как работает цикл в функции.

accept · 07.05.2009, 04:15

да, цикл работает просто: берёт меньшее из чисел и делит на него оба числа, пока не получит ситуацию, когда они оба разделились (ну до еденицы дойдёт, если они не имеют общих делителей)
тут ситуация 0 0 не рассматривается, там нод будет равен +бесконечность, и цикл ещё из двух чисел типа 0 5 вернёт ноль, хотя должен вернуть 5
юзай лучше рекурсивную версию, она в случае бесконечности возвращает EOF

@Don_Haim · 31.10.2014, 03:13

Сообщение от ElemeNT

Проблема состоит в том если вести 24 и 48 чтоб он выводил только один ответ. Как это сделать?

просто добавь еще оду функцию, что если найдено первое число, то автоматически будет прекращена работа цикла for, да, и все это нужно взять в скобки {}

C++
1
2
3
4
5
for (i=n; i>0; i--)
    {
    if (a%i==0 && b%i==0){ printf("Naibil`shiy spil`niy dil`nik - %d\n",i); break;}
    
}

P.S. Понимаю что это уже давно не нужно, но по крайней мере кому-то все-таки пригодиться, потому что сам только что игрался с этой задачей минут 20

@TheCalligrapher · 31.10.2014, 03:19

Я тоже понимаю, что это давно не нужно, но искренне надеюсь, что любители находить НОД через подобный полный перебор были отчислены и отправлены на зимние сельхозработы.

@Don_Haim · 31.10.2014, 03:48

Сообщение от TheCalligrapher

были отчислены и отправлены на зимние сельхозработы.

Просто если учишся на первом курсе в университете, там где еще не учили рекурсию, то это как-раз

@TheCalligrapher · 31.10.2014, 04:22

Сообщение от Don_Haim

Просто если учишся на первом курсе в университете, там где еще не учили рекурсию, то это как-раз

Никакой рекурсии для этого не надо. Даже в рекурсивном коде Humanitis хорошо видно, что рекурсия хвостовая, т.е. чисто косметическая.

Аналогичный алгоритм, но без рекурсии

C++
1
2
3
4
5
6
7
8
9
10
11
unsigned nod(unsigned a, unsigned b) 
{
  while (b != 0) 
  {
    unsigned next_b = a % b;
    a = b;
    b = next_b;
  }
 
  return a;
}

@Don_Haim · 31.10.2014, 04:29

Сообщение от TheCalligrapher

Даже в рекурсивном коде Humanitis хорошо видно, что рекурсия хвостовая, т.е. чисто косметическая

Если честно то эти слова мне как просто на иностранном языке которого не знаю(
Я думаю все-равно такой код кому-то понадобиться, по крайней мере такому как я

@TheCalligrapher · 31.10.2014, 07:33

Сообщение от Don_Haim

Я думаю все-равно такой код кому-то понадобиться

Вполне может быть. Многое зависит от задания.

Я исхожу из того, что когда студенту дают задание программно вычислить НОД, совсем не предполагается, что студент будет заперт в каменной башне и в полной изоляции от окружающего мира с нуля отчаянно составлять алгоритм вычисления НОД из подручных материалов. Я полагаю, что студенту разрешается провести небольшое исследование на тему существующих алгоритмов. А в таком исследовании просто невозможно пройти мимо такой классики, как алгоритм Евклида.

@Krock21rus · 15.05.2015, 13:51

столько ответов, и не одного правильного:

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main(void)
{
    int a,b,c,n,i;
    scanf("%d%d",&a,&b);
    if ((a>b)&&(b==0)) {printf("0\n");return 1;}
    if ((a<b) &&(a==0)) {printf("0\n");return 1;}
    if ((a==0) &&(b==0)) {printf("0\n");return 1;}
    if (a<b)
    {c=a;
    a=b;
    b=c;
    n=a;}
    else
    { 
    n=b;}
    for (i=n; i>0; i--)
    {
    if (a%i==0)
    if (b%i==0)
    printf("%d\n",i);}
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а привычная функция main(). . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/

klm
	16.02.2009, 22:37
	Пипл, по этому же алгоритму, есть исходник C++ для трех целых чисел? НОД(a, b, c)= НОД(НОД(a, b), c)

@Humanitis 176 / 168 / 27 Регистрация: 12.01.2009 Сообщений: 430
	16.02.2009, 23:29
	это для двух чисел 0

@Humanitis 176 / 168 / 27 Регистрация: 12.01.2009 Сообщений: 430
	18.02.2009, 10:14
	так ведь никто не мешает передавать числа в функцию со значениями по модулю 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	20.02.2009, 03:15
	если объявлены как int - значит знаковые, обнаружил в своей косяк, не считает для нуля (когда писал думал нет наибольшего делителя) 0

@Humanitis 176 / 168 / 27 Регистрация: 12.01.2009 Сообщений: 430
	20.02.2009, 10:16
	Чтож сдаюсь, перебор лучше этой рекурсии. 0

@grrrrr 49 / 49 / 13 Регистрация: 21.04.2009 Сообщений: 265
	06.05.2009, 17:56
	accept, Здравствуйте! Прокомментируйте пожалуйста вашу программа. Не могу понять как работает цикл в функции. 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	07.05.2009, 04:15
	да, цикл работает просто: берёт меньшее из чисел и делит на него оба числа, пока не получит ситуацию, когда они оба разделились (ну до еденицы дойдёт, если они не имеют общих делителей) тут ситуация 0 0 не рассматривается, там нод будет равен +бесконечность, и цикл ещё из двух чисел типа 0 5 вернёт ноль, хотя должен вернуть 5 юзай лучше рекурсивную версию, она в случае бесконечности возвращает EOF 0

@TheCalligrapher Вездепух 12932 / 6800 / 1820 Регистрация: 18.10.2014 Сообщений: 17,212
	31.10.2014, 03:19
	Я тоже понимаю, что это давно не нужно, но искренне надеюсь, что любители находить НОД через подобный полный перебор были отчислены и отправлены на зимние сельхозработы. 0