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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.77
fruktik
 Аватар для fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 12:59     вычисление нод #1
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++ Заданы натуральные числа m и n. Найти НОД(m,n) Составить программу которая будет содержать рекурсивную функцию вычисления НОД......
Вычисление НОД. не могу понять где ошибка. C++
C++ Вычисление НОД рекурсией!
C++ Вычисление НОД
C++ Рекурсия: вычисление НОД
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
Фрилансер
Эксперт C++
 Аватар для Dekio
5817 / 1215 / 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
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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
 Аватар для diagon
1921 / 1187 / 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
Фрилансер
Эксперт C++
 Аватар для Dekio
5817 / 1215 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
12.04.2011, 15:09     вычисление нод #6
diagon, задержку ещё б сделать
silent_1991
12.04.2011, 15:12
  #7

Не по теме:

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

NeRRouZ
 Аватар для 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
 Аватар для 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
 Аватар для 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
 Аватар для 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
 Аватар для fruktik
32 / 32 / 3
Регистрация: 03.03.2011
Сообщений: 302
12.04.2011, 22:34  [ТС]     вычисление нод #14
ailia, получается nod это стд. ф-ция? или же это достигается специальной записью в скобках со значками всякими?

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

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4945 / 3021 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 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     вычисление нод
Ответ Создать тему
Опции темы

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