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

Вычисление НОД рекурсией! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
Rusl_v
 Аватар для Rusl_v
13 / 12 / 1
Регистрация: 22.12.2010
Сообщений: 67
04.03.2012, 14:50     Вычисление НОД рекурсией! #1
Программа которая вычисляет наибольший общий делитель НОД двух чисел
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include "stdafx.h"
#include <iostream>
using namespace std;
int nod(int,int);
 
int _tmain(int argc, _TCHAR* argv[])
{
    setlocale(LC_ALL,"Russian");
    int x,y;
    cin>>x>>y;
    cout<<nod(x,y)<<endl;
    system("pause");
    return 0;
}
int nod(int x,int y){
    if (y==0) return x;
    return nod(y,x%y);
}
return nod(y,x%y); Объясните пожалуйста этот вызов рекурсии, как она вычисляет нод?
Как я понимаю например: если вводим x=8 и y=20
Рекурсия принимает значение nod(20 , 8%20) следующий вызов будет nod(20, 8%20) т.к. return nod(y,x%y);
Помогите разобраться с этой непонятной рекурсией блин
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2012, 14:50     Вычисление НОД рекурсией!
Посмотрите здесь:

Вычисление НОД. не могу понять где ошибка. C++
C++ вычисление нод
C++ Вычисление НОД
C++ Рекурсия: вычисление НОД
C++ Вычисление НОД двух натуральных чисел (рекурсия)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Eugen-S
 Аватар для Eugen-S
8 / 8 / 0
Регистрация: 06.11.2011
Сообщений: 122
04.03.2012, 16:40     Вычисление НОД рекурсией! #2
Попробуй прописать вывод значений, внутри функции, чтоб проследить как изменяются аргументы
Mayonez
04.03.2012, 18:17
  #3

Не по теме:

Цитата Сообщение от Rusl_v Посмотреть сообщение
Помогите разобраться с этой непонятной рекурсией блин
чтобы понять рекурсию - нужно сначала понять рекурсию

starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 71
04.03.2012, 18:30     Вычисление НОД рекурсией! #4
Функция может вызвать сама себя. Такой способ вычислений называется рекурсией.
Привожу пример работающей функции вычисления НОД:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* прототипы функций */
/* нахождение наибольшего общего делителя
   двух целых чисел
   используются свойства НОД:
   nod(n1,n2)=nod(n2,n1)
   nod(0, n2)=n2
   nod(n1,n2)=nod(n2,n3) где n3=n1%n2
*/
int nod(int n1, int n2);
...
/* вычисление НОД: рекурсия */
int nod(int n1, int n2)
{
  if(n1==0) return n2;
  return nod(n2%n1,n1);
}
при вызове функции (например, nod(8, 12) ) функция натыкается на return nod(4,8) - потому что 12%8=4. Тогда она запускает новый вызов функции nod. Далее она наткнется на вызов nod(4%8,8) и так далее - пока не обнаружится n1==0.
Yandex
Объявления
04.03.2012, 18:30     Вычисление НОД рекурсией!
Ответ Создать тему
Опции темы

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