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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.88
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
#1

Вычисление НОД двух натуральных чисел (рекурсия) - C++

03.05.2012, 12:28. Просмотров 3328. Ответов 21
Метки нет (Все метки)

День добрый, помогите пожалуйста поправить данную прогу, надо бы избавиться от меток, короче говоря, сократить строки.

Вот сама задачка.

Составить программу нахождения НОД двух натуральных чисел
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
    #include <conio.h>
    #include <math.h>
    void main()
    {
 
     int b, m, n, r, k, k1;
     clrscr();
     printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&m);
     printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&n);
     m=abs(m);
     n=abs(n);
     if(m==0 && n==0)
     {
    printf("NEVERNYI VVOD \n\n");
//======================================
     goto v2;     }
 
     if(n>m)
     {
     b=n;
     n=m;
     m=b;
     }
 
     r=n%m;
     if(r==0)
     {
     printf("\n NOD(m,n)= %i", r);
     goto v2;
     }
    v1: k=m%r;
     if (k>0)
     {
     k1=r%k;
     r=k;
     k=k1;
    goto v1;
     }
     printf("\nNOD(m,n)= %i", r);
 
    v2: printf("\nNazhmite lubuyu klavishu");
 
     getch();
     }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2012, 12:28     Вычисление НОД двух натуральных чисел (рекурсия)
Посмотрите здесь:

Используя функцию нахождения НОД двух натуральных чисел, сократить обычную дробь C++
C++ Написать функции рекурсивной и не рекурсивной реализации алгоритма Евклида нахождения наибольшего общего делителя (НОД) двух натуральных чисел
Рекурсия: сложение, вычитание, деление и вычисление остатка от деления двух целых чисел C++
C++ Рекурсия: вычисление НОД
C++ Найти наибольший общий делитель (НОД) двух введенных натуральных чисел, используя алгоритм Евклида
Вычисление нок и нод переменных натуральных чисел C++
C++ Вычислить НОД (наибольший общий делитель) двух натуральных чисел A и B
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
03.05.2012, 12:57     Вычисление НОД двух натуральных чисел (рекурсия) #2
избавьтесь от goto, тут вам не бейсик, goto не рекомендуется использоваться
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
 
int calc_gcd( int a, int b ) {
    return b == 0 ? ( a == 0 ? 0 : abs( a ) ) : abs( calc_gcd( b, a % b ) );
}
 
int main( void ) {
    int a, b, gcd;
    puts( "Введите два целых числа через пробел" );
    scanf( "%d%d", &a, &b );
    gcd = calc_gcd( a, b );
    gcd ?
            printf( "Наибольший общий делитель этих чисел = %d", gcd )
            :
            puts( "Не существует наибольшего общего делителя для этих чисел" );
    return EXIT_SUCCESS;
}
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 13:10  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #3
panicwassano,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<conio.h>
void main()
{ clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
while (a!=b) do {
        if (a>b) a-=b; else b-=a;
        }
printf("NOD chisel %i i %i = %i"a,b,a);
}
но так шо то не катит...
А по вашему когду...классно, работает, только препод подставу спалит=) ...
мой если можете подкорректните

Добавлено через 1 минуту
одну ошибку выдает почему то...
printf("NOD chisel %i i %i = %i"a,b,a);
}
Добавлено через 19 секунд
в этом районе
amfisat
 Аватар для amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 235
03.05.2012, 13:12     Вычисление НОД двух натуральных чисел (рекурсия) #4
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<conio.h>
#include <cstdio>
void main()
{ clrscr();
    int a;
    int b;
    int c;
    printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
    printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
    printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
    c = a;
    while (a!=b) {
        if (a>b) a-=b; else b-=a;
    }
    printf("NOD chisel %i i %i = %i", c, b, a);
}
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 13:35  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #5
amfisat, точно, тут же нету DO
вот я...

Добавлено через 6 минут
panicwassano, только вы блин не забыли что надо функцию=)

Добавлено через 12 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<conio.h>
int nod(int A, int B);
void main()
{ clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
c=nod(a,b);
printf("\ n NOD(%i , %i) = %i", a,b,c);
getch();
}
int nod(int A, int B)
{
while (A!=B) {
         if (A>B) A-=B; else B-=A;
         }
return(A);
}
panicwassano
591 / 559 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
03.05.2012, 14:43     Вычисление НОД двух натуральных чисел (рекурсия) #6
MoSanya это не рекурсия, это алгоритм евклида
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 15:33  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #7
panicwassano, а как тогда мне "подключить" рекурсию?

Добавлено через 28 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
#include<conio.h>
void main()
{ clrscr();
int a;
int b;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
while (a!=b) {
         if (a>b) a-=b; else b-=a;
         }
 
printf("\ n NOD(%i , %i) = %i", a,b,a);
getch();
}


это рекурсия?
amfisat
 Аватар для amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 235
03.05.2012, 15:39     Вычисление НОД двух натуральных чисел (рекурсия) #8
Рекурсивная функция - это функция, которая, выполняя определенные действия, в процессе работы вызывает саму себя какое-то количество раз.

рекурсивное нахождение нод
C++
1
2
3
4
5
6
int nod(int x, int y) 
{ 
if (y == 0)  // надо ставить условие окончания рекурсии, иначе будет плохо
return x; 
return nod(y, x % y); //о-па: сама себя вызывает
}
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 16:35  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #9
amfisat, а вне функции как выглядит? так?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<conio.h>
void main()
{ clrscr();
int a;
int b;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
while (a!=b) { 
if (b == 0)  // надо ставить условие окончания рекурсии, иначе будет плохо
return a; 
return nod(y, x % y); //о-па: сама себя вызывает (тут как? ) 
} 
 
printf("\ n NOD(%i , %i) = %i", a,b,a);
getch();
}


ЧТО ТО Я ЗАПУТАЛ И ВАС ВСЕХ И САМ.
ДАВАЙТЕ РЕКУРСИЮ БЕЗ ФУНКЦИИ СДЕЛАЕМ...
amfisat
 Аватар для amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 235
03.05.2012, 16:55     Вычисление НОД двух натуральных чисел (рекурсия) #10
ЧТО ТО Я ЗАПУТАЛ И ВАС ВСЕХ И САМ.
ДАВАЙТЕ РЕКУРСИЮ БЕЗ ФУНКЦИИ СДЕЛАЕМ...
Ну и как вы себе это представляете? Чем вас функция не устраивает?

Определитесь: либо цикл, либо рекурсия (функция).

C++
1
2
3
4
5
6
7
8
void main() 
{ ...
while (a!=b) { 
if (b == 0)  // надо ставить условие окончания рекурсии, иначе будет плохо
return a; //к чему тут return? К main? - так она же void! - ничего не должна возвращать. 
return nod(y, x % y);  // что такое nod? - где это определено? - это функция! - определяйте ее до или после main. И опять-таки: return - к чему?
}
...}
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 16:57  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #11
amfisat, давайте чисто рекурсия. можете мне написать?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.05.2012, 17:01     Вычисление НОД двух натуральных чисел (рекурсия) #12
Вы хоть понимаете значение термина в программировании "рекурсия"? Ее невозможно сделать без функции.
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 17:02  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #13
Toshkarik, так мне и надо БЕЗ функции. функция уже сделана
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.05.2012, 17:04     Вычисление НОД двух натуральных чисел (рекурсия) #14
Какая функция сделана? О чем Вы? Кроме функции main у Вас больше их нет в программе. Вы не понимаете термина рекурсия и/или функция.
amfisat
 Аватар для amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 235
03.05.2012, 17:07     Вычисление НОД двух натуральных чисел (рекурсия) #15
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
 
int nod(int x, int y) 
{ 
if (y == 0) 
return x; 
return nod(y, x % y);
} 
 
void main()
{clrscr();
int a;
int b;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
 
printf("\ n NOD(%i , %i) = %i", a, b, nod(a,b));
getch();
}
Добавлено через 40 секунд
Я сдаюсь: не знаю, что еще предложить.
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.05.2012, 17:12     Вычисление НОД двух натуральных чисел (рекурсия) #16
C
1
2
3
long int gcd( const long int x, const long int y ) {
   return ( y == 0 ? x : gcd( y, x % y ));
}
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 17:12  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #17
\ сам запутался=)
Toshkarik, щас.... вот эта программа с использованием функции...
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<stdio.h>
#include<conio.h>
int nod(int A, int B);
void main()
{ clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
c=nod(a,b);
printf("\ n NOD(%i , %i) = %i", a,b,c);
getch();
}
int nod(int A, int B)
{
while (A!=B) {
         if (A>B) A-=B; else B-=A;
         }
return(A);
}
а вот теперь мне эта же программа нужна с использованием рекурсии. теперь вроде понятно должно стать нам всем
amfisat
 Аватар для amfisat
67 / 67 / 1
Регистрация: 16.06.2009
Сообщений: 235
03.05.2012, 17:14     Вычисление НОД двух натуральных чисел (рекурсия) #18
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
 
int nod(int A, int B);
 
void main()
{clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
 c = nod(a,b);
printf("\ n NOD(%i , %i) = %i", a, b, c);
getch();
}
 
int nod(int A, int B)
{ 
if (B == 0) 
return A; 
return nod(B, A % B);
}
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 51
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.05.2012, 17:14     Вычисление НОД двух натуральных чисел (рекурсия) #19
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<conio.h>
long int gcd( const long int x, const long int y ) {
   return ( y == 0 ? x : gcd( y, x % y ));
}
void main()
{ clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: -->   "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: -->   "); scanf("%i",&b);
c=gcd(a,b);
printf("\ n NOD(%i , %i) = %i", a,b,c);
getch();
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2012, 17:16     Вычисление НОД двух натуральных чисел (рекурсия)
Еще ссылки по теме:

Нод для двух натуральных чисел с циклом for C++
C++ Подправить код. НОД двух натуральных чисел
Вычисление НОД ряда натуральных чисел C++
Нод для 2-х заданных натуральных чисел с циклом while C++
Последовательность натуральных чисел, вычисление их НОД методом Евклида C++

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

Или воспользуйтесь поиском по форуму:
MoSanya
6 / 6 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 17:16  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #20
Цитата Сообщение от Toshkarik Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
#include<conio.h>
long int gcd( const long int x, const long int y ) {
 return ( y == 0 ? x : gcd( y, x % y ));
}
void main()
{ clrscr();
int a;
int b;
int c;
printf("Vichislenie NOD 2-x natural`nyh chisel \n" );
printf("\n Vvedite 1-oe chislo: --> "); scanf("%i",&a);
printf("\n Vvedite 2-oe chislo: --> "); scanf("%i",&b);
c=gcd(a,b);
printf("\ n NOD(%i , %i) = %i", a,b,c);
getch();
}
так я сделал, но это разве рекурсия?
Yandex
Объявления
03.05.2012, 17:16     Вычисление НОД двух натуральных чисел (рекурсия)
Ответ Создать тему
Опции темы

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