Resultados 1 al 5 de 5

Tema: problema de recursion

  1. #1 problema de recursion 
    Iniciado
    Fecha de ingreso
    Apr 2006
    Mensajes
    15
    Descargas
    0
    Uploads
    0
    hola, tengo un problema que me tiraron en la facu que me esta costando horrores resolver, tengo que usar recursión si o si. La idea es calcular el minimo comun multiplo a partir de dos numeros. No hace falta pasar el algoritmo a algun lenguaje en particular, en pseudocódigo está bien.

    Les paso como lo hice yo pero no me convence:

    Código:
    Funcion MCM(n,m,n2,m2:enteros): entero
       Si n=m entonces
           MCM:=n
         sino
           si n<m entonces
              MCM:=MCM(n+n2,m,n2.m2)
             sino
              MCM:=MCM(n,m+m2,n2.m2)
          fin si
        fin si
    fin funcion
    A mi lo que no me convence es que tenga que pasar siempre como parámetros los valores de n2 y m2 que se encargarian de resguardar los valores iniciales de los dos numeros para de esa manera ir sumándolos. Además no estoy seguro si los lenguajes permiten pasar parámetros que no se usen en alguna operación o comparacion dentro del algoritmo.
    Lo que quiero es una funcion que haga lo mismo pero pasándole únicamente los dos números como parámetros (n y m).
    Que quede Funcion(n,m:enteros):entero

    Si me pueden ayudar se los agradeceré mucho porque la verdad es que no me da mas la cabeza

    Muchas gracias
    Última edición por Giskard; 27-03-2007 a las 03:02
    Citar  
     

  2. #2  
    Moderador HH
    Fecha de ingreso
    Feb 2002
    Ubicación
    México
    Mensajes
    1.155
    Descargas
    4
    Uploads
    0
    A m&#237; tampoco me convence...
    Precisamente la recursividad me da muchos dolores de cabeza. Es interesante esa funci&#243;n que intentas hacer y ver&#233; si puedo ayudarte en algo, s&#243;lo debo digerir un poco m&#225;s el problema y agarrar mis viejos libros de matem&#225;ticas...
    Saludos
    Mientras el mundo permanezca no acabarán la fama y la gloria de México-Tenochtitlan
    Citar  
     

  3. #3  
    Moderador HH
    Fecha de ingreso
    Feb 2002
    Ubicación
    México
    Mensajes
    1.155
    Descargas
    4
    Uploads
    0
    Como no me gusta mucho el pseudocódigo, siempre prefiero el código de a deveras voy a postear la solución final en C (aunque muy posiblemente no sea la mejor). Una de las características en las funciones recursivas, es que muchas veces es necesario pasar un parámetro que sirva como variable auxiliar.

    Para el cálculo del mínimo común múltiplo de dos o más números se descompondrán los números en factores primos y se tomarán los factores comunes y no comunes con su mayor exponente.

    Por ejemplo, de las factorizaciones de 6936 y 1200,

    6936 = 2'3 · 3 · 17'2 (léase dos al cubo por tres por diecisiete al cuadrado)
    1200 = 2'4 · 3 · 5'2

    podemos inferir que su m.c.m. es 24 · 3 · 52 · 172 = 346 800.

    Se necesita una variable auxiliar que nos diga en qué numero vamos, esta claro que puede hacerse muy bien sin usar ninguna función recursiva, pero como en tu caso es a fuerza entonces dejo ambos códigos:

    Con recursión:
    Código:
    #include <stdio.h>
    
    int mcm(int div, int n1, int n2);
    
    int main(){
    	int n1, n2;
    	int result;
    	printf("Valores: \n");
    	scanf("%d",&n1);
    	scanf("%d",&n2);
    	result=mcm(2,n1,n2);
    	printf("El minimo común múltiplo es: %i \n",result);
            return 0;
    }
    
    int mcm(int div, int n1, int n2){
    	int aux=1;
    	while(n1%div==0 || n2%div==0){
    		aux*=div;
    		if(n1%div==0)
    			n1/=div;
    		if(n2%div==0)
    			n2/=div;
    	}
    	if(div<=n1||div<=n2)
    		aux*=mcm(div+1,n1,n2);
    	return aux;
    }
    Sin recursión:
    Código:
    #include <stdio.h>
    
    int main(){
    	int n1, n2;
    	int mcm=1;
    	int a=2;
    	printf("Valores:");
    	scanf("%d",&n1);
    	scanf("%d",&n2);
    	do{
    		if(n1%a==0 || n2%a==0){
    			mcm *=a;
    			if(n1%a==0)
    				n1/=a;
    			if(n2%a==0)
    				n2/=a;
    		}
    		else
    			a++;
    	}while(a<=n1||a<=n2);
    	printf("El minimo comun multiplo es: %i\n",mcm);
    	return 0;
    }
    Saludos.
    Mientras el mundo permanezca no acabarán la fama y la gloria de México-Tenochtitlan
    Citar  
     

  4. #4  
    Medio
    Fecha de ingreso
    Jan 2006
    Mensajes
    98
    Descargas
    0
    Uploads
    0
    mr hiccup, creo que tu soluci&#243;n es perfectamente valida aunque pases dos parametros asi, de hecho es lo que se suele usar (mirate la recursividad final y no final); lo unico que te falta saber es que ese algoritmo en la practica no es el de calcular el mcm sino es como tu algoritmo secundario, interno. El problema usando tu soluci&#243;n quedar&#237;a como:

    //Este es el algoritmo de calculo de mcm que a su vez llama a otro
    //y esto se denomina "la primera llamada"
    entero mcm(entero n, entero m)
    mcmR(n,m,n,m)

    Funcion mcmR(n,m,n2,m2:enteros): entero
    Si n=m entonces
    devolver n
    sino
    si n<m entonces
    devolver MCM(n+n2,m,n2.m2)
    sino
    devolver MCM(n,m+m2,n2.m2)
    fin si
    fin si
    fin funcion

    Saludos
    Prvo nauci milslit, poslije programiraj.
    Citar  
     

  5. #5  
    Iniciado
    Fecha de ingreso
    Apr 2006
    Mensajes
    15
    Descargas
    0
    Uploads
    0
    ahi esta, bueno, muchisimas gracias por los datos, me fueron de gran ayuda. Igualmente sigo haciendo la guia de ejercicios de recursividad, asi que si sale algo raro otra vez lo posteo aca devielta.

    Muchas gracias
    salu2
    Citar  
     

Marcadores

Marcadores

Permisos de publicación

  • No puedes crear nuevos temas
  • No puedes responder temas
  • No puedes subir archivos adjuntos
  • No puedes editar tus mensajes
  •