Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

04.03.2012, 14:50. Просмотров 2286. Ответов 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);
Помогите разобраться с этой непонятной рекурсией блин
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2012, 14:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Вычисление НОД рекурсией! (C++):

Вычисление факториала циклом и рекурсией - C++
Помогите с вычислением выражения: S=(1/1!)+(1/2!)+...+(1/k!) C++, циклом и рекурсией.

Вычисление НОД - C++
Составить программу для вычисления НОД двух натуральных чисел вот еще одна програмка.

вычисление нод - C++
int nod(int x, int y) { if ((y == 0) || (x==0)) return x; else return nod(y, x % y); ...

Вычисление НОД и НОК - C++
Нужно написать программу по вычислению НОД и НОК. Мысли проскакивают, но не полное решение). Подскажите кто сможет, только не кидайте...

Рекурсия: вычисление НОД - C++
Даны натуральные числа n,m; найти НОД(n,m). Использовать программу, включающую рекурсивную процедуру вычисления НОД, основанную на...

Вычисление НОД ряда натуральных чисел - C++
Даны натуральные числа m, n1,...,nm (m&gt;=2). Вычислить НОД (n1,...,nm), воспользовавшись для этого соотношением...

3
Eugen-S
8 / 8 / 0
Регистрация: 06.11.2011
Сообщений: 122
04.03.2012, 16:40 #2
Попробуй прописать вывод значений, внутри функции, чтоб проследить как изменяются аргументы
0
Mayonez
04.03.2012, 18:17
  #3

Не по теме:

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

0
starikNAD
11 / 11 / 3
Регистрация: 01.12.2010
Сообщений: 83
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.
0
04.03.2012, 18:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.03.2012, 18:30
Привет! Вот еще темы с ответами:

Вычисление НОД. не могу понять где ошибка. - C++
#include &quot;stdio.h&quot; #include &quot;conio.h&quot; int NOD (int x,int y) { while (x!=y) { if (x&gt;y) {x==x-y;}; if (y&gt;x) {x==y-x;}; ...

Вычисление НОД двух натуральных чисел (рекурсия) - C++
День добрый, помогите пожалуйста поправить данную прогу, надо бы избавиться от меток, короче говоря, сократить строки. Вот сама...

Вычисление нок и нод переменных натуральных чисел - C++
Здравствуйте. Искал подобную тему по форуму, но там все либо на 2 числа либо на несколько, но с фиксированным числом после компиляции....

Вычисление НОД по алгоритму Евклида (как организовать код?) - C++
Всем доброго время суток, помогите составить код задачи, я знаю как ее решить, но не знаю как правильно организовать. Вот условие...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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