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

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

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

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

12.04.2011, 12:59. Просмотров 3427. Ответов 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]
}
можно объяснить вот про нод немножко, в частности в выделенной строке ниче не понимаю
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++
Даны натуральные числа m, n1,...,nm (m>=2). Вычислить НОД (n1,...,nm), воспользовавшись для этого соотношением...

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ailia
27 / 26 / 1
Регистрация: 27.12.2009
Сообщений: 106
12.04.2011, 13:22     вычисление нод #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <math.h>
...
int nod(int a,int b)
{
//Алгоритм Евклида: если a = bq + r, то НОД(а,b) = НОД(b,r)
int max,min;
//Находим большее по модулю число
if(a > b)
{
max = abs(a);
min = abs(b);
}
else
{
max = abs(b);
min = abs(a);
}
//находим остаток от деления большего числа на меньшее
int r = max % min;
//если остаток равен нулю
if(r == 0)
{
//то вернуть меньшее число
return min;
}
else
{
//иначе вычислить НОД меньшего числа и остатка
return nod(b,r);
}
}
p.s.: НОД - наибольший общий делитель
Dekio
Фрилансер
Эксперт С++
5837 / 1218 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
12.04.2011, 13:31     вычисление нод #3
ещё 1 алгоритм Евклида
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL,"Russian");
    int a,b;
    cout<<"Ââåäèòå 2 Г·ГЁГ±Г«Г*\n";
    cin>>a>>b;
    while(a!=b)
    {
        if(a>b)
        a-=b;
        else
        b-=a;
    }
    cout<<"ГЌГЋГ„ "<<a<<endl;
    system("pause");
    return 0;
}
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 15:03     вычисление нод #4
Для разнообразия:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
long long NOD(long long A, long long B)
{
    A = A < 0 ? -A : A;
    B = B < 0 ? -B : B;
 
    while (A != 0 && B != 0)
    {
        if (A > B)
            A %= B;
        else
            B %= A;
    }
 
    return A + B;
}
diagon
Higher
1926 / 1192 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
12.04.2011, 15:07     вычисление нод #5
Кратко=)
C++
1
2
3
4
5
6
7
8
9
10
#include <stdio.h>
#include <conio.h>
main(){
   int a,b;
   scanf("%d%d",&a,&b);
   while (b) b^=a^=b^=a%=b;
   printf("%d",a);
   getch();
   return 0;
}
Dekio
Фрилансер
Эксперт С++
5837 / 1218 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
12.04.2011, 15:09     вычисление нод #6
diagon, задержку ещё б сделать
silent_1991
12.04.2011, 15:12
  #7

Не по теме:

Dekio, консольные программы не просто так консольными называются. Их надо запускать из той среды, для которой они отцами-создателями предназначены - из консоли. А там эта задержка только мешает - хочется запустить программу, увидеть результат и без лишних телодвижений, будь даже это всего всего одно лишнее нажатие, продолжить работу.

NeRRouZ
4 / 4 / 0
Регистрация: 19.12.2010
Сообщений: 54
12.04.2011, 17:23     вычисление нод #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main()
{
     int n1,n2; 
     int nod;    
     int r; 
     scanf("%i%i", &n1, &n2);
     while (n1 % n2)
     {
       r = n1 % n2;
       n1 = n2;
       n2 = r;
     }
     nod = n2;
     printf("%i\n", nod);
   return 0;
}
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 21:29  [ТС]     вычисление нод #9
всем мерси, но мне нужно рекурсивным методом)
и если можно все-таки обясните то, что в заголовке темы)
ailia
27 / 26 / 1
Регистрация: 27.12.2009
Сообщений: 106
12.04.2011, 21:41     вычисление нод #10
вернуть нод игрека и остатка от деления иск на игрек
term1t
25 / 25 / 2
Регистрация: 04.03.2011
Сообщений: 61
12.04.2011, 21:41     вычисление нод #11
C++
1
2
3
4
5
6
7
8
9
int nod(int x, int y)      // заголовок функции. функция принимает 2 целых значения
 
{
        if ((y == 0) || (x==0))    //проверяет их на 0, если одно из них = 0
        return x;                 // наименьшим делителем будет x
        else                     // иначе 
        return nod(y, x % y);   // вызываем рекурсивную функцию, 
                               //пока не будет (y == 0) || (x==0)
}
ailia
27 / 26 / 1
Регистрация: 27.12.2009
Сообщений: 106
12.04.2011, 21:43     вычисление нод #12
кстати нод нулем быть не может, а тут может
term1t
25 / 25 / 2
Регистрация: 04.03.2011
Сообщений: 61
12.04.2011, 21:49     вычисление нод #13
упс, тогда вот так

C++
1
2
3
4
5
6
7
8
9
 int nod(int x, int y)      // заголовок функции. функция принимает 2 целых значения
 
{
        if (x % y == 0)            //если делится без остатка
        return y;                 // наименьшим делителем будет y
        else                     // иначе 
        return nod(y, x % y);   // вызываем рекурсивную функцию, 
                               //пока не будет x % y == 0
}
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 22:34  [ТС]     вычисление нод #14
ailia, получается nod это стд. ф-ция? или же это достигается специальной записью в скобках со значками всякими?

Добавлено через 1 минуту
term1t, спаисбо большое...только все равно со скобой после ретерна не въезжаю...видел так и сумму можно и разность и умнож представлять...
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 22:36     вычисление нод #15
fruktik,
1. Гуглим "Рекурсия";
2. Читаем 12 раз;
3. Читаем ещё, пока не достигнем полного просветления;
4. ???????
5. PROFIT
fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 22:39  [ТС]     вычисление нод #16
silent_1991, не парень, рекурсию разобрал))насчет этого проблем нету
я про ...... ретерн(х, у)....получается это возвратит сумму икс и игрек?
а разными комбинациями мы уже можем добиться нод, нок, деления, умножения рекурсивного так?
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.04.2011, 22:41     вычисление нод #17
fruktik, а где вы здесь вообще return (x, y); видите? Всю тему ещё раз пересмотрел - в упор такого не увидел. Максимум, что видел, это return nod(y, x % y);, что опять-таки возвращает нас к рекурсии...
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?...
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.04.2011, 22:56     вычисление нод
Еще ссылки по теме:

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

НОД - C++
Написать программу которая из двух чисел x и y ищет наибольший общий делитель

НОД - C++
Нужно доработать код, чтобы находить НОД трех чисел, пожалуйста) #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &lt;locale.h&gt; using...


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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт С++
4958 / 3034 / 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.
Yandex
Объявления
12.04.2011, 22:56     вычисление нод
Ответ Создать тему
Опции темы

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