MULTIPLICACIÓN EGIPCIA EN JAVA, ACM 2008, HCH
Primeramente un saludo a todos, y en especial para los programadores y todos aquellos que quieran aprender. Esta es mi primera publicación y como me gusta programar en java pues decidí publicar un programa que hice cuando participe en el concurso de ACM ok, bueno este problema es del concurso de ACM del año 2008:
Nombre del problema: multiplicación Egipcia
Descripción:
Ancient Egyptian multiplication is a systematic method for multiplying two numbers that does not require the multiplication table, only the ability to multiply by 2, and to add. Also known as Egyptian multiplication and Peasant multiplication, it decomposes one of the multiplicands into a sum of powers of two and creates a table of doublings of the second multiplicand. This method may be called mediation and duplication, where mediation means halving one number and duplication means doubling the other number.
This method has three phases: the decomposition, the table and the result.
The decomposition of a number N thus consists of finding the powers of two which make it up. The Egyptians knew empirically that a given power of two would only appear once in a number. For the decomposition, they proceeded methodically; they would initially find the largest power of two less than or equal to the number in question, subtract it out and repeat until nothing remained. (The Egyptians did not make use of the number zero in mathematics).
Example: First consider the decomposition of the number N = 13 :
· the largest power of two less than or equal to 13 is 8, 13 - 8 = 5,
· the largest power of two less than or equal to 5 is 4, 5 - 4 = 1,
· the largest power of two less than or equal to 1 is 1, 1 - 1 = 0
N = 13 is thus the sum of the powers of two: 8, 4 and 1.
After the decomposition of the first multiplicand (N ), it is necessary to construct a table of powers of two times the second multiplicand (M ) from one up to the largest power of two found during the decomposition. In the table, a line is obtained by multiplying the preceding line by two.
For example, if the largest power of two found during the decomposition of N = 13 is 8 and M =238 , the table is created as follows:
Finally, the result is obtained by adding the numbers from the second column for which the corresponding power of two makes up part of the decomposition of N (denoted by a mark).
Thus, the result of the multiplication of 13 × 238 is obtained as the addition of: 1904 + 952 + 238 = 3094 or 238 + 952 + 1904 = 3094.
Input
The input consists of multiple test cases. Each test case consists of a single line containing two integers N and M ( 0 N, M 1, 000, 000, 000 ) that indicate the multiplicands and the begin addition specification, that it indicates from that row will initiate the addition by obtained the result. The begin addition specification is one of `u' or `b' referring to up row and bottom row respectively.
The last test case is followed by `-1' on a line by itself.
Output
For each test case, print the case number (beginning with 1) followed by the multiplicands (N and M ) separated by ` x ', an equal sign, and an expression giving the sum of the multiples of M (numbers from the second column of the table) for which the corresponding power of two makes up part of the decomposition of the multiplicand N of the form indicated by the begin addition specification. Use the format shown in the sample output below. In the event that the values of N or M are 0, then the answer must be only `0'.
Sample Input
13 238 u
13 238 b
1000 1 u
1 1000 b
1 1 u
0 10 u
-1
Sample Output
Case 1: 13 x 238 = 238 + 952 + 1904
Case 2: 13 x 238 = 1904 + 952 + 238
Case 3: 1000 x 1 = 8 + 32 + 64 + 128 + 256 + 512
Case 4: 1 x 1000 = 1000
Case 5: 1 x 1 = 1
Case 6: 0 x 10 = 0
Bueno en resumen lo que pide el problema es recrear la multiplicación egipcia; dicha multiplicación se obtiene de la sumatoria de varios números, por ejemplo:
La solución del caso 1 es:
13 x 238 = 238 + 952 + 1904
La multiplicación de 13x238 es igual a 3094. y la sumatoria de 238+952+1904=3094.
En el segundo miembro tenemos la equivalencia de multiplicar 13x238 en una sumatoria de varios números. Lo que tiene que hacer el programa es encontrar los números que tienen que sumarse para obtener el resultado de la multiplicación de 13x238.
Los datos de entrada tienen que tener el siguiente formato:
13 238 u
O
13 238 b
Los dos primeros datos o sea 13 238 son los números a multiplicar y el tercer dato nos indica el orden en el que se mostraran los resultados.
Por ejemplo:
13 238 u = 13 x 238 = 238 + 952 + 1904
Y
13 238 b = 13 x 238 = 1904 + 952 + 238
Si se fijan el orden en el Segundo miembro del resultado varia dependiendo del tercer dato; si el tercer dato es u entonces el resultado se mostrara en el orden de menor a mayor y si el dato es b el orden será de mayor a menor. Y bueno a continuación les dejo el código fuente para que lo ejecuten y chequen el resultado.
package _2008;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
*
* @author Hilario
* Nombre del Programa: Multiplicacion Egipcia; ACM 2008;
* Autor: Hilario de la Cruz Hernandez
* Institucion: Instituto Tecnologico Superior de Tantoyuca
* Ciudad: Tantoyuca, Veracruz, Mexico
* Email: hil_ch@hotmail.com
*
*Nota: este archivo puede ser modificado o redistribuido, siempre y cuando
*se informe de dichas acciones
*
* Este es un programa que resulve la multiplicacion egipcia
* el cual se optiene de la sumatoria de varios numeros.
* por ejemplo:
* 13 x 238 = 238 + 952 + 1904
* 13x 238=3094
* 238 + 952 + 1904=3094
*
* el formato de entrada es el siguiente:
* 13 238 u
* los dos primeros numeros son los numeros a multiplicar y el ultimo define
* el orden del resultado:
* u=menor a mayor
* b=mayor a menor
* ejemplo:
* 13 238 u = 13 x 238 = 238 + 952 + 1904
* 13 238 b = 13 x 238 = 1904 + 952 + 238
*/
public class _4284_Egyptian_Multiplication {
public _4284_Egyptian_Multiplication(){//constructor
}
public void leerLineas(){//este metodo lee las lineas del txt
String linea="";//la variable linea guarda cada linea del txt
int caso=1;//indica el numero de caso
try {
BufferedReader br = new BufferedReader(new FileReader("MultE.txt"));//se obtiene el arcrivo txt "MultE.txt"
while(br.ready()){//mientras existan lineas en el txt se seguira ejecutando
linea=br.readLine();//se lee una lunea del txt
//el "-1" indica el final de los casos asi que si se llega
//a esta cadena entonces se termina la ejecusion del programa
if(!linea.equals("-1")){//si la linea es diferente a "-1" entonces
extraerValores(linea,caso);//se extraen los valores de la linea
caso++;//incerementa caso
}
else{//si no entonces
System.exit(0);//se termina la ejecusion del programa
}
}
} catch (FileNotFoundException ex) {}
catch(IOException ex){}
}
public void extraerValores(String linea,int caso){//este metodo extre los valores de cada linea del txt
int cont=0;//identifica el tipo de dato
int N=0,M=0;//N=primer operando, M=segundo operando
char sentido=' ';//indica el sentido o el orden de la impresion de los resultados
StringTokenizer st=new StringTokenizer(linea," ");//se establece un token para espacios en blanco
while(st.hasMoreTokens()){//mientras existan mas tokens
switch(cont){//se determina el tipo de dato a capturar
case 0:N=Integer.parseInt(st.nextToken());//el caso 0 es para N el primer operando
case 1:M=Integer.parseInt(st.nextToken());//el caso 1 es para M el segundo operando
case 2:sentido=st.nextToken().charAt(0);//el caso 2 es para U el dato que indica el orden de impresion
}
}
System.out.println("--------------------\n"+N+" "+M+" "+sentido);//se imprime el caso
System.out.println("Case "+caso+":"+multiplicar(N,M,sentido));//se imprime el resultado
}
public String multiplicar(int N,int M,char sentido){//este metodo se encarga de realizar la multiplicacion egipcia
String resultado="";//resultado que se devolvera
// Vector vecPotencias=new Vector();
Vector vecMultiplicacion=new Vector();//en este vector se guardaran temporalmente los resultados
int indice=0;//indice del vector
resultado+=N+"x"+M+"=";//se adiere NxM a resultado
int potenciaMax=0;//se inicializa la potencia a 0
if(N==0||M==0){//si n=0 o M=0 entonces
resultado+="0";//se adiere 0 a resultado
}
else{//sino
while(N>=1){//mientras que N sea >= a 1 entonces
potenciaMax=obtenerPotenciaMax(N);//se obtiene la potencia maxima menor a N
// System.out.println(potenciaMax);
// vecPotencias.add(indice,Integer.toString(potenciaMax));
//se adiere al vector la expresion potenciaMax*M
vecMultiplicacion.add(indice,Integer.toString(potenciaMax*M));
N-=potenciaMax;//se decrementa potencia en N
indice++;//se incrementa indice
}
//a continuecion se definen el sentido de los resultados
if(sentido=='u'){//si sentido es igual a 'u' entonces
//se ordenan los resultados de menor a mayor
for(int i=vecMultiplicacion.size()-1;i>=0;i--){
if(i==0){
resultado+=vecMultiplicacion.elementAt(i);
}
else{
resultado+=vecMultiplicacion.elementAt(i)+"+";
}
}
}
else if(sentido=='b'){//si no, si sentido e igual a 'b'
//se ordena el resultado de mayor a menos
for(int i=0;i<vecMultiplicacion.size();i++){
if(i==vecMultiplicacion.size()-1){
resultado+=vecMultiplicacion.elementAt(i);
}
else{
resultado+=vecMultiplicacion.elementAt(i)+"+";
}
}
}
}
return resultado;
}
//este metodo obtiene la potencia maxima anterior a N
public int obtenerPotenciaMax(int N){
int potencia=0;//potencia de retorno
int it=0;//iteracion
boolean menor=true;//centinela
while(menor==true){//mientras menor=true
potencia=(int)Math.pow(2, it);//se genera una potencia de 2 a la it
if((int)Math.pow(2, it+1)>N){//si la siguiente potencia es mayor a N entonces
menor=false;//menor=false para terminar el while
}
// System.out.println(potencia);
it++;//se incrementa it
}
return potencia;//se regresa la potencia
}
public static void main(String[]args){
_4284_Egyptian_Multiplication em=new _4284_Egyptian_Multiplication();
em.leerLineas();
}
}
Bueno para poder ejecutar este programa necesitaran crear un txt en el directorio raíz de su proyecto y le darán el nombre de “MultE.txt” y copian el siguiente ejemplo en el txt:
13 238 u
13 238 b
1000 1 u
1 1000 b
1 1 u
0 10 u
54 300 u
54 300 b
-1
Cuando ejecuten el programa les tiene que arrojar los siguientes resultados:
Bueno espero que este programa les sirva de algo ok, la verdad tengo varios de estos programas de ACM resueltos pero los iré publicando poco a poco ok saludossss.
No hay comentarios:
Publicar un comentario