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

@MoSanya · Регистрация: 16.10.2011

Author24 — интернет-сервис помощи студентам

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

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

Составить программу нахождения НОД двух натуральных чисел

C++

#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 · 03.05.2012, 12:57

избавьтесь от goto, тут вам не бейсик, goto не рекомендуется использоваться

C

#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 · 03.05.2012, 13:10 **[ТС]**

panicwassano,

C++

#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 · 03.05.2012, 13:12

C

#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 · 03.05.2012, 13:35 **[ТС]**

amfisat, точно, тут же нету DO

вот я...

Добавлено через 6 минут
panicwassano,

только вы блин не забыли что надо функцию=)

Добавлено через 12 минут

C++

#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 · 03.05.2012, 14:43

MoSanya это не рекурсия, это алгоритм евклида

@MoSanya · 03.05.2012, 15:33 **[ТС]**

panicwassano, а как тогда мне "подключить" рекурсию?

Добавлено через 28 минут

C++

#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 · 03.05.2012, 15:39

Рекурсивная функция - это функция, которая, выполняя определенные действия, в процессе работы вызывает саму себя какое-то количество раз.

рекурсивное нахождение нод

C++

int nod(int x, int y) 
{ 
if (y == 0)  // надо ставить условие окончания рекурсии, иначе будет плохо
return x; 
return nod(y, x % y); //о-па: сама себя вызывает
}

@MoSanya · 03.05.2012, 16:35 **[ТС]**

amfisat, а вне функции как выглядит? так?

C++

#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 · 03.05.2012, 16:55

ЧТО ТО Я ЗАПУТАЛ И ВАС ВСЕХ И САМ.
ДАВАЙТЕ РЕКУРСИЮ БЕЗ ФУНКЦИИ СДЕЛАЕМ...

Ну и как вы себе это представляете? Чем вас функция не устраивает?

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

C++

void main() 
{ ...
while (a!=b) { 
if (b == 0)  // надо ставить условие окончания рекурсии, иначе будет плохо
return a; //к чему тут return? К main? - так она же void! - ничего не должна возвращать. 
return nod(y, x % y);  // что такое nod? - где это определено? - это функция! - определяйте ее до или после main. И опять-таки: return - к чему?
}
...}

@MoSanya · 03.05.2012, 16:57 **[ТС]**

amfisat, давайте чисто рекурсия. можете мне написать?

@Toshkarik · 03.05.2012, 17:01

Вы хоть понимаете значение термина в программировании "рекурсия"? Ее невозможно сделать без функции.

@MoSanya · 03.05.2012, 17:02 **[ТС]**

Toshkarik, так мне и надо БЕЗ функции. функция уже сделана

@Toshkarik · 03.05.2012, 17:04

Какая функция сделана? О чем Вы? Кроме функции main у Вас больше их нет в программе. Вы не понимаете термина рекурсия и/или функция.

@amfisat · 03.05.2012, 17:07

C++

#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 · 03.05.2012, 17:12

C

1
2
3

long int gcd( const long int x, const long int y ) {
   return ( y == 0 ? x : gcd( y, x % y ));
}

@MoSanya · 03.05.2012, 17:12 **[ТС]**

\ сам запутался=)
Toshkarik, щас.... вот эта программа с использованием функции...

C

#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 · 03.05.2012, 17:14

C++

#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 · 03.05.2012, 17:14

C

#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();
}

@MoSanya · 03.05.2012, 17:16 **[ТС]**

Сообщение от Toshkarik

C++

#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();
}

так я сделал, но это разве рекурсия?

@panicwassano 601 / 569 / 104 Регистрация: 07.11.2010 Сообщений: 2,004
	03.05.2012, 14:43	6
	MoSanya это не рекурсия, это алгоритм евклида 0

@MoSanya 6 / 6 / 2 Регистрация: 16.10.2011 Сообщений: 226
	03.05.2012, 16:57 [ТС]	11
	amfisat, давайте чисто рекурсия. можете мне написать? 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	03.05.2012, 17:01	12
	Вы хоть понимаете значение термина в программировании "рекурсия"? Ее невозможно сделать без функции. 1

@MoSanya 6 / 6 / 2 Регистрация: 16.10.2011 Сообщений: 226
	03.05.2012, 17:02 [ТС]	13
	Toshkarik, так мне и надо БЕЗ функции. функция уже сделана 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	03.05.2012, 17:04	14
	Какая функция сделана? О чем Вы? Кроме функции main у Вас больше их нет в программе. Вы не понимаете термина рекурсия и/или функция. 1