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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
Rusl_v
 Аватар для Rusl_v
13 / 12 / 1
Регистрация: 22.12.2010
Сообщений: 67
#1

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

04.03.2012, 14:50. Просмотров 1824. Ответов 3
Метки нет (Все метки)

Программа которая вычисляет наибольший общий делитель НОД двух чисел
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++ Заданы натуральные числа m и n. Найти НОД(m,n) Составить программу которая будет содержать рекурсивную функцию вычисления НОД......
Вычисление НОД. не могу понять где ошибка. C++
с++ с рекурсией C++
C++ вычисление нод
C++ Вычисление НОД
C++ Рекурсия: вычисление НОД
C++ Вычисление НОД двух натуральных чисел (рекурсия)
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
Сообщений: 74
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     Вычисление НОД рекурсией!
Ответ Создать тему
Опции темы

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