• Miércoles 6 de Noviembre de 2024, 06:15

Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.


Mensajes - Xinefpro

Páginas: [1]
1
Diseño de Algoritmos / Re: Algoritmo Maximo comun divisor
« en: Viernes 5 de Noviembre de 2010, 02:57 »
Holas, te dejo 2 formas de resolver el problema:

* PRIMER METODO:

Existe una propiedad interesante del MCD, el cual sirve para el problema que mencionas:

Sean los enteros positivos: x[1], x[2], x[3], ..., x[n] ; entonces:

MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( x[1], x[2], ..., x[n-1] ), x[n] )

Esto se puede aplicar recursivamente, hasta llegar a:

MCD( x[1], x[2], x[3], ..., x[n] ) = MCD( MCD( ... MCD( MCD( MCD( x[1], x[2] ), x[3] ), x[4]), ... ), x[n] )

En resumen para hallar el MCD de los N numeros, puedes intentar:

Primero calculas el MCD de x[1] y x[2], luego calculas el MCD del resultado anterior con x[3],
luego calculas el MCD del resultado anterior con x[4], asi sucesivamente hasta el ultimo numero x[n].

En pseudocogido seria asi:

Código: Java
  1.  
  2. Entero MCD = 1;
  3.  
  4. // MaximoComunDivisor( a, b ) es el algoritmo de euclides usado para
  5. // hallar el Maximo Comun Divisor de dos enteros positivos.
  6. Para i de 2 hasta n hacer
  7.    MCD = MaximoComunDivisor( MCD, x[i] )
  8.  
  9. Retornar MCD
  10.  
  11.  

* SEGUNDO METODO:

Otra propiedad del MCD dice que el máximo común divisor de dos números resulta ser el producto
de sus factores primos comunes elevados al menor exponente.
Es decir sean los numeros: 24, 30, 36

- 24 = ( 2^3 ) * (  3^1 )               = ( 2^3 ) * (  3^1 ) * ( 5^0 )
- 30 = ( 2^1 ) * ( 3^1 ) * ( 5^1 )   = ( 2^1 ) * ( 3^1 ) * ( 5^1 )
- 36 = ( 2^2 ) * ( 3^2 )                = ( 2^2 ) * ( 3^2 ) * ( 5^0 )

Por lo tanto el MCD( 24, 30, 36 ) = ( 2^1 ) * ( 3^1 ) * ( 5^0 ) = 6

Esto de puede modelar en un algoritmos, si es que guardamos cada numero en un vector de tamaño N,
y luego ir dividiendo todos los numeros del vector, entre 2, 3, 4, ..., Z, donde z es el menor numero almacenado en el vector:

Código: Java
  1.  
  2. // Vector donde estan almacenados los numeros de los que se hallara su MCD
  3. Entero[] vector           
  4. // Obtenemos el menor elemento del vector, el cual sera el maximo valor  por el que dividiremos cada elemento del vector.
  5. Entero menor = MenorElemento( vector )
  6. // Menor de todos los exponentes del factor primo actual
  7. Entero menorExponente = 0                  
  8. // Valor que almacena el MCD divisor de los numeros
  9. Entero MCD = 1                   
  10. // Indica si el factor primo actual es un divisor comun de todos los numeros
  11. Booleano esDivisorComun
  12.  
  13. // "i", indica el factor que verificaremos si es factor comun ( divisor ) a todos los numeros
  14. Para i desde 2 hasta i*i <= menor hacer
  15.      
  16.       esDivisorComun = verdad
  17.       j = 1
  18.       menorExponente = 0
  19.  
  20.       Mientras( esDivisorComun  )
  21.             Si( j = n + 1 )   // Si el divisor "i", es comun a todos entonces el menorExponente aumenta 1
  22.                 menorExponente = menorExponente + 1
  23.                 j = 1
  24.                
  25.                 // Como el i es divisor comun, pasamos a dividir todos los numeros entre i,
  26.                 // esto tambien afecta a "menor"
  27.                 Para  h de 1 hasta n hacer
  28.                      vector[ h ] = vector[ h ] / i
  29.                 FinPara
  30.  
  31.                 menor = menor / i
  32.             FinSi          
  33.                
  34.             Si( vector[ i ] mod i  != 0 )   // Si el divisor actual no es comun a todos, pasamos al siguiente divisor
  35.                 esDivisorComun = falso
  36.  
  37.        Fin_Mientras
  38.  
  39.        // Actualizamos el MCD
  40.        MCD = MCD * Potencia( i, menorExponente )
  41.  
  42. Fin_Para
  43.  
  44.  

Si comparamos los 2 algoritmos te puedes dar cuenta de que el primero es mas facil dec codificar ademas
que es de orden O( n log(n) ) , en cambio el segundo es mas "engorroso" para codificar y encima es de orden  O( n Raiz( n ) )
( lo cual es mas lento que el primer algoritmo ) .
Donde n es el valor del mayor elemento de los que se desea hallar su MCD.

Espero que te sirvan de algo.

PD: Realmente esos ordenes de los algortimos no son los correctos, ya que estos han sido calculados
en funcion del valor de n y no del tamaño de n.

2
Diseño de Algoritmos / Re: programa de calculadora
« en: Miércoles 7 de Abril de 2010, 20:58 »
Como bien dijo Akabane89 para ver la paridad de signos de asociacion tienes que usar una pila, y para lo de la evaluacion de las expresiones aritmeticas te recomiendo buscar en google
o wikipedia "Notacion postfija", que es lo que se usa para evaluar expresiones aritmeticas en las calculadoras. Suerte .

3
Diseño de Algoritmos / Re: Solución de este Algoritmo
« en: Miércoles 7 de Abril de 2010, 20:50 »
Hey tranqui muchos hemos tenido problemas en nuestros inicios, y me incluyo en ese grupo, pero recuerda que La practica hace al maestro :

Si es que te entendi bien lo  que deseas que se muestre es lo siguiente :
Código: Java
  1.  
  2.      Si   No   Si   No   Si   No   Si   No   Si   No
  3.       1    2    3    4    5    6    7    8    9   10
  4.  
  5.  

No es dificl darse cuenta de que las palabras "Si" aparecen en posiciones impares y las palabras "No" en posiciones pares, por ende una posible
solucion seria esta :
Código: Java
  1.  
  2.  
  3. // El operador % nos da el residuo de una division. Ejm : 7 % 3 = 1,  12 % 4 = 0
  4. Para i de 1 hasta 10 hacer
  5.      Si( i % 2 = 0 )      // Posicion par
  6.           Escribir( "No" )
  7.      
  8.      Sino                  // Posicion impar
  9.           Escribir( "Si" )
  10.  
  11.  

4
Diseño de Algoritmos / Re: area de triangulo
« en: Miércoles 7 de Abril de 2010, 20:38 »
Holas amigo, creo que no es necesario tratar el problema de los signos :

Mira por geometria basica, sea un Triangulo de lados : a, b, c ; se cumple lo siguiente :
Código: Java
  1.  
  2.  
  3. *   a - b < c < a + b   ... ( 1 )
  4. *   b - c < a < b + c   ... ( 2 )
  5. *   a - c < b < a + c   ... ( 3 )
  6.  
  7.  
  8.  

Luego como tu para hallar el area quieres usar la Fórmula de Herón :

Código: Java
  1.  
  2. p = (  a + b + c   ) / 2
  3. area ← raiz(p * (p-a) * (p-b) * (p-c))
  4.  
  5.  
 
Para que un producto resulte negativo uno de sus factores debe de ser negativo, entonces analizamos cada factor del producto de la formula de Heron :
Código: Java
  1.  
  2. * p = ( a + b + c )/2 > 0       //  ya que un lado triangulo solo puede tener lados positivos por ende a + b + c > 0
  3.  
  4. * ( p - a ) = ( a + b + c )/2 - a = ( b + c - a )/2  > 0          // ya que de ( 2 ) tenemos que b + c > a
  5. * ( p - b ) = ( a + b + c )/2 - b = ( a + c - b )/2  > 0          // ya que de ( 3 ) tenemos que a + c > b
  6. * ( p - c ) = ( a + b + c )/2 - c = ( a + b - c )/2  > 0          // ya que de ( 1 ) tenemos que a + b > c
  7.  
  8.  

Por lo tanto mientras los lados del triangulo sean validos ( positivos ), lo que esta dentro de la raiz nunca va a salir negativo, por ende no
tienes que preocuparte de los signos.

Páginas: [1]