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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.77
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
#1

вычисление нод - C++

12.04.2011, 12:59. Просмотров 3695. Ответов 24
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
int nod(int x, int y)
 
{
        if ((y == 0) || (x==0))
        return x;
        else        
        [B]return nod(y, x % y);[/B]
}
можно объяснить вот про нод немножко, в частности в выделенной строке ниче не понимаю
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2011, 12:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос вычисление нод (C++):

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

Вычисление НОД рекурсией! - C++
Программа которая вычисляет наибольший общий делитель НОД двух чисел #include "stdafx.h" #include <iostream> using namespace std; ...

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

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

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

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

24
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 22:39  [ТС] #16
silent_1991, не парень, рекурсию разобрал))насчет этого проблем нету
я про ...... ретерн(х, у)....получается это возвратит сумму икс и игрек?
а разными комбинациями мы уже можем добиться нод, нок, деления, умножения рекурсивного так?
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 22:41 #17
fruktik, а где вы здесь вообще return (x, y); видите? Всю тему ещё раз пересмотрел - в упор такого не увидел. Максимум, что видел, это return nod(y, x % y);, что опять-таки возвращает нас к рекурсии...
0
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 22:51  [ТС] #18
silent_1991, описался

Добавлено через 4 минуты
C++
1
2
3
4
5
6
int summa(int x, int y) 
       {
       if (x == 0) return y;
       if (y == 0) return x;
       return summa(x -1, y)+1;
       }
вот при сумме например при икс = 8 игрек = 7 получится в результате рекурсии (0, 7)+8
как из return summa(0, 7)+8 получится 15?...
0
term1t
25 / 25 / 2
Регистрация: 04.03.2011
Сообщений: 61
12.04.2011, 22:53 #19

Не по теме:

тут я что-то напутал, ssory



Добавлено через 1 минуту
как из return summa(0, 7)+8 получится 15?...
if (x == 0) return y; а строкой выше x = 0

значит вернется 7 ( т. е. у), и к нему еще прибавиться 8, а 7 + 8 = 15
1
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 22:56 #20
fruktik,
Разворачиваем рекурсикю:
1. x = 8, y = 7: summa(7, 7) + 1;
2. x = 7, y = 7: summa(6, 7) + 1;
3. x = 6, y = 7: summa(5, 7) + 1;
4. x = 5, y = 7: summa(4, 7) + 1;
5. x = 4, y = 7: summa(3, 7) + 1;
6. x = 3, y = 7: summa(2, 7) + 1;
7. x = 2, y = 7: summa(1, 7) + 1;
8. x = 1, y = 7: summa(0, 7) + 1;

Дошли до базиса:
9. x = 0, y = 7: 7;

Разворачиваем рекурсию (то, что после =, подставится вместо summa(x, y) в каждом из соответствующих пунктов):
8. 7 + 1 = 8;
7: 8 + 1 = 9;
6. 9 + 1 = 10;
5. 10 + 1 = 11;
4. 11 + 1 = 12;
3. 12 + 1 = 13;
2. 13 + 1 = 14;
1. 14 + 1 = 15.
1
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 23:06  [ТС] #21
silent_1991, как вот подклинит иогда...смотрю- и все равно не очень понимаю разворот рекурсии, что откуда берется:
8. 7 + 1 = 8;
7: 8 + 1 = 9;
6. 9 + 1 = 10;
5. 10 + 1 = 11;
4. 11 + 1 = 12;
3. 12 + 1 = 13;
2. 13 + 1 = 14;
1. 14 + 1 = 15.

мда...надеюсь вдохновение придет
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 23:10 #22
То, что в пункте 8 при свёртке рекурсии стоит после равно (т.е. 8), подставится в пункт 8 при развороте рекурсии вместо summa. Получится 8 + 1 = 9. Эта 9 вернётся в пункт 7 и подставится вместо summa, получим 9 + 1 = 10. И т.д.
1
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
16.04.2011, 16:04  [ТС] #23
silent_1991, ахахах,...прикалываете, дошло)))

Добавлено через 2 минуты
Цитата Сообщение от ailia Посмотреть сообщение
p.s.: НОД - наибольший общий делитель
ну спасибо, открыли))...мне кажется это еще все с 5-6 класса знают, когда находят эти ноды и ноки раскладыванием на простые множители
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
16.04.2011, 18:26 #24
Shortest code
C++
1
2
templete<typename T>
T gcd(const T &a, const &T b) { return a ? gcd(b%a, a) : b; }
0
silent_1991
16.04.2011, 18:31     вычисление нод
  #25

Не по теме:

outoftime, не вижу смысла в шаблонности таких функций. А что, если я захочу вычислить НОД двух строк? Лучше уж явно перегрузить функцию для всех возможных типов параметров, благо их не много, более "короткие" параметры всё равно автоматически будут приведены к более "длинным". Поэтому достаточно описать функцию для максимального long long, а также, если возникнет необходимость, перегрузить для особых типов (например, для какого-нибудь самописного Verylong)

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.04.2011, 18:31
Привет! Вот еще темы с ответами:

Вычисление НОД. не могу понять где ошибка. - 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++
Здравствуйте. Искал подобную тему по форуму, но там все либо на 2 числа либо на несколько, но с фиксированным числом после компиляции....

Последовательность натуральных чисел, вычисление их НОД методом Евклида - C++
Уважаемые форумчане, прошу помощи в решении задачи: Составьте программу, которая позволяет организовать ввод последовательности...

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


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

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

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