Ejercicio Euclides
Publicado por Axel (1 intervención) el 29/07/2018 23:18:31
Hola, soy nuevo en todo el mundo de la programación y estoy tratando de aprender un poco por mi cuenta, por lo que espero puedan perdonar mi inexperiencia y el nivel tan básico.
El problema es este:
El algoritmo más famoso de la historia es el algoritmo de Euclides que sirve para calcular el máximo común divisor (MCD) de dos números. Para encontrarlo, se realizan restas sucesivas, restando el número más pequeño al número más grande, hasta que los dos números son iguales.
Para calcular el MCD de A=26 y B=36, realizaremos las siguientes restas hasta que A y B sean iguales.
y por lo tanto, el MCD de 26 y 36 es 2.
Entrada
Dos números enteros, A y B
Salida
Una sola línea que contiene un número entero, el MCD de los dos números de la entrada.
Ejemplo
Entrada Salida
26 36 2
Límites
1<=A, B<=2^62
Hice este algoritmo y todo parece estar bien, el problema es que al evaluarlo, este excede el tiempo limite de cada caso, y quería saber de qué forma puedo optimizarlo.
Se los agradezco de antemano.
El problema es este:
El algoritmo más famoso de la historia es el algoritmo de Euclides que sirve para calcular el máximo común divisor (MCD) de dos números. Para encontrarlo, se realizan restas sucesivas, restando el número más pequeño al número más grande, hasta que los dos números son iguales.
Para calcular el MCD de A=26 y B=36, realizaremos las siguientes restas hasta que A y B sean iguales.
y por lo tanto, el MCD de 26 y 36 es 2.
Entrada
Dos números enteros, A y B
Salida
Una sola línea que contiene un número entero, el MCD de los dos números de la entrada.
Ejemplo
Entrada Salida
26 36 2
Límites
1<=A, B<=2^62
Hice este algoritmo y todo parece estar bien, el problema es que al evaluarlo, este excede el tiempo limite de cada caso, y quería saber de qué forma puedo optimizarlo.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
int main(void){
int a,b;scanf("%d%d",&a,&b);
while(a!=b){
if(a>b){
a = a - b;
} else{b = b - a;
} }printf("%d",a);
}Se los agradezco de antemano.
Valora esta pregunta
0