Составить рекурсивную функцию вычисления НОД

@Mark33 · Регистрация: 13.09.2012

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

Даны натуральные числа n и m; Найти НОД(n,m). составить рекурсивную функцию вычисления НОД, основанную на соотношении НОД(n, m)=НОД(m, r), где r- остаток от деления n на m(n>m)

@Nixy · 20.12.2012, 23:38

пробовали найти на форуме ? думаете вы первый кому нужен НОД? тем более рекурсией

@Mark33 · 20.12.2012, 23:50 **[ТС]**

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

пробовали найти на форуме ? думаете вы первый кому нужен НОД? тем более рекурсией

на форуме туфта, которая не компилируется, а сам я мало в этом понимаю, хотя очень хотелось бы понять

а может и не туфта, в любом случае понять хочется, а никто не объяснит, все умные, но занятые, "всё есть на форуме"....коль было бы разъяснено, я б уже давно настрочил что надо сам

@komand0 · 20.12.2012, 23:58

C++

#include <iostream>
 
int nod(int n, int m)
{
    if(m==0)
        return n;
    if(n>m)
        return nod(m,n%m);
    else
        return nod(n,m%n);
}
 
int main ()
{
    std::cout << nod(12,8);
    system("PAUSE");
    return 0;
}

Добавлено через 45 секунд
строго по тому что вы написали в задании

@radamaerl · 21.12.2012, 00:10

вобще то НОД определен для n и m не нулевых

@komand0 · 21.12.2012, 00:19

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

вобще то НОД определен для n и m не нулевых

если вы о

C++

1 2	if(m==0) return n;

то это условие выхода из рекурсии

@radamaerl · 21.12.2012, 00:58

в этом случае НОД(12,0)=12
Эвклид в шоке
ну это к слову, просто чтобы человек понимал где препод может придраться и смог объяснить
тогда можно упростить

C++

int nod(int n, int m)
{
    if (m==0)
        return n;
    return nod(m,n%m);
}

ну не упростить
уменьшить длину кода

@Mark33 · 21.12.2012, 01:12 **[ТС]**

вопрос такой, что такое вообще - этот НОД?

Croessmah · 21.12.2012, 01:15

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

вопрос такой, что такое вообще - этот НОД?

Наибольший Общий Делитель

@radamaerl · 21.12.2012, 01:21

Mark33, ты чисто по приколу для себя разбираешься или сдать гдето надо?

@Mark33 · 21.12.2012, 12:39 **[ТС]**

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

Mark33, ты чисто по приколу для себя разбираешься или сдать гдето надо?

Чисто по приколу ДА, немного
первокур я, разобраться просто надо и хочется
да в вообще, задачку эту сдать бы

@radamaerl · 21.12.2012, 13:08

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

C++

int nod(int n, int m)
{
    if (n%m==0)
        return m;
    return nod(m,n%m);
}

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

Добавлено через 12 минут
короче если вводить по твоему условию (n>m) и n,m не равны 0 то есть грамотно то работает все
в последнем случае просто условий меньше в самой функции и m не может быть равен 0
и четко по по твоему условию поиска НОД
НОД(n, m)=НОД(m, r), где r- остаток от деления n на m(n>m)

@Mark33 0 / 0 / 0 Регистрация: 13.09.2012 Сообщений: 13
	21.12.2012, 12:39 [ТС]	11
	Сообщение от radamaerl Mark33, ты чисто по приколу для себя разбираешься или сдать гдето надо? Чисто по приколу ДА, немного первокур я, разобраться просто надо и хочется да в вообще, задачку эту сдать бы 0

@Nixy ComfyMobile 401 / 282 / 34 Регистрация: 24.07.2012 Сообщений: 916
	20.12.2012, 23:38	2
	пробовали найти на форуме ? думаете вы первый кому нужен НОД? тем более рекурсией 0

@Mark33 0 / 0 / 0 Регистрация: 13.09.2012 Сообщений: 13
	20.12.2012, 23:50 [ТС]	3
	Сообщение от Nixy пробовали найти на форуме ? думаете вы первый кому нужен НОД? тем более рекурсией на форуме туфта, которая не компилируется, а сам я мало в этом понимаю, хотя очень хотелось бы понять а может и не туфта, в любом случае понять хочется, а никто не объяснит, все умные, но занятые, "всё есть на форуме"....коль было бы разъяснено, я б уже давно настрочил что надо сам 0

@radamaerl 27 / 6 / 1 Регистрация: 20.12.2012 Сообщений: 39
	21.12.2012, 00:10	5
	вобще то НОД определен для n и m не нулевых 0

@Mark33 0 / 0 / 0 Регистрация: 13.09.2012 Сообщений: 13
	21.12.2012, 01:12 [ТС]	8
	вопрос такой, что такое вообще - этот НОД? 0

Croessmah Неэпический 17870 / 10635 / 2054 Регистрация: 27.09.2012 Сообщений: 26,737 Записей в блоге: 1
	21.12.2012, 01:15	9
	Сообщение от Mark33 вопрос такой, что такое вообще - этот НОД? Наибольший Общий Делитель 0

@radamaerl 27 / 6 / 1 Регистрация: 20.12.2012 Сообщений: 39
	21.12.2012, 01:21	10
	Mark33, ты чисто по приколу для себя разбираешься или сдать гдето надо? 0

	21.12.2012, 13:08