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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 26, средняя оценка - 4.88
MoSanya
5 / 5 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 12:28     Вычисление НОД двух натуральных чисел (рекурсия) #1
День добрый, помогите пожалуйста поправить данную прогу, надо бы избавиться от меток, короче говоря, сократить строки.

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

Составить программу нахождения НОД двух натуральных чисел
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();
     }
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
panicwassano
590 / 558 / 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
5 / 5 / 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
5 / 5 / 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
590 / 558 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
03.05.2012, 14:43     Вычисление НОД двух натуральных чисел (рекурсия) #6
MoSanya это не рекурсия, это алгоритм евклида
MoSanya
5 / 5 / 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
5 / 5 / 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
5 / 5 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 16:57  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #11
amfisat, давайте чисто рекурсия. можете мне написать?
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 03.08.2011
Сообщений: 2,381
Завершенные тесты: 1
03.05.2012, 17:01     Вычисление НОД двух натуральных чисел (рекурсия) #12
Вы хоть понимаете значение термина в программировании "рекурсия"? Ее невозможно сделать без функции.
MoSanya
5 / 5 / 0
Регистрация: 16.10.2011
Сообщений: 226
03.05.2012, 17:02  [ТС]     Вычисление НОД двух натуральных чисел (рекурсия) #13
Toshkarik, так мне и надо БЕЗ функции. функция уже сделана
Toshkarik
 Аватар для Toshkarik
1139 / 856 / 50
Регистрация: 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 / 50
Регистрация: 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
5 / 5 / 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 / 50
Регистрация: 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     Вычисление НОД двух натуральных чисел (рекурсия)
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
MoSanya
5 / 5 / 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     Вычисление НОД двух натуральных чисел (рекурсия)
Ответ Создать тему
Опции темы

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