miércoles, 30 de abril de 2014

Clases LinkedBag y ArrayBag en Java. Estructuras de Datos.

Buenas gente, os traigo un ejercicio de los primeros en Java de la asignatura Estructuras de Datos de la UMA. Ésta consiste (cito textualmente):
  • La interfaz Bag y la clase  LinkedBag deben situarse dentro del paquete dataStructures.bag. Para ello, crear en el proyecto este paquete con nombre "dataStructures.bag" y colocar los ficheros dentro.
    La clase BagTester debe colocarse en el paquete por defecto y usará el paquete anterior.
    Los ficheros con extensión out son pruebas de ejecución tanto en Unix como en Dos de dos ejemplos que se encuentran en la clase BagTester. Podéis comprobar si vuestra salida por consola coincide con los ficheros que os proporcionamos.
Sí, como veis nuestro profesor tampoco se esforzaba mucho en hacernos saber lo que pedía. Solía explicarlo en clase y "a buscarse la vida". Por eso mismo atrasé esta entrada para subir primero la de Haskell en la cual sí venía explicado. Aquí teneis el test, el archivo de prueba Cervantes y el Dickens.
Os doy la interfaz Bag:

package dataStructures.bag;

/**
 * Interface for the Bag ADT.
 * 
 * @param <T>
 *            Type of elements in bag. Note that {@code T} must be
 *            {@code Comparable}
 */
public interface Bag<T extends Comparable<? super T>> {
 /**
  * Test the bag for emptiness.
  * 
  * @return {@code true} if bag is empty, else {@code false}.
  */
 boolean isEmpty();

 /**
  * Inserts a new occurrence in the bag.
  * 
  * @param item
  *            the element to insert.
  */
 void insert(T item);

 /**
  * Returns the number of occurrences of {@code item} in the bag
  * 
  * @param item
  *            the item to be counted
  * @return number of occurrences of {@code item}
  */
 int occurrences(T item);

 /**
  * Removes an occurrence of {@code item} from the bag
  * 
  * @param item
  *            the item to remove
  */
 void delete(T item);
}

Ahora las respuestas:

Class ArrayBag:

package dataStructures.bag;

import java.util.Arrays;

public class ArrayBag<T extends Comparable<? super T>> implements Bag<T> {

 private final static int INITIAL_CAPACITY = 5;

 protected T[] value; // keep this array sorted
 protected int[] count; // keep only positive counters
 protected int nextFree;

 public ArrayBag() {
  this(INITIAL_CAPACITY);
 }

 @SuppressWarnings("unchecked")
 public ArrayBag(int n) {
  value = (T[]) new Comparable[n]; // everything to null
  count = new int[n]; // everything to 0
  nextFree = 0;
 }

 private void ensureCapacity() {
  if (nextFree == value.length) {
   value = Arrays.copyOf(value, 2 * value.length);

   // TO BE FILLED OUT
   count = Arrays.copyOf(count, 2*count.length);

  }
 }

 public boolean isEmpty() {
  return nextFree == 0;
 }

 // if "item" is stored in the array "value", returns its index
 // otherwise returns the index where "item" would be inserted
 
 // si item está almacenado en el array devuelve su índice
 // si no devuelve el índice en el que item debería insertarse

 private int locate(T item) {
  int lower = 0;
  int upper = nextFree - 1;
  int mid = 0;
  boolean found = false;

  // binary search
  while (lower <= upper && !found) {
   mid = lower + ((upper - lower) / 2); // == (lower + upper) / 2;
   found = value[mid].equals(item);
   if (!found) {
    if (value[mid].compareTo(item) > 0) {
     upper = mid - 1;
    } else {
     lower = mid + 1;
    }
   }
  }

  if (found)
   return mid; // the index where "item" is stored
  else
   return lower; // the index where "item" would be inserted
 }

 public void insert(T item) {
  ensureCapacity();
  int i = locate(item);//donde está o deberia estar
  if (value[i] != null && value[i].equals(item)) {//está ahí
   count[i]++;
   // TO BE FILLED OUT
   
  } else {
   // shift elements to right
   for (int j = nextFree; j > i; j--) {
    value[j] = value[j - 1];
    count[j] = count[j - 1];
   }
   value[i] = item;
   count[i] = 1;
   
   
   nextFree++;

  }
 }

 public int occurrences(T item) {
  int result = 0;
  int i = locate(item);
  if (value[i] != null && value[i].equals(item)) {

   result = count[i];

  }
  return result;
 }

 public void delete(T item) {
  int i = locate(item);
  if (value[i] != null && value[i].equals(item)) {
   if (count[i] > 1) {
    count[i]--;
   } else {
    // shift elements to left
    for (int j = i; j < nextFree-1; j++) {
     value[j] = value[j+1];
     count[j] = count[j+1];

    }
    nextFree--;
   }
  }
 }

 public String toString() {
  String text = "Bag(";
  for (int i = 0; i < nextFree; i++) {
   text += "(" + value[i] + ", " + count[i] + ") ";
  }
  return text + ")";
 }
}

Class LinkedBag:

package dataStructures.bag;

public class LinkedBag<T extends Comparable<? super T>> implements Bag<T> {

 static private class Node<E> {
  E elem;
  int count;
  Node<E> next;

  Node(E x, int n, Node<E> node) {
   elem = x;
   count = n;
   next = node;
  }
 }

 private Node<T> first; // keep the linked list sorted by "elem"

 public LinkedBag() {
  first = null;
 }

 public boolean isEmpty() {
  return first == null;
 }

 public void insert(T item) {
  Node<T> previous = null;
  Node<T> current = first;

  while (current != null && current.elem.compareTo(item) < 0) {
   previous = current;
   current = current.next;
  }

  if (current != null && current.elem.equals(item)) { //hemos encontrado el elemento
   //aumentamos count
   current.count++;
   // TO BE FILLED OUT

  } else if (previous == null) { //no hay elementos
   first = new Node<T>(item, 1, first);
  } else {// no existe, hay que insertarlo

   // TO BE FILLED OUT
   Node<T> aux = new Node<T>(item, 1, current);
   previous.next = aux;

  }
 }

 public int occurrences(T item) {
  Node<T> current = first;
  int result = 0;

  while (current != null && current.elem.compareTo(item) < 0) {
   current = current.next;
  }

  if (current != null && current.elem.equals(item)) { // lo hemos encontrado

   // TO BE FILLED OUT
   result = current.count;

  }
  return result;
 }

 public void delete(T item) {
  Node<T> previous = null;
  Node<T> current = first;

  while (current != null && current.elem.compareTo(item) < 0) {
   previous = current;
   current = current.next;
  }

  if (current != null && current.elem.equals(item)) {//lo hemos encontrado
   if (current.count > 1) {// tiene mas de uno
    current.count--;
   } else if (previous == null) {//es el primero 
    first = first.next;

   } else {
    previous.next = current.next;
   }
  }
 }

 public String toString() {
  String text = "Bag(";
  for (Node<T> p = first; p != null; p = p.next) {
   text += "(" + p.elem + ", " + p.count + ") ";
  }
  return text + ")";
 }
}

Bueno amigos, eso es todo. Espero que os sirva ;) Si tenéis alguna petición o duda, comentadla ;)

Muchas gracias.

lunes, 28 de abril de 2014

Práctica soluciones de Sudokus.

Bueno. Ésta práctica consiste en utilizar el algoritmo de vuelta atrás (backtracking) para obtener todas las posibles soluciones de un sudoku. Supongo que no tengo que explicar en qué consiste un sudoku ni como resolverlo, pero de todos modos preguntad si tenéis alguna duda ;)

Podremos crear un Tablero de Sudoku a partir de otro o de una string de 81 caracteres del tipo

.4....36263.941...5.7.3.....9.3751..3.48.....17..62...716.9..2...96.......312..9.
Donde los caracteres son las filas concatenadas y un punto significa que ésa casilla está vacía.

Aquí os dejo UNA solución, pero debo deciros que hay muchas más ;)

import java.util.*;


public class TableroSudoku implements Cloneable {
 
 // constantes relativas al nº de filas y columnas del tablero
 protected static final int MAXVALOR=9; 
 protected static final int FILAS=9; 
 protected static final int COLUMNAS=9; 
 ////////////////////////////////////////////////////////////////////////////////
 protected static final int raízFilas = (int) Math.sqrt(FILAS);
 protected static final int raízColumnas = (int) Math.sqrt(COLUMNAS);
 ///////////////////////////////////////////////////////////////////////////////
 protected static Random r = new Random();
 
 protected int celdas[][]; // una celda vale cero si est\u00E1 libre.
 
 public TableroSudoku() {
  celdas = new int[FILAS][COLUMNAS]; //todas a cero.
 }

 // crea una copia de su par\u00E1metro
 public TableroSudoku(TableroSudoku uno) {
  TableroSudoku otro = (TableroSudoku) uno.clone();
  this.celdas = otro.celdas;
 }

 // crear un tablero a parir de una configuraci\u00D3n inicial (las celdas vac\u00EDas
 // se representan con el caracter ".".
    public TableroSudoku(String s) {
     this();
     if(s.length() != FILAS*COLUMNAS) { //tiene que tener tantos caracteres como casillas MIO
      throw new RuntimeException("Construcci\u00D3n de sudoku no v\u00E1lida.");
     } else {
      for(int f=0;f<FILAS;f++) 
    for(int c=0;c<COLUMNAS;c++) {
     Character ch = s.charAt(f*FILAS+c);
     celdas[f][c] = (Character.isDigit(ch) ? Integer.parseInt(ch.toString()) : 0 ); 
    }  
  }  
    }

 
 /* Realizar una copia en profundidad del objeto
  * @see java.lang.Object#clone()
  */
 public Object clone()  {
  TableroSudoku clon;
  try {
   clon = (TableroSudoku) super.clone();
   clon.celdas = new int[FILAS][COLUMNAS]; 
   for(int i=0; i<celdas.length; i++)
    System.arraycopy(celdas[i], 0, clon.celdas[i], 0, celdas[i].length);
  } catch (CloneNotSupportedException e) {
   clon = null;
  } 
  return clon;
 }
 
 /* Igualdad para la clase
  * @see java.lang.Object#equals()
  */
 public boolean equals(Object obj) {
  if (obj instanceof TableroSudoku) {
   TableroSudoku otro = (TableroSudoku) obj;
   for(int f=0; f<FILAS; f++)
    if(!Arrays.equals(this.celdas[f],otro.celdas[f]))
     return false;
   return true;  
  } else
   return false;
 }
 


 public String toString() {
  String s = "";

  for(int f=0;f<FILAS;f++) {
   for(int c=0;c<COLUMNAS;c++) 
    s += (celdas[f][c]==0 ? "." : String.format("%d",celdas[f][c])); 
  }
  return s; 
 }


 // devuelva true si la celda del tablero dada por fila y columna est\u00E1 vac\u00EDa.
 protected boolean estaLibre(int fila, int columna) {
  return celdas[fila][columna] == 0;
 }
 
 // devuelve el número de casillas libres en un sudoku.
 protected int numeroDeLibres() {
  int n=0;
     for (int f = 0; f < FILAS; f++) 
         for (int c = 0; c < COLUMNAS; c++)
          if(estaLibre(f,c))
           n++;
     return n;
 }
 
 protected int numeroDeFijos() {
  return FILAS*COLUMNAS - numeroDeLibres();
 }

 // Devuelve true si @valor ya esta en la fila @fila.
 protected boolean estaEnFila(int fila, int valor) {
  // A completar por el alumno
  
  for(int i=0; i < COLUMNAS; i++){
   if(celdas[fila][i] == valor) return true;
  }
  
  
  return false;
 }    

 // Devuelve true si @valor ya esta en la columna @columna.
 protected boolean estaEnColumna(int columna, int valor) {
  // A completar por el alumno
  
  for(int i=0; i < FILAS; i++){
   if(celdas[i][columna] == valor) return true;
  }
  return false;
 }    
 

 // Devuelve true si @valor ya esta en subtablero al que pertence @fila y @columna.
 protected boolean estaEnSubtablero(int fila, int columna, int valor) {
  // A completar por el alumno
  //int raízFilas = (int) Math.sqrt(FILAS);
  //int raízColumnas = (int) Math.sqrt(COLUMNAS);
  
  int x = fila/raízFilas;
  int y = columna/raízColumnas;
  int finicio = x * raízFilas;
  int cinicio = y * raízColumnas;
  
  for(int i= finicio; i< finicio + raízFilas; i++){
   for(int j= cinicio; j < cinicio + raízFilas; j++ ){
    if(celdas[i][j] == valor) return true;
   }
  }
  return false; 
 }    

 
 // Devuelve true si se puede colocar el @valor en la @fila y @columna dadas.
 protected boolean sePuedePonerEn(int fila, int columna, int valor) {
  // A completar por el alumno
  boolean resultado = false;
  if(!estaEnColumna(columna,valor) && !estaEnFila(fila, valor) && !estaEnSubtablero(fila, columna, valor))
   resultado = true;
  return resultado;
 }
 
 
 

 protected void resolverTodos(List<TableroSudoku> soluciones, int fila, int columna) {
  // A completar por el alumno
  
  if (estaLibre(fila, columna)) {
   for (int i = 1; i <= MAXVALOR; i++) {
    if (sePuedePonerEn(fila, columna, i)) {
     celdas[fila][columna] = i; //como se puede poner, lo escribo en esa posición
     
     if(fila == FILAS -1 && columna == COLUMNAS -1){
      // es la última casilla y ya los hemos colocado todos, por tanto es solucion
      this.toString();
      soluciones.add(new TableroSudoku(this)); //construtor que copia el tablero
     } else if(fila < FILAS - 1 &&  columna == COLUMNAS -1){ //quedan filas pero no columnas
      resolverTodos(soluciones, fila + 1, 0);
     } else { //quedan aun columnas
      resolverTodos(soluciones, fila, columna + 1);
     }
     
     celdas[fila][columna] = 0; //ponemos a 0 el escrito para volver a construir con el siguiente valor
    }
    
   }
  } else { //no está libre
   if(fila == FILAS -1 && columna == COLUMNAS -1){
    // es la última casilla y ya los hemos colocado todos, por tanto es solucion
    this.toString();
    soluciones.add(new TableroSudoku(this)); //construtor que copia el tablero
   } else if(fila < FILAS - 1 &&  columna == COLUMNAS -1){ //quedan filas pero no columnas
    resolverTodos(soluciones, fila + 1, 0);
   } else { //quedan aun columnas
    resolverTodos(soluciones, fila, columna + 1);
   }
  }
 }
 

 public List<TableroSudoku> resolverTodos() {
        List<TableroSudoku> sols  = new LinkedList<TableroSudoku>();
        resolverTodos(sols, 0, 0);
  return sols;
 }
 
 
 public static void main(String arg[]) {
  TableroSudoku t = new TableroSudoku( 
       ".4....36263.941...5.7.3.....9.3751..3.48.....17..62...716.9..2...96.......312..9.");
  List<TableroSudoku> lt = t.resolverTodos();
  System.out.println(t);
  System.out.println(lt.size());
  for(Iterator<TableroSudoku> i= lt.iterator(); i.hasNext();) {
   TableroSudoku ts = i.next(); 
   System.out.println(ts);
   
  }

 }
 
 
}


Pues lo que hace es ver si lo que le damos es solución. si lo es, lo mete en una lista y en otro caso crea una lista con los posibles candidatos a soluciones (las cuasi-soluciones a las que puede llegar dando un único paso). Y con un while va usando recursivamente la función resolverTodos en cada una de ellas. De esta forma si alguna presunta solución (al pasarle el resolverTodos) no tiene huecos libres, será solución y se añadirá a la lista.

Saludos, espero que os haya gustado ;)

domingo, 27 de abril de 2014

Examen parcial Concurrencia Java 2012

Buenas gente, aquí os traigo el examen parcial de Programación de Sistemas y Concurrencia del 2012 resuelto (la parte de Java). El enunciado dice tal que así:

Desarrollar un programa en Java que permita calcular de manera concurrente el máximo de un array de elementos de tipo int. Para calcular el máximo suponer que se dispone de un array de N posiciones y M hebras donde N y M podrán ser leídos desde teclado o almacenados como constantes. Los valores contenidos en el array son inicializados aleatoriamente antes de la creación de las hebras.
La solución desarrollada dividirá el array N en M fragmentos de manera que cada una de las hebras calculará el máximo del fragmento de array que le corresponda (se puede suponer para simplificar que N es múltiplo de M). Posteriormente, una vez hayan terminado todas las hebras de calcular su máximo local, en la hebra principal del programa se procederá a calcular el máximo global examinando el máximo local de cada una de las hebras.
La siguiente figura ilustra el proceso para un array de 9 posiciones y 3 hebras.

Y aquí teneis el resultado:

import java.util.*;
public class Nodo extends Thread{
 
 private int[] vector;
 private int inic,fin;
 private int valor;
 private boolean[] res;
 
 public Nodo(int[] vector,int inic,int fin,int valor,boolean[] res){
  // busca "valor" en vector[inic..fin-1] y deja el resultado en res[0]
  this.vector = vector;
  this.valor = valor;
  this.res = res;
  this.inic = inic;
  this.fin = fin;
 }
 
 public void run(){
  
  if (inic == fin){
   res[0] = false;
  } else if (inic+1==fin){
   res[0] = (vector[inic]== valor);
  }else{
   boolean[] res1 = new boolean[1];
   boolean[] res2 = new boolean[1];
   Nodo izdo = new Nodo(vector,inic,(inic+fin)/2,valor,res1);
   Nodo dcho = new Nodo(vector,(inic+fin)/2,fin,valor,res2);
   izdo.start();
   dcho.start();
   try{
    izdo.join();
    dcho.join();
   } catch(InterruptedException ie){}
   
   res[0] = res1[0]||res2[0];
  }
  //System.out.println("Buscamos "+ valor +" en "+Arrays.toString(Arrays.copyOfRange(vector,inic,fin)) + "  "+res[0]);
 }
 
 public static void main(String[] args){
  Random r = new Random();
  int[] vector = new int[r.nextInt(20)+1];
  for (int i = 0; i<vector.length; i++){
   vector[i] = r.nextInt(20);
  }
  int valor = r.nextInt(20);
  System.out.println("Buscamos "+ valor +" en "+Arrays.toString(vector));
  boolean[] res = new boolean[1];
  Nodo nodo = new Nodo(vector,0,vector.length,valor,res);
  nodo.start();
  try{
   nodo.join();
  }catch(InterruptedException ie){}
  System.out.println("Esta el elemento: "+res[0]);
 }

}

Bueno, ya veis que era bastante sencillo. Espero que no hayais tenido mucha dificultad. Saludos y hasta otra ;)

viernes, 25 de abril de 2014

Estructura Bag (saco) en Haskell. Estructuras de Datos

Buenas gente. Iba a escribir sobre una práctica de Java, pero he visto que los conceptos no venían explicados en los apuntes, por lo que primero haremos la parte de Haskell que es donde mejor lo explican. Aquí teneis el enunciado:

Un saco (o multiconjunto) es parecido a un conjunto salvo que un elemento puede estar incluido varias veces. Por ejemplo, {‘b’, ‘a’, ‘d’, ‘d’, ‘a’, ‘c’ , b’, ‘a’} es un saco que incluye tres ocurrencias del carácter ‘a’ , dos ocurrencias del ‘b’, una del ‘c’ y dos del ‘d’.

a) Implementa sacos en Haskell usando el siguiente tipo de datos:
data Bag a = Empty | Node a Int (Bag a)
De forma que en cada nodo aparece, además del saco restante, cada elemento junto con su contador de ocurrencias, o sea, el número de veces que aparece. Para agilizar las operaciones de inserción y borrado en un Bag, interesa que los nodos estén ordenados atendiendo al orden de los elementos a incluir. Además, no deben aparecer elementos con contador nulo (o negativo). Por ejemplo, el saco anterior se representa por:
Node ‘a’ 3 (Node ‘b’ 2 (Node ‘c’ 1 (Node ‘d’ 2 Empty)))
La implementación debe incluir las siguientes funciones:
empty :: Bag a -- Devuelve un saco vacío
isEmpty :: Bag a -> Bool -- Comprueba si un saco está vacío
insert :: (Ord a) => a -> Bag a -> Bag a --Inserta una nueva ocurrencia
occurrences :: (Ord a) => a -> Bag a -> Int -- Devuelve el número de -- ocurrencias de un elemento en un saco (0 si el elemento no está) -}
delete :: (Ord a) => a -> Bag a -> Bag a -- Borra una ocurrencia de un -- elemento de un saco. Devuelve el mismo saco si el elemento no estaba incluido

b) Proporciona una especificación de Bag definiendo sus axiomas para las diferentes operaciones y comprueba la implementación realizada con QuickCheck. Para ello, incluye en el módulo la siguiente instancia para generar sacos aleatorios:
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where
arbitrary = do
xs <- listOf arbitrary
return (foldr insert empty xs) 

La solución es la siguiente:

module DataStructures.Bag.LinearBag
  ( Bag
  , empty
  , isEmpty
  , insert
  , delete
  , occurrences
  ) where

import Data.List(intercalate)
import Test.QuickCheck

data Bag a = Empty | Node a Int (Bag a)

empty :: Bag a
empty = Empty

isEmpty :: Bag a -> Bool
isEmpty Empty = True
isEmpty _     = False

insert :: (Ord a) => a -> Bag a -> Bag a
insert x Empty = Node x 1 Empty
insert x (Node y n b)
  | x<y        = Node x 1 (Node y n b)
  | x==y       = Node y (n+1) b
  | otherwise  = Node y n (insert x b)

occurrences :: (Ord a) => a -> Bag a -> Int
occurrences x Empty = 0
occurrences x (Node y n b)
  | x<y             = 0
  | x==y            = n
  | otherwise       = occurrences x b

delete :: (Ord a) => a -> Bag a -> Bag a
delete x Empty = Empty
delete x (Node y n b)
  | x<y        = Node y n b
  | x==y       = if n>1 then Node y (n-1) b else b
  | otherwise  = delete x b

-- Showing a bag
instance (Show a) => Show (Bag a) where
        show b = "LinearBag(" ++ intercalate "," (map show (elems b)) ++")"
          where
            elems Empty        = []
            elems (Node x n b) = replicate n x ++ elems b

-- bag equality
instance (Eq a) => Eq (Bag a) where
  Empty        == Empty            = True
  (Node x n b) == (Node x' n' b')  = x==x' && n==n' && b==b'
  _            == _                = False

-- This instace is used by QuickCheck to generate random bags
instance (Ord a, Arbitrary a) => Arbitrary (Bag a) where
    arbitrary = do
      xs <- listOf arbitrary
      return (foldr insert empty xs)
 


He de decir que ésta solución no está mal, pues ha sido implementada por un profesor y es la que se utilizaba de prueba para los que no sabían hacerla y la necesitaban. Yo si supe hacerla, pero como quiero que tengáis el material de mejor calidad posible, agradecedle a Pepe Gallardo (el mejor en Haskell que conozco) el código.

Saludos, el domingo subo el homónimo en Java ;)

miércoles, 23 de abril de 2014

Práctica prDiccionarios en Java

Buenas gente. Aquí os traigo otra práctica. Es la segunda del pdf de prKWIC. No parece demasiado dificil, ahora lo veremos ;).

Como siempre aquí os dejo el pdf y los archivos auxiliares ( datos, frases, noClaves, Test y TestDiccionario).

Aquí os pongo el enunciado:


En esta práctica se construirá un paquete diccionarios que incluya:
· La interfaz Diccionario<C,V>,
· La clase DiccionarioDePalabras
Los diccionarios pueden ser considerados como “memorias asociativas”, que se indexan mediante claves, a diferencia de las listas, que lo hacen mediante un rango de números. Por tanto, el acceso a los valores almacenados en un diccionario se realiza a través de la clave correspondiente. Un requisito es que las claves sean únicas (dentro del mismo diccionario).
Las operaciones principales sobre un diccionario que asocia una lista de valores de tipo V a claves de tipo C son las siguientes:
boolean insertar(C,V)Añade al diccionario un valor con una clave dada; si se inserta un valor asociándolo a una clave ya existente, se añade el valor a la lista de valores asociados a la clave. Si la estructura contenía una entrada con esa clave se devuelve false; true en cualquier otro caso. Si se intenta insertar una clave null se lanzará una excepción RuntimeException.
List<V> consultar(C)Devuelve la lista de valores asociados a una clave determinada en el diccionario; si la clave que se pasa como argumento no existe en el diccionario (o es null) se devuelve null.
boolean eliminar(C)Elimina una pareja clave- lista de valores correspondiente a la clave que se pasa como argumento, devolviendo true si la clave existe y, por tanto, la operación se ha podido realizar, y false en caso contrario.
int tamaño()Devuelve el número de entradas (parejas clave-lista de valores) que incluye el diccionario.
void limpiar()Vacía el diccionario, eliminando todas sus claves.
También deberán proporcionarse dos métodos uno que devuelve una lista con todas las claves utilizadas en un diccionario (List<C> claves()), y otro que vuelca el diccionario en un fichero cuyo nombre se da como parámetro (escribirDiccionario(String nombFich)), siguiendo el formato que se da al final del enunciado.
La clase DiccionarioDePalabras implementa la interfaz Diccionario<C,V> en la que tanto las claves como los valores son de tipo String y utiliza una aplicación (Map) para almacenar los pares clave-lista de valores ordenados según el orden alfabético de sus claves.
La clase DiccionarioDePalabras tiene un constructor por defecto, y otro que tiene como parámetro el nombre de un fichero del que se leen las palabras y definiciones del diccionario con el siguiente formato:
feo:Que carece de belleza;Que causa horror o aversión;Desaire manifiesto, grosero;
bombín:Sombrero hongo;
costal:Perteneciente a las costillas;Saco grande de tela ordinaria;
arco:Porción continua de una curva;Arma hecha de una varilla de acero;
Es decir, cada palabra está separada de las definiciones por dos puntos “:”, y está seguida de una secuencia de definiciones separadas por un punto y coma “;”. Cualquier error de formato debe producir una excepción del tipo RuntimeException.
Clase ejemplo de uso:

import java.io.*;

import diccionarios.Diccionario;
import diccionarios.DiccionarioDePalabras;
public class TestDiccionario {

 public static void main(String[] args) throws IOException{
  Diccionario<String, String> dic = new DiccionarioDePalabras("datos.txt");

  System.out.println(dic.claves());
  System.out.println(dic.insertar("feo", "Horroroso"));
  System.out.println(dic.consultar("feo"));
  System.out.println(dic.consultar("arco"));
  System.out.println(dic.eliminar("arco"));
  System.out.println(dic.consultar("costal"));
  System.out.println(dic.insertar("costal", "Listón de madera"));
  System.out.println(dic.consultar("costal"));
  System.out.println(dic.tamaño());
  System.out.println(dic.consultar("bombín"));
  System.out.println(dic.claves());
  System.out.println(dic.eliminar("feo"));
  System.out.println(dic.eliminar("feo"));
  System.out.println(dic.claves());
  dic.escribirDiccionario("dic.txt");
  dic.limpiar();
  System.out.println(dic.tamaño());

 }
}


Resultado de la ejecución de la clase de ejemplo de uso:
[arco, bombín, costal, feo]
false
[Que carece de belleza, Que causa horror o aversión, Desaire manifiesto, grosero, Horroroso]
[Porción continua de una curva, Arma hecha de una varilla de acero]
true
[Perteneciente a las costillas, Saco grande de tela ordinaria]
false
[Perteneciente a las costillas, Saco grande de tela ordinaria, Listón de madera]
3
[Sombrero hongo]
[bombín, costal, feo]
true
false
[bombín, costal]
0
El fichero “dic.txt” tendría el siguiente contenido:
bombín:
Sombrero hongo
costal:
Perteneciente a las costillas
Saco grande de tela ordinaria
Listón de madera
Ahora procedo a poneros los resultados:
Primero la clase Diccionario:
import java.io.IOException;
import java.util.List;


public interface Diccionario <C, V>{ 
 public boolean insertar(C clave, V valor);
 public List <V> consultar (C clave);
 public boolean eliminar ( C clave);
 public List <C> claves();
 public void escribirDiccionario(String nomFich) throws IOException;
 public int tamaño();
 public void limpiar();

}
 


Ahora la clase DiccionarioDePalabras:
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.SortedMap;
import java.util.TreeMap;


public class DiccionarioDePalabras implements Diccionario<String, String>{
 private SortedMap<String, List<String>> diccionario;
 
 public DiccionarioDePalabras(String std) throws IOException {
  diccionario = new TreeMap<String, List<String>>();
  Scanner sc = new Scanner(new File(std));
  leeDiccionario(sc);
 }
 
 private void leeDiccionario (Scanner sc) throws IOException {
  while (sc.hasNextLine()) {
   String linea = sc.nextLine();
   Scanner sPal = new Scanner(linea);
   sPal.useDelimiter(":");
   String palabra = sPal.next();
   String definicion = sPal.next();
   Scanner sSig = new Scanner(definicion);
   sSig.useDelimiter(";");
   List<String> definiciones = diccionario.get(palabra);
   if(definiciones == null) {
    definiciones = new ArrayList<String>();
    }
   while(sSig.hasNext()) {
    String def = sSig.next();
    definiciones.add(def);
   }
   diccionario.put(palabra, definiciones);
   
   //feo: Que carece de belleza; Que causa horror;
   //palabra : def1; def2; def3...
  }
  sc.close();
 }
 
 @Override
 public boolean insertar(String clave, String valor) throws RuntimeException{
  // TODO Auto-generated method stub
  boolean estaba = false;
  if(clave.equals(null)) throw new RuntimeException("Palabra no válida");
  if(diccionario.keySet().contains(clave)) {
   diccionario.get(clave).add(valor);
  } else {
   estaba = false;
   diccionario.keySet().add(clave);
   diccionario.get(clave).add(valor);
  }
  return estaba;
 }

 @Override
 public List<String> consultar(String clave) {
  // TODO Auto-generated method stub
  List<String> lista = new ArrayList<String>();
  if(diccionario.keySet().contains(clave)) {
   lista = diccionario.get(clave);
  } else {
   if(diccionario.keySet().contains(clave)) lista = null;
  }
  return lista;
 }

 @Override
 public boolean eliminar(String clave) {
  // TODO Auto-generated method stub
  return diccionario.keySet().remove(clave);
 }

 @Override
 public List<String> claves() {
  // TODO Auto-generated method stub
  List<String> lista = new ArrayList<String>();
  for(String pal : diccionario.keySet()) {
   lista.add(pal);
  }
  return lista;
 }

 @Override
 public void escribirDiccionario(String nomFich) throws IOException {
  // TODO Auto-generated method stub
  
 }

 @Override
 public int tamaño() {
  // TODO Auto-generated method stub
  return diccionario.size();
 }

 @Override
 public void limpiar() {
  // TODO Auto-generated method stub
  diccionario.clear();
 }

 
}
 

lunes, 21 de abril de 2014

Conectar dos Arduinos mediante RadioFrecuencia

Ups. Bueno, ayer nos despistamos un poco y no subimos nada (no nos crucifiqueis porfaplis :p). Hoy os traigo algo bastante curioso. Cómo encender un led en un arduino desde otro usando RadioFrecuencia.
Aquí podeis descargaros los archivos .ino directos para abrir en arduino: Emisor y Receptor. Además os dejo la librería VirtualWire la cual solo teneis que descomprimirla donde estén todas las demás (en mi caso en libraries).

Aquí un video de proyecto final:
Aquí os doy la lista de materiales necesarios:

   Para el emisor:
      - Led de 10.000 Ohmios      - Pulsador
      - Jumpers (cablecitos de conexión)
      - Protoboard
      - Arduino (está claro. Yo uso el Uno R3)
      - Un emisor de RadioFrecuencia.(He usado uno de 433MHz)
Aquí teneis el esquemático del circuito emisor:

Y aquí las conexiones (por si no han quedado claras):



Ahora el Receptor.
      - Arduino cables y protoboard (como en el anterior)
      - Receptor de RadioFrecuencia
      - Led
      - Resistencia de 220 Ohmios 
Este es el esquemático:
Y estas algunas fotos de las conexiones:


Aquí os dejo el código del emisor:
#include <VirtualWire.h>  //incluimos la libreria de virtualwire
int boton = 2;            //Asignamos el numero dos al boton
char *msg = "";           //Asignamos el mensaje en blanco
int eb = 0;               //Asignamos el estado del boton en 0

void setup(){
  vw_setup(7000);            //Configuramos la velocidad de transimsion de datos
  pinMode(boton, INPUT);    //Configuramos el pin boton como entrada
}

void loop () {
  eb = digitalRead(boton);    //Leemos el estado del boton y lo guardamos en la variable
  if ( eb == HIGH) {          //Condicion para ver si esta activado el boton
    msg = "E";                //Si lo esta, asignamos la letra E al mensaje
    vw_send((uint8_t *)msg, strlen(msg));  //y enviamos este mensaje
  }
  else {                      //Si no lo esta
    msg = "A";                //Asignamos A al mensaje
    vw_send((uint8_t *)msg, strlen(msg));    // y lo enviamos

  }
}

Y aquí el del receptor:
#include <VirtualWire.h>  //incluimos la libreria de virtualwire

int led = 12; //Asignamos el 12 a la variable led

void setup() {
  vw_setup(7000);        //Seleccionamos la velocidad de transmision de datos
  vw_rx_start();         //Iniciamos la comunicación
  pinMode(led, OUTPUT);  //Asignamos la variable led como salida
}

void loop(){
  uint8_t msg[VW_MAX_MESSAGE_LEN];
  uint8_t len = VW_MAX_MESSAGE_LEN;

  if (vw_get_message(msg, &len)){  //Condicion para ver si hay mensaje
    if ( msg[0] == ‘E’) {            //Si el mensaje es una E
      digitalWrite(led, HIGH);         //Encendemos el LED
    }
    else if (msg[0] == ‘A’){         // Si es una A
      digitalWrite(led, LOW);        //Apagamos el led
    }
  }
}

Bueno gente, espero que hayais estado un rato entretenidos trasteando. Este proyecto también se puede hacer con un solo Arduino pero ni la impresión es la misma (que tener dos Arduinos conectados) ni es necesario, pues se haría directamente, ¿no creeis?

Saludos a todos, perdón por no subir nada ayer y, hasta la próxima! ;)

viernes, 18 de abril de 2014

Ejercicios C++: Registros y arrays

Empezamos a ver los registros y arrays de C++, por lo que la cosa ya se complica un poquito. Os dejo unos ejercicios para practicar.

En los ejercicios se pedirá la dimensión real del array, que deberá ser menor que el tamaño máximo que se haya puesto en la definición de dicho array. Para la realización de los ejercicios nos serán útiles las siguientes funciones:

unsigned leerDim()

void leerArray(TVector &v, unsigned dim)

void ImprimirVector(const TVector &v, unsigned n)

Otra opción más adecuada es definir una estructura registro que contenga tanto el array en sí como su dimensión:

const unsigned int MAX = 100;

typedef float TVect[MAX];

struct TVector

{

  TVect vect;

  unsigned dim;

};
 
Por tanto cada ejercicio os lo dejaré de ambas maneras aunque son muy parecidas ;)

Ejercicio 1.
Desarrollar una función de nombre tomar_mayor que tome como parámetro un array de valores reales (usar float o double queda a la elección del alumno) y dé como resultado el valor mayor contenido en dicho array. Como tamaño máximo del array puede tomarse el valor 100. Crear también una función main para comprobar que todo funciona bien.

#include <iostream>
using namespace std;

const unsigned MAXIMO = 100;
typedef double TVector[MAXIMO];


unsigned leerDim (){
 unsigned elementos;
 cout << "Introduce el número de elementos: ";
 cin >> elementos;
 return elementos;
}

void leerArray(TVector& miarray, unsigned elementos){
 cout << "Introduce "<< elementos << " elementos: "<< endl;
 for(unsigned i=0; i< elementos; i++){
  cin >> miarray[i];
 }
}

double tomar_mayor(const TVector& miarray, unsigned elementos){
 double mayor = miarray[0];
 for(unsigned i=1; i< elementos; i++){
  if(miarray[i] > mayor){
   mayor = miarray[i];
  }
 }
 return mayor;
}


int main() {
 cout << "Mayor contenido de un array." << endl;
 TVector miarray;
 unsigned elementos = leerDim();
 leerArray(miarray, elementos);
 cout << "El mayor de los números del array es "<< tomar_mayor(miarray, elementos); ;

 return 0;
}



#include  <iostream>
using namespace std;

const unsigned int MAX = 100;

typedef float TVect[MAX];

struct TVector
{
  TVect vect;
  unsigned dim;
};

void leerDim (TVector &v){
 cout << "Introduce el número de elementos: ";
 cin >> v.dim;
}

void leerArray(TVector& miarray){
 cout << "Introduce "<< miarray.dim << " elementos: "<< endl;
 for(unsigned i=0; i< miarray.dim; i++){
  cin >> miarray.vect[i];
 }
}

double tomar_mayor(const TVector& miarray){
 double mayor = miarray.vect[0];
 for(unsigned i=1; i< miarray.dim; i++){
  if(miarray.vect[i] > mayor){
   mayor = miarray.vect[i];
  }
 }
 return mayor;
}


int main() {
 cout << "Mayor contenido de un array." << endl;
 TVector miarray;
 leerDim(miarray);
 leerArray(miarray);
 cout << "El mayor de los números del array es "<< tomar_mayor(miarray); ;

 return 0;
}
Ejercicio 2.
Mediante el uso de arrays, diseñar una función para calcular la media de las estaturas de una clase asumiendo que el número máximo de alumnos en una clase es de 50 y que, además, las estaturas son valores expresados en centímetros. Crear otras dos funciones para determinar cuántos alumnos son más altos y cuántos más bajos que la media. El nombre de las funciones queda a criterio del alumno. Crear también una función main para comprobar que estas funciones se han codificado correctamente.

#include  <iostream>
using namespace std;

const unsigned MAXIMO = 50;

typedef unsigned TAlturas[MAXIMO];

unsigned leerDim (){
 unsigned elementos;
 cout << "Introduce el número de elementos: ";
 cin >> elementos;
 return elementos;
}

void leerArray(TAlturas& alturas, unsigned elementos){
 cout << "Introduce "<< elementos<< " elementos: "<< endl;
 for(unsigned i=0; i< elementos; i++){
  cin >> alturas[i];
 }
}

double calcularMedia (const TAlturas& alturas, unsigned elementos){
 unsigned suma = 0;
 for(unsigned i = 0; i < elementos; i++){
  suma = suma + alturas[i];
 }
 return suma/elementos;
}

unsigned masAltos(const TAlturas& alturas, double media, unsigned elementos){
 unsigned altos = 0;
 for(unsigned i = 0; i < elementos; i++){
   if(alturas[i] > media){
    altos++;
   }
 }
 return altos;
}


unsigned masBajos(const TAlturas& alturas, double media, unsigned elementos){
 unsigned bajos = 0;
 for(unsigned i = 0; i < elementos; i++){
   if(alturas[i] < media){
    bajos++;
   }
 }
 return bajos;
}


int main() {

 TAlturas alturas;
 unsigned elementos = leerDim();
 leerArray(alturas, elementos);
 double media = calcularMedia(alturas, elementos);
 cout << "La altura media de la clase es "<< media << " centímetros." << endl;
 cout << masAltos(alturas, media, elementos) << " alumnos son más altos que la media y "<< masBajos(alturas, media, elementos) << " alumnos son más bajos que la media.";


 return 0;
}
#include  <iostream>
using namespace std;

const unsigned MAXIMO = 50;

typedef unsigned TAlt[MAXIMO];

struct TAlturas
{
  TAlt vect;
  unsigned dim;
};

void leerDim (TAlturas &v){
 cout << "Introduce el número de elementos: ";
 cin >> v.dim;
}

void leerArray(TAlturas& miarray){
 cout << "Introduce "<< miarray.dim << " elementos: "<< endl;
 for(unsigned i=0; i< miarray.dim; i++){
  cin >> miarray.vect[i];
 }
}

double calcularMedia (const TAlturas& alturas){
 unsigned suma = 0;
 for(unsigned i = 0; i < alturas.dim; i++){
  suma = suma + alturas.vect[i];
 }
 return suma/alturas.dim;
}

unsigned masAltos(const TAlturas& alturas, double media){
 unsigned altos = 0;
 for(unsigned i = 0; i < alturas.dim; i++){
   if(alturas.vect[i] > media){
    altos++;
   }
 }
 return altos;
}


unsigned masBajos(const TAlturas& alturas, double media){
 unsigned bajos = 0;
 for(unsigned i = 0; i < alturas.dim; i++){
   if(alturas.vect[i] < media){
    bajos++;
   }
 }
 return bajos;
}


int main() {

 TAlturas alturas;
 leerDim(alturas);
 leerArray(alturas);
 double media = calcularMedia(alturas);
 cout << "La altura media de la clase es "<< media << " centímetros." << endl;
 cout << masAltos(alturas, media) << " alumnos son más altos que la media y "<< masBajos(alturas, media) << " alumnos son más bajos que la media.";


 return 0;
}
Ejercicio 3.
Diseñar un algoritmo (y desarrollar la función C++ correspondiente y el main para probarla) que acepte de teclado una secuencia de números entre 0 y 9 y cuente el número de veces que se repite cada dígito. La secuencia de números de entrada se da por finalizada al leer un número negativo. Ej.:
Entrada: 1 8 7 3 4 8 5 9 5 0 0 4 8 4 5 3 2 8 -1
Salida: 0: 2; 1:1; 2: 1; 3: 2; 4: 3; 5: 3; 6: 0; 7: 1; 8: 4; 9: 1

#include <iostream>
using namespace std;

typedef int TFrecuencias[10];

void inicializar(TFrecuencias& frecuencias){
 for(unsigned i= 0; i < 10; i++){
  frecuencias[i]= 0;
 }
}



void leerDatos(TFrecuencias& frecuencias){
 int num = -1;
 cout << "Introducir lista de números y terminar con un negativo: "<< endl;

 do {
  frecuencias[num]++;
  do{
  cin >> num;
  }while(num >= 10);
 }while(num >= 0);
}

void imprimirFrecuencias (const TFrecuencias& frecuencias){
 for(unsigned i= 0; i < 10; i++){
  cout << i << ":"<< frecuencias[i] <<"; ";
 }
}



int main() {
 TFrecuencias frecuencias;
 inicializar(frecuencias);
 leerDatos(frecuencias);
 imprimirFrecuencias(frecuencias);
 return 0;
}
Ejercicio 4.
Un histograma es una gráfica que muestra la frecuencia con que aparecen en una lista dada los distintos valores que la pudieran formar. Por ejemplo, si los valores de una lista pueden estar comprendidos entre 0 y 9, y la lista es:
6 4 4 1 9 7 5 6 4 2 3 9 5 6 4
entonces su histograma es:

Esto indica que los dígitos 0 y 8 no aparecen ninguna vez, que 1, 2, 3 y 7 aparecen una vez, 5 y 9 dos veces, etc. Escriba un programa que lea una lista de números comprendidos entre 0 y 9 separados por espacios (la lista acabará cuando se lea un número negativo, y a priori no se puede determinar cuántos números contiene) e imprima por pantalla un histograma como el anterior. Para ello deben usarse funciones y arrays.
#include <iostream>
using namespace std;

typedef unsigned TFrecuencias[10];

void inicializar(TFrecuencias& frecuencias){
 for(unsigned i= 0; i < 10; i++){
  frecuencias[i]= 0;
 }
}



void leerDatos(TFrecuencias& frecuencias){
 int num = -1;

 do {
  frecuencias[num]++;
  cin >> num;
 }while(num >= 0);
}

unsigned tomar_mayor(const TFrecuencias& miarray){
 unsigned mayor = miarray[0];
 for(unsigned i=1; i< 10; i++){
  if(miarray[i] > mayor){
   mayor = miarray[i];
  }
 }
 return mayor;
}


void imprimirFrecuencias (TFrecuencias& frecuencias, unsigned mayor){
 unsigned a = mayor;

 for(unsigned i= 0; i < mayor; i++){


  for(unsigned e=0; e< 10; e++){
   if(frecuencias[e] == a){
    cout << "* ";
    frecuencias[e] = frecuencias[e]-1;
   }else{
    cout << "  ";
   }
  }
  a = tomar_mayor(frecuencias);
  cout << endl;
 }

 cout << "0 1 2 3 4 5 6 7 8 9";

}



int main() {
 TFrecuencias frecuencias;
 inicializar(frecuencias);
 leerDatos(frecuencias);
 imprimirFrecuencias(frecuencias, tomar_mayor(frecuencias));
 return 0;
}

Ejercicio 5
La denominada Criba de Eratóstenes es un método para determinar los números primos
entre 1 y N, siguiendo los siguientes pasos:

  • Se escriben los números naturales entre 1 y N.
  • Se deja el 1.
  • Se deja el 2 y se tachan todos los demás números pares.
  • Se deja el 3 y se tachan todos sus múltiplos.
  • Como el 4 ya está tachado, pasamos al 5, que se deja y se tachan todos sus múltiplos (los del 5).
  • ...

Así, cuando pasemos del 13, estarán tachados 14, 15 y 16, con lo que seguimos el proceso
en el 17. El proceso acaba cuando llegamos a la raíz cuadrada de N. Los números que
queden sin tachar, serán primos. La siguiente figura muestra este método aplicado del 1 al
100. Aparecen en blanco los números no marcados y que, por tanto, son primos.

Se pide crear una función denominada eratostenes que, mediante la criba descrita y
haciendo uso de arrays, debe tomar como parámetro un natural N menor o igual a 1000 e
imprimir por pantalla todos los números primos del 1 al N.
#include <iostream>
#include <math.h>
using namespace std;

const unsigned MAXIMO = 1000;
typedef unsigned TArray[MAXIMO];

unsigned leerN (){
 unsigned N;
 do{
 cout << "Introduce N: ";
 cin >> N;
 }while(N > 1000);
 return N;
}

void inicializar(TArray& array, unsigned N){
 for(unsigned i= 0; i < N; i++)
  array[i]=i+1;
}

void eliminar (TArray array, unsigned N){
 for(unsigned i= 2; i < N; i++){
  if(array[i] != 0){
   for(unsigned j = i+1; j < N; j++){
    if((j+1)%(i+1) == 0){
     array[j] = 0;
    }


   }



  }
 }
}

void mostrar(const TArray& array, unsigned N){
 for(unsigned i = 0;i < N; i++){
  if(array[i] != 0){
   cout << array[i] << " ";
  }
 }
}

int main() {
 unsigned dim = leerN();
 TArray array;
 inicializar(array, dim);
 eliminar(array, dim);
 mostrar(array, dim);
 return 0;
}

Ejercicio 6 
Para realizar operaciones con números complejos, podemos definir el siguiente tipo:
struct TComplejo {

double p_real, p_imaginaria;

} 

Escribir funciones que realicen las operaciones de suma, resta, multiplicación y división de números complejos definidos con el tipo anterior:
void sumar(TComplejo &resultado, const TComplejo &a, const TComplejo &b)

void restar(TComplejo &resultado, const TComplejo &a, const TComplejo &b)

void multiplicar(TComplejo &resultado, const TComplejo &a, const TComplejo &b)

void dividir(TComplejo &resultado, const TComplejo &a, const TComplejo &b)

Crear asimismo una función main que permita comprobar el correcto funcionamiento de las funciones anteriores.
#include  <iostream>
using namespace std;

struct TComplejo {
 double p_real, p_imaginaria;
};

void leerComplejo(TComplejo& complejo){
 cout << "Introduce parte real: ";
 cin >> complejo.p_real;
 cout << "Parte imaginaria: ";
 cin >> complejo.p_imaginaria;
}


void sumar(TComplejo &resultado, const TComplejo &a, const TComplejo &b){
 //(a + bi) + (c + di) = (a + c) + (b + d)i
 resultado.p_real= a.p_real +b.p_real;
 resultado.p_imaginaria= a.p_imaginaria + b.p_imaginaria;

}
void restar(TComplejo &resultado, const TComplejo &a, const TComplejo &b){
 resultado.p_imaginaria = a.p_imaginaria - b.p_imaginaria;
 resultado.p_real = a.p_real - b.p_real;
}
void multiplicar(TComplejo &resultado, const TComplejo &a, const TComplejo &b){
 //(a + bi) · (c + di) = (ac − bd) + (ad + bc)i
 resultado.p_real = (a.p_real*b.p_real)-(a.p_imaginaria*b.p_imaginaria);
 resultado.p_imaginaria = (a.p_real*b.p_imaginaria)+(a.p_imaginaria*b.p_real);
}
void dividir(TComplejo &resultado, const TComplejo &a, const TComplejo &b){
 resultado.p_real = ((a.p_real*b.p_real)+(a.p_imaginaria*b.p_imaginaria))/(b.p_real*b.p_real + b.p_imaginaria*b.p_imaginaria);
 resultado.p_imaginaria = (a.p_imaginaria*b.p_real-a.p_real*b.p_imaginaria)/(b.p_real*b.p_real + b.p_imaginaria*b.p_imaginaria);
}
void mostrarComplejo(TComplejo & a){
 cout << a.p_real << "+" << a.p_imaginaria <<"i" << endl;
}

int main() {
 cout << "Operaciones con números complejos." << endl;
 TComplejo a, b, resultado;
 cout << "Introduce dos numeros complejos a operar." << endl;
 leerComplejo(a);
 leerComplejo(b);
 cout << "Resultado de su suma: ";
 sumar(resultado, a, b);
 mostrarComplejo(resultado);
 cout << "Resultado de su resta: ";
 restar(resultado, a, b);
 mostrarComplejo(resultado);
 cout << "Resultado de su multiplicacion: ";
 multiplicar(resultado, a, b);
 mostrarComplejo(resultado);
 cout << "Resultado de su division: ";
  dividir(resultado, a, b);
  mostrarComplejo(resultado);


 return 0;
}

miércoles, 16 de abril de 2014

Práctica prKWIC de Java

Buenas gente, por aquí estoy yo de nuevo. Se que vosotros quereis leer a Cris, pero ahora está en su pueblo y Blogger aún no permite publicar vía telegrama ni paloma mensajera.

Hoy os traigo la que, según creo, es la última práctica de Programación Orientada a Objetos de Primer año. De todos modos, si se me olvida alguna o hay alguna nueva siempre podéis avisarme y pasarme el enunciado ;)
Como siempre os dejo aquí linkeados el enunciado y la clase test.
Bueno, aquí voy con el enunciado:
El objetivo de esta práctica es realizar un glosario o índice de palabras atendiendo a su aparición en un conjunto de frases (KeyWord In Context, KWIC). La idea es analizar una colección de frases, extraer las distintas palabras que aparecen y construir una estructura que establezca una correspondencia entre cada palabra y el conjunto de frases en las que aparece. Para esta práctica será necesario repasar las clases String, StringBuilder y StringTokenizer, así como las clases correspondientes al marco de colecciones de java.
En concreto, se pide: 
a) Definir una clase Titulo que dé envoltura a una frase o título (de tipo String), y que permita
ordenar y comparar frases independientemente de si éstas contienen caracteres en minúsculas o
mayúsculas, así como un método String replace(String pal) para producir una cadena, a
partir del título, con las apariciones de la palabra pal sustituidas por "...". 
b) Definir una clase Indice que mantenga la información relativa a los caracteres separadores que se pueden presentar en los títulos y el índice (palabra -> conjunto de títulos en los que aparece) correspondiente a una colección de objetos de la clase Titulo. Esta clase tendrá:
- i. Dos constructores: uno con un argumento de tipo String con la relación de caracteres
separadores y otro con dos argumentos, uno de tipo String (como el anterior) y otro del
tipo Collection<String> con una relación de frases que habrá que analizar para
construir el correspondiente índice.
- ii. Un método void agregarTitulo(String t) para agregar un título al índice y otro
void agregarTitulo(Collection<String> ct) para agregar una colección de
títulos.
- iii. Un método String presentaIndice() que genere una presentación del índice de
forma que, cuando se imprima, quede como aparece en la salida del programa siguiente: 
Para las frases de entrada
“La rosa púrpura del Cairo”
“La rosa del azafrán”
“El color púrpura”
Salida:
AZAFRÁN
              La rosa del ...
CAIRO
              La rosa púrpura del ...
COLOR
              El ... púrpura
DEL
               La rosa ... azafrán
               La rosa púrpura ... Cairo
EL
               ... color púrpura
LA
               ... rosa del azafrán
               ... rosa púrpura del Cairo
PÚRPURA
               El color ...
               La rosa ... del Cairo
ROSA
               La ... del azafrán
               La ... púrpura del Cairo

c) Definir otra clase IndiceSignificativas, parecida a la clase Indice, que mantenga además
un conjunto de palabras que se consideran no significativas (artículos, preposiciones, conjunciones, …) y que ofrezca los mismos servicios con una diferencia de comportamiento en cuanto a las palabras que mantiene en el índice: sólo mantendrá las palabras significativas que aparezcan en los títulos. En concreto, esta clase tendrá dos constructores: uno con dos argumentos, el primero de tipo String con la relación de caracteres separadores y el segundo de tipo Collection<String> con una relación de palabras no significativas, y otro constructor con tres argumentos, el primero de tipo String con la relación de caracteres separadores, el segundo de tipo Collection<String> con una relación de frases que habrá que analizar para construir el correspondiente índice y el tercero de tipo Collection<String> con una relación de palabras no significativas.  
En este caso el método presentaIndice() generará una presentación del índice que,
cuando se imprima, quedará como aparece en la salida del programa siguiente: 
Para las frases de entrada
“La rosa púrpura del Cairo”
“La rosa del azafrán”
“El color púrpura”
Salida:
AZAFRÁN
               La rosa del ...
CAIRO
               La rosa púrpura del ...
COLOR
               El ... púrpura
PÚRPURA
               El color ...
               La rosa ... del Cairo
ROSA
               La ... del azafrán
               La ... púrpura del Cairo 
Probar el funcionamiento de las clases con la siguiente aplicación:

import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
/*
public class Test {
 public static void main(String[] args) {
  String[] datos = { "La rosa púrpura del Cairo", "La rosa del azafrán",
    "El color Púrpura" };
  List<String> frases = Arrays.asList(datos);
  String separadores = " ,;.:()¿!¡?";
  Indice index = new Indice(separadores, frases);
  System.out.println(index.presentaIndice());
  String[] noSig = { "el", "ella", "la", "lo", "un", "una", "del" };
  Collection<String> colNoSig = Arrays.asList(noSig);
  IndiceSignificativas indexSig = new IndiceSignificativas(separadores,
    frases, colNoSig);
  System.out.println(indexSig.presentaIndice());
 }
}*/

public class Test {

 public static void main(String[] args) {

  String separadores = "[ ,;.:\\(\\)\\¿\\!\\¡\\?]+";
  //String separadores = " ,;.:()¿!¡?";

  try {
   Indice index = new Indice(separadores, "frases.txt");
   // para presentar por pantalla
   PrintWriter pw = new PrintWriter(System.out, true);
   index.presentaIndice(pw);
   // para guardar en fichero
   index.presentaIndice("salida.txt");

   // Ahora con palabrasNoSignificativas
   IndiceSignificativas indexSig = new IndiceSignificativas(
     separadores, "frases.txt", "noClaves.txt");
   // para presentar por pantalla
   indexSig.presentaIndice(pw);

   // para guardar en fichero
   indexSig.presentaIndice("salidaNoSig.txt");
  } catch (IOException e) {
   System.out.println("Error:" + e.getMessage());
  }
 }
}

Bueno, aquí os traigo los resultados: Primero la class Titulo:

public class Titulo implements Comparable<Titulo>{
 private String titulo;
 
 public Titulo(String t) {
  titulo = t;
 }
 
 public boolean equals(Object o) {
  return titulo.equalsIgnoreCase((String) o);
 }
 public int hashCode() {
  return titulo.hashCode();
 }
 @Override
 public int compareTo(Titulo tk) {
  return titulo.compareToIgnoreCase(tk.titulo);
 }
 
 public String toString() {
  return titulo;
 }
 public String replace(String pal) { //Devuelve la string original con las veces que aparezca pal cambiadas por "..." 
  StringBuilder sb = new StringBuilder(titulo);
  String palU = pal.toUpperCase();
  String sbU = sb.toString().toUpperCase();   //Stringbuilder a cadena y lo pasamos a mayuscula
  int ind = sbU.indexOf(palU);     //indexOf devuelve la posición de la primera aparicion de la palabra
  while (ind>=0) {         //  
   sb.replace(ind,  ind + pal.length(), "...");//Cambio el trozo de cadena de sb por el ...
   sbU = sb.toString().toUpperCase();   //Transformo el StringBuilder a cadena mayuscula de nuevo
   ind = sbU.indexOf(palU);     //vuelvo a buscar. Si no encuentra devuelve -1
  } 
  return sb.toString();
 }

}


Luego la class Indice:
import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;


public class Indice {//Extrae de cada frase las palabras.
 protected SortedMap<String, SortedSet<Titulo>> indice;
 private String separadores;
 
 public Indice(String sep) {
  separadores = sep;
  indice = new TreeMap<String, SortedSet<Titulo>>();
 }
 public Indice(String sep, Collection<String> col) {
  this(sep);
  agregarTitulo(col);
 }
 public Indice(String sep, String filFrases) throws IOException {
  this(sep);
  agregarTituloFichero(filFrases);
 }
 
 public void agregarTitulo(Collection<String> col) {
  // TODO Auto-generated method stub
  for(String tit: col) {
   agregarTitulo(tit);
  }
 }
 public void agregarTitulo(String tit) {
  // TODO Auto-generated method stub
  //1º tokenizamos el titulo con los separadores
  Titulo tit2 = new Titulo(tit);
  StringTokenizer st = new StringTokenizer(tit, separadores);
  while(st.hasMoreTokens()) {
   String palabra = st.nextToken().toUpperCase();
   if(!indice.containsKey(palabra)) {
    indice.put(palabra, new TreeSet<Titulo>());
    indice.get(palabra).add(tit2);
    
   } else {
    indice.get(palabra).add(tit2);
   }
  }
 }
 public void agregarTitulo(Scanner sc) {
  while(sc.hasNextLine()) {
   String linea = sc.nextLine();
   agregarTitulo(linea);
  }
 }
 public void agregarTituloFichero(String filFrases) throws IOException {
  Scanner sc = new Scanner(new File(filFrases));
  agregarTitulo(sc); //Método auxiliar
  sc.close();
 }
 public String presentaIndice() {
  String str = "";
  for(String pal : indice.keySet()) {          //recorre las palabras clave 
   str = str + pal + "\n";
   for(Titulo tit : indice.get(pal)) {         //Nos da los titulos de cada palabra clave
    str = str + "\t" + tit.replace(pal);
    str = str + "\n";
   }
  }
  return str;
 }
 
 public void presentaIndice(String salida) throws IOException{
  PrintWriter pw = new PrintWriter(salida);
  presentaIndice(pw);
  pw.close();
 }
 public void presentaIndice(PrintWriter pw){
  for(String pal : indice.keySet()){        //Estos dos bucles podrían cambiarse por un simple
   pw.println(pal);        //pw.println(presentaIndice());
   for(Titulo tit : indice.get(pal)) {
    pw.println("\t" + tit.replace(pal));
   }
  }
 }
}

Y por último la class IndiceSignificativas:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;


public class IndiceSignificativas extends Indice{
 private SortedSet<String> noSignificativas;
 
 public IndiceSignificativas(String sep, Collection<String> noSig) {
  super(sep);
  //la coleccion las recorre, pasa a mayusculas y las mete en el conjunto de forma ordenada
  noSignificativas = new TreeSet<String>();
  for(String str : noSig) {
   noSignificativas.add(str.toUpperCase());
  }
 }
 public IndiceSignificativas(String sep, Collection<String> col, Collection<String> noSig){ //Falta Otro Constructor
  this(sep, noSig);
  this.agregarTitulo(col);
 }
 public IndiceSignificativas(String sep, String fichNoSig) throws IOException {
  super(sep);
  noSignificativas = new TreeSet<String>();
  palabrasNoSignificativas(fichNoSig);
  
 }
 public IndiceSignificativas(String sep, String fich, String fichNoSig) throws IOException {
  super(sep, fich);
  noSignificativas = new TreeSet<String>();
  palabrasNoSignificativas(fichNoSig);
  
 }

 public void palabrasNoSignificativas(String filNoSig) throws FileNotFoundException {
  Scanner sc = new Scanner(new File(filNoSig));
  palabrasNoSignificativas(sc);
 }
 public void palabrasNoSignificativas(Scanner sc)  {
  while(sc.hasNext()) {
   String linea = sc.next();
   noSignificativas.add(linea);
  }
 }
 public String presentaIndice() {
  String str = "";
  for(String pal : indice.keySet()) {          //recorre las palabras clave 
   if(!noSignificativas.contains(pal)) {
    str = str + pal + "\n";
    for(Titulo tit : indice.get(pal)) {         //Nos da los titulos de cada palabra clave
     str = str + "\t" + tit.replace(pal);
     str = str + "\n" + "\n";
    }
   }
   
  }
  return str;
 }
 public void presentaIndice(String salida) throws IOException{
  PrintWriter pw = new PrintWriter(salida);
  presentaIndice(pw);
  pw.close();
 }
 public void presentaIndice(PrintWriter pw){
  for(String pal : indice.keySet()){        //Estos dos bucles podrían cambiarse por un simple
   if(!noSignificativas.contains(pal.toLowerCase())) {
     pw.println(pal);        //pw.println(presentaIndice());
     for(Titulo tit : indice.get(pal)) {
      pw.println("\t" + tit.replace(pal));
     }
   }
   
  }
 }
 
}

Bueno gente, espero que os hayan gustado mis entradas de POO y os hayan sido de gran ayuda para aprobar ésta asignatura con buena nota ^^ Eso no significa que me vaya, aún quedan muchas cosas por subir :P

Hasta la próxima!! ;)

Actualización: He encontrado los archivos de entrada y salida y os los linkeo aquí:

Frases. 
Noclaves.
Salida
SalidanoSig

lunes, 14 de abril de 2014

Práctica AnagramasSimple Java POO

Buenas gente, aquí os traigo otra práctica. prAnagramasSimple. Como siempre, aquí os dejo linkeados el pdf (es el mismo que el de la práctica de llaves) y un programa principal para probarlo.

A diferencia de la práctica de las llaves, ésta parte del pdf si me permite copiar por lo que aquí os dejo el enunciado ;)
1. Un anagrama de una palabra es otra palabra obtenida mediante una permutación de sus letras; por ejemplo, saco es un anagrama de cosa. La signatura de una palabra se define como la cadena resultante de ordenar alfabéticamente las letras de dicha palabra en minúsculas. Así, la signatura de saco y cOSa es acos. Teniendo en cuenta esto se deberá construir una clase Palabra con las siguientes características: · Las instancias de esta clase deben mantener información de una palabra: una cadena de caracteres que la representa y su correspondiente signatura. · El constructor de la clase recibirá como argumento la cadena de caracteres y deberá construir su signatura. · La clase contará con un método boolean esAnagrama(Palabra), que determinará si la palabra argumento es o no un anagrama de la receptora. · Redefine los métodos equals(Object), hashCode() y toString(), teniendo en cuenta que para que dos palabras sean iguales basta con que lo sean las cadenas de caracteres correspondientes, con independencia de su tipografía (no se distinguen mayúsculas de minúsculas). · Deberá existir un orden natural entre palabras basado en el orden lexicográfico de las cadenas correspondientes con independencia de su tipografía. · Debe existir un método String getPalabra() que devuelve la cadena que representa la palabra y otro String getSignatura() que devuelve la cadena que representa la signatura. 2. Crear la clase Anagrama que almacenará palabras a partir de cadenas de caracteres que le proporcionaremos. En la información almacenada, cada palabra estará asociada con el conjunto de otras palabras incluidas en esta clase con las que forma un anagrama (ver el listado más abajo). · Define un constructor para crear la clase que inicializará las estructuras necesarias para guardar la información. Las palabras deberán estar ordenadas según el orden natural (ver el listado más abajo). · Define el método void nuevaPalabra(String) que incluye una nueva palabra a partir de la cadena que se le proporciona. Si la palabra ya se encuentra en la estructura no hace nada. Si no estaba, deberá asociarse a cualquier palabra que forme anagrama con ella. Además, esas que forman anagrama también deberán estar asociadas con ésta. Por ejemplo, al introducir mora, se debe asociar con amor, roma y ramo y a su vez, estas tres se deben asociar con mora. · Define el método void mostrarEnConsola() que muestra la información contenida en el anagrama en la salida estándar. El listado que hay más abajo muestra cómo hacerlo. Si las palabras introducidas en un anagrama son olí, ramo, amor, cosa, caso, ostra, lío, roma, astro, mora, lió, saco, el método que muestra en consola deberá producir la siguiente salida (nótese que no se muestra la signatura de las palabras): amor ( mora ramo roma ) astro ( ostra ) caso ( cosa saco ) cosa ( caso saco ) lió ( ) lío ( olí ) mora ( amor ramo roma ) olí ( lío ) ostra ( astro ) ramo ( amor mora roma ) roma ( amor mora ramo ) saco ( caso cosa ) 3. Además del orden natural definido para las palabras, construye una clase SatPalabra que proporcione un orden alternativo para las palabras basado en la longitud de las cadenas y, en caso de igualdad, en el orden ascendente lexicográfico, con independencia de su tipografía. Incluir un nuevo constructor a la clase Anagrama que tome como argumento un objeto de SatPalabra y cree un anagrama que genere el listado con esta ordenación alternativa: lió ( ) lío ( olí ) olí ( lío ) amor ( mora ramo roma ) caso ( cosa saco ) cosa ( caso saco ) ramo ( amor mora roma ) roma ( amor mora ramo ) saco ( caso cosa ) astro ( ostra ) ostra ( astro ) Ejemplo del programa principal (las palabras se debe introducir como argumentos del programa): 
public class mainAnagramas {
 public static void main (String[] args) {
  System.out.println("Orden Natural");
  Anagrama an1 = new Anagrama();
  for (String arg: args) {
   an1.nuevaPalabra(arg);
  }
  an1.mostrarEnConsola();
  System.out.println();
  System.out.println("Orden Alternativo");
  Anagrama an2 = new Anagrama(new SatPalabra());
  for (String arg: args) {an2.nuevaPalabra(arg);
  }
  an2.mostrarEnConsola();
 }
}

La salida producida:
Orden natural:
amor ( mora ramo roma )
astro ( ostra )
caso ( cosa saco )
cosa ( caso saco )
lió ( )
lío ( olí )
mora ( amor ramo roma )
olí ( lío )
ostra ( astro )
ramo ( amor mora roma )
roma ( amor mora ramo )
saco ( caso cosa )

Orden alternativo:
lió ( )
lío ( olí )
olí ( lío )
amor ( mora ramo roma )
caso ( cosa saco )
cosa ( caso saco )
mora ( amor ramo roma )
ramo ( amor mora roma )
roma ( amor mora ramo )
saco ( caso cosa )
astro ( ostra )
ostra ( astro )
Y aquí tenéis las soluciones:


Class Anagrama:
import java.util.*;


public class Anagrama {
 private Map<Palabra, Set<Palabra>> anagramas;
 
 public Anagrama() {
  anagramas = new TreeMap<Palabra, Set<Palabra>>();
 }
 public Anagrama(Comparator<Palabra> cs) {
  anagramas = new TreeMap<Palabra, Set<Palabra>>(cs);
 }
 public void nuevaPalabra(String pal) {
  Palabra sPal = new Palabra(pal);
  if(!anagramas.containsKey(sPal)) {
   //Creo una nueva entrada en la aplicación
   //Creo el conjunto vacío
   Set<Palabra> conjunto = new TreeSet<Palabra>();
   anagramas.put(sPal, conjunto);
  
   for(Palabra p: anagramas.keySet()) {
    if(sPal.esAnagrama(p) && (!sPal.equals(p))) {
     Set<Palabra> con = anagramas.get(p);
     con.add(sPal);
     Set<Palabra> condof = anagramas.get(sPal);
     condof.add(p);
    
    }  
   }
  }
 }


 public void mostrarEnConsola() {
  for( Palabra p : anagramas.keySet()) {
   System.out.print(p + "\t (" );
   for (Palabra p2 : anagramas.get(p)) {
    if(!p.equals(p2)) System.out.print(p2 + " ");
   }
   System.out.println(")");
  }
 }
}


Class Palabra:
import java.util.Arrays;


public class Palabra implements Comparable<Palabra>{
 private String cadena;
 private String signatura;
 
 public Palabra(String p) {
  cadena = p.toLowerCase();
  char [] s = p.toCharArray();
  Arrays.sort(s);
  signatura = new String(s);
 }
 
 public boolean esAnagrama(Palabra p) {
  return signatura.equals(p.signatura);
 }
 
 public boolean equals(Object p) {
 // boolean iguales = true;
  return cadena.equalsIgnoreCase(((Palabra) p).getPalabra());
 }
 
 public int hashCode() {
  return cadena.hashCode();
 }

 public String toString() {
  String std = new String(cadena /*+ " y su anagrama correspondiente " + signatura*/);
  return std;  
 }

 @Override
 public int compareTo(Palabra s) {
  // TODO Auto-generated method stub
  return cadena.compareToIgnoreCase(s.cadena);
 }
 public String getPalabra() {
  return cadena;
 }
 public String getSignatura() {
  return signatura;
 }
}


Class SatPalabra:
import java.util.Comparator;


public class SatPalabra implements Comparator<Palabra>{
 public int compare(Palabra arg0, Palabra arg1) {
  int ns;
  int aux = arg0.getPalabra().length() - arg1.getPalabra().length();
  if(aux<0) ns = -1;
  else if (aux> 0) ns = 1;
  else ns = arg0.compareTo(arg1);
  return ns;
 }

}

Bueno, ésta puede ser más pesada por el hecho de enterarse primero de lo que es un anagrama y, bueno, que tampoco es mucha diversión :p pero ánimo, que ya vereis que conforme avanzais se vuelve todo más ameno ;)

Saludos

domingo, 13 de abril de 2014

Ejercicios C++: procedimientos, funciones y recursividad (II)

¡Hola! Vuelvo con otra entrada de C++ para repasar tanto los procedimientos y funciones y el paso de parámetros a estos como la recursividad. Si os interesa practicar estos temas os recomiendo que además de ver esta entrada, os paséis por ésta  sobre procedimientos y ésta sobre recursividad publicadas hace unos días. Os dejo los ejercicios resueltos ;)

Escribe un programa que lea un número natural N por teclado y dibuje un triángulo de
asteriscos con base y altura N. Por ejemplo si N=5 debería dibujarse:

#include <iostream>
using namespace std;

void leerDatos(unsigned& x){
 int n;
 do{
  cout << "Introduce altura de la pirámide: ";
  cin >> n;
 }while( n < 1);
 x = n;
}

void dibujarFila(unsigned x, unsigned i){
 for(unsigned j = 1; j <= (x-i); j++){
  cout << " ";
 }
 for(unsigned j = 1; j<= i; j++){
  cout << "* ";
 }
 for(unsigned j = 1; j <= (x-i); j++){
  cout << " ";
 }
}

void dibujarPiramide (unsigned x){
 for(unsigned i = 1; i <= x; i++){
  dibujarFila(x, i);
  cout << endl;
 }
}

int main() {
 unsigned x;
 leerDatos(x);
 dibujarPiramide(x);
 return 0;
}

Escriba un programa que tome como entrada desde teclado dos números naturales (mayores
que cero) "N" e "i", e imprima en pantalla el dígito que ocupa la posición i-ésima del número
N. Si i es mayor que el número de dígitos de N, se escribirá en pantalla -1. Por ejemplo, para N
= 25064 e i = 2, el resultado es el dígito 6, y para i = 7, el resultado es -1.

#include<iostream>
#include <math.h>
using namespace std;

void introducirDatos(unsigned& N, unsigned& i){
 cout << "Introduce N  (>0) : ";
 cin >> N;
 cout << "Introduce i  (>0) : ";
 cin >> i;
}
int calcularDigito(unsigned N, unsigned i){
 int num;
 num = N /(pow( 10,(i-1)  ));
 if(num == 0){
  num = -1;
 }else{
  num = num%10;
 }
 return num;
}



int main() {
 unsigned N, i;
 cout << "Programa que imprime en pantalla el dígito que ocupa la posición i-ésima del número N."<< endl;
 introducirDatos(N, i);
 cout << "Resultado: " << calcularDigito(N, i);


 return 0;
}


Escribe un programa que acepte como entrada desde teclado un número natural mayor que cero
y dé como salida el resultado de sumar dos a dos los dígitos que aparecen en posiciones
simétricas respecto al dígito central dentro del número dado como entrada. Por ejemplo :
para el número : 2354869
la salida es: 2+9 = 11, 3 + 6 = 9, 5 + 8 = 13, 4
para el número : 6582
la salida es : 6 + 2 = 8, 5 + 8 = 13
#include <iostream>
using namespace std;

void introducirDatos(unsigned& N){
 cout << "Introduce N  (>0) : ";
 cin >> N;
}

unsigned longitudNumero(unsigned num){
 unsigned contador = 0;
 while(num!= 0){
  num = num/10;
  contador++;
 }
 return contador;
}
unsigned potencia(int a,int b) { //potencia(10, 3)
 unsigned resultado = 1;
 if(b == 1){
  resultado = a;
 } else if (b > 1){
  for(int i = 1; i <= b; i++){
   resultado = resultado * a;
  }
 }
 return resultado;
}

int calcularDigito(unsigned N, unsigned i){
 int num;
 num = N /(potencia( 10,(i-1)  ));
 if(num == 0){
  num = -1;
 }else{
  num = num%10;
 }
 return num;
}

void Sumar(unsigned N){
 unsigned longitud = longitudNumero(N);
 unsigned long2= longitud;

 unsigned suma;
 for(int i =1; i <= int(longitud/2); i++){
  suma = calcularDigito(N, i) + calcularDigito (N, long2);
  cout << calcularDigito (N, long2)<< "+" << calcularDigito(N, i)   <<"=" << suma << " ";
  long2 --;
 }
 if(longitud%2 != 0){
  cout << calcularDigito(N, unsigned(longitud/2)+1 );
 }
}




int main() {
 unsigned N;
 introducirDatos(N);
 Sumar(N);


 return 0;
}


Decimos que una sucesión a1,a2,...,an de enteros forma una montaña, si existe un h tal
que : 1 <= h <= n y además
a1 < ...ah-1 < ah > ah+1 > ...an
Definimos la longitud de una montaña como el número de enteros que la forman. Por ejemplo
la sucesión -7, -1, 6, 21, 15 es una montaña de longitud 5.
Definimos un valle de la misma forma que una montaña pero cambiando el signo de las
desigualdades de la definición anterior:
a1 > ...ah-1 > ah < ah+1 < ...an
Por ejemplo 24, 13, 6, 15, 50 sería un valle.
Dada una secuencia de enteros terminada en cero (0) que como mínimo contiene una montaña
y un valle (suponemos que la secuencia de enteros de entrada es una secuencia correcta de
montañas y valles), diseña un programa que calcule la longitud de la montaña y el valle más
largos.

#include<iostream>
using namespace std;


void leerNumero(int& mmontana, int& mvalle){
 int num, ant=0;
 int montana =0;
 int valle = 0;
 mmontana =0;
 mvalle =0;
 int antant=0;
 cout << "Introduce: "<<endl;
 cin >> num;
 while(num!= 0){
  if(num < ant && antant < ant){
   valle = 2;
  }else{
   valle++;
   if(mvalle < valle){
    mvalle = valle;
   }
  }
  if(num > ant && antant > ant){
   montana =1;

  }else{
   montana++;
   if(mmontana < montana){
    mmontana = montana;
   }
  }
  antant = ant;
  ant= num;
  cin >> num;
 }
}

int main() {
 int mmontana;
 int mvalle;
 leerNumero(mmontana, mvalle);
 cout <<"Mayor montaña: "<< (mmontana+1) << endl;
 cout << "Mayor valle: "<< mvalle;
 return 0;
}

El máximo común divisor (mcd) de dos números naturales p y q es el mayor entero d que
divide a ambos. Un algoritmo muy conocido para calcularlo es el de Euclides. Éste utiliza
dos variables, que contienen inicialmente a cada uno de los números, y trata de hacer que su
contenido sea el mismo. Para ello, irá restando la menor a la mayor hasta que ambas
contengan el mismo valor. En dicho momento, el valor obtenido en cualquiera de ellas es el
máximo común divisor de los dos números iniciales. Por ejemplo, si P = 18 y Q = 12, el
algoritmo hará que P y Q vayan tomando los siguientes valores:
Inicialmente P == 18 y Q == 12 (P > Q => P = P - Q)
Después P == 6 y Q == 12 (Q > P => Q = Q - P)
Después P == 6 y Q == 6 (P == Q => El mcd es 6)
Diseña el algoritmo anterior siguiendo un enfoque recursivo:
unsigned mcd(unsigned P, unsigned Q)
#include <iostream>
using namespace std;

unsigned mcd(unsigned P, unsigned Q){
 unsigned res;
 if(P == Q){
  res = P;
 }else{
  if(P > Q){
   res = mcd(P - Q, Q);
  }else{
   res = mcd(P, Q - P );
  }
 }
 return res;
}

int main() {
 unsigned P, Q;
 cout << "Máximo común divisor. " << endl; // prints !!!Hello World!!!
 cout << "Introduce dos naturales: ";
 cin >> P >> Q;
 cout << "El mcd es "<< mcd(P,Q);
 return 0;
}

Diseña un procedimiento recursivo que lea una secuencia de caracteres de longitud arbitraria
terminada en un punto, y la imprima en orden inverso. El procedimiento no tiene parámetros.
#include <iostream>
using namespace std;

void invertirTexto(){
 char a;
 cin.get(a);
 if(a == '.'){

 }else{
  invertirTexto();
  cout << a;
 }
}

int main() {
 cout << "Introduce texto a invertir terminado en punto." << endl; // prints !!!Hello World!!
 invertirTexto();
 return 0;
}

Y hasta aquí la entrada de hoy ;)

viernes, 11 de abril de 2014

Práctica Llaves POO

Buenas gente. Aquí os traigo otra práctica de Java de primer año. Esta es la (según tengo apuntado) número 6. prLlaves. Aquí os dejo para descargar el enunciado y el test.

Os copio parte del enunciado para que veais más o menos de que va. No lo puedo copiar entero porque el pdf está mal creado y no me deja T_T
Una llave está formada por un número determinado de dientes, cada uno de una altura (una llave se representará como una lista de enteros). 
Inicialmente las llaves tienen sus dientes sin limar a una altura de 10mm, obteniéndose el perfil deseado limando cada uno de estos dientes una altura ni (entre 0 y 10), de forma que la altura final de cada uno de estos dientes sea 10 - ni.
Aquí tenéis la clase test para probarla:

public class TestLlaves {
 public static void main(String[] args) {
  try {
   Llave l = new Llave(3);
   Cerradura c = new Cerradura(3);
   Cerradura cc = new Cerradura(3);
   Cerradura ccc = new Cerradura(2);
   l.limarDiente(2, 4);
   l.limarDiente(1, 3);
   l.limarDiente(0, 8);
   System.out.println("Llave " + l);
   c.agregarMarca(0, 8);
   c.agregarMarca(1, 3);
   c.agregarMarca(2, 4);
   System.out.println("Cerradura 1 " + c);
   cc.agregarMarca(0, 3);
   cc.agregarMarca(2, 9);
   cc.agregarMarca(0, 8);
   cc.agregarMarca(1, 3);
   cc.agregarMarca(2, 4);
   System.out.println("Cerradura 2 " + cc);
   ccc.agregarMarca(0, 2);
   ccc.agregarMarca(0, 5);
   ccc.agregarMarca(1, 9);
   System.out.println("Cerradura 3 " + ccc);
   System.out.println("¿Encaja la llave con la cerradura 1? "
     + c.abrir(l));
   System.out.println("¿Encaja la llave con la cerradura 2? "
     + cc.abrir(l));
   System.out.println("¿Encaja la llave con la cerradura 3? "
     + ccc.abrir(l));
  } catch (LyCException e) {
   System.out.println("Operación incorrecta: " + e.getMessage());
  }
 }
}

Y aquí teneis los resultados: - La class LyCException

public class LyCException extends Exception{
 private static final long serialVersionUID = 1L;
 //Si fuera una excepcion no comprobada se usaria extends RunTimeException.
  public LyCException() {
   super();
  }
  public LyCException(String e) {
   super(e);
  }
 }

La class Llave

import java.util.*;


public class Llave {
 static final int MAX_ALTURA_DIENTE = 10;
 private List<Integer> dientes;
 
 public Llave(int numDientes) {
  dientes = new ArrayList<Integer>(numDientes);
  for(int i = 0; i<numDientes; i++) {
   dientes.add(MAX_ALTURA_DIENTE);
  }
 }
 public void limarDiente(int diente, int altura) throws LyCException{
  if(diente >=dientes.size()) throw new LyCException("No existe ningún diente en esa posición");
  int alturaAntigua = dientes.get(diente);
  if(altura> alturaAntigua) throw new LyCException("No puedes limarlo tanto");
  dientes.set(diente, alturaAntigua - altura);
 }
 public int obtenerAltura(int diente) {
  return dientes.get(diente);
 }
 public int numeroDeDientes() {
  return dientes.size();  
 }
 public String toString() {
  return dientes.toString();
 }
}

Y por último la class Cerradura

import java.util.*;

public class Cerradura {
 static final int MAX_MARCAS_POR_ANCLAJE = 4;
 private List<Set<Integer>> anclajes;
 
 public Cerradura(int numAnclajes) {
  anclajes = new ArrayList<Set<Integer>>(numAnclajes);
  for(int i = 0; i< numAnclajes; i++) {
   anclajes.add(new HashSet<Integer>(MAX_MARCAS_POR_ANCLAJE));
  }
 }
 public void agregarMarca(int anclaje, int marca) throws LyCException{  //.................poner throws
  if (anclajes.get(anclaje).size()>=MAX_MARCAS_POR_ANCLAJE) throw new LyCException("Máximo de marcas excedido en anclaje");
  if(anclajes.get(anclaje).isEmpty()) anclajes.get(anclaje).add(marca);
  else {anclajes.get(anclaje).add(marca) ;}
 }
 public boolean abrir(Llave llave) {
  boolean abierto = false;
  for (int i = 0; i<llave.numeroDeDientes(); i++) {
   if(llave.numeroDeDientes()<=anclajes.size()){
    abierto = encajaDienteAnclaje(llave.obtenerAltura(i), anclajes.get(i));
   }
  }
  return abierto;
 }
 
 static boolean encajaDienteAnclaje(int altura, Set<Integer> anclaje) {
  boolean encaja = false;
  for (int i : anclaje) {
   if(10 - altura == i) encaja = true;
  }
  return encaja;
 }
 
 public String toString(){
  /*String std = "{ ";
  for(Set<Integer> entero : anclajes) {
   std = std + "[";
   for(int n: entero) {
    std = std + " " + n ;
   }
   std = std + " ]";
  }*/
  return anclajes.toString();//std + "}";
  
 }
}
 

Bueno, espero que todas estas entradas os estén sirviendo de algo ;) Si teneis alguna pregunta ya sabeis, comentadla ;)

Saludos ;)

miércoles, 9 de abril de 2014

Ejercicios C++: recursividad

Os dejo unos ejercicios sencillitos de C++ con recursividad que sirven sobretodo para enterderla.

Implementa una función recursiva que calcule la suma de los n primeros números naturales. La cabecera sería la siguiente:
unsigned sumanaturales(unsigned n)
donde el parámetro n es el número de naturales a sumar.

#include <iostream>
using namespace std;

unsigned sumanaturales(unsigned n){
 unsigned suma;
 if(n == 0){
  suma = 0;
 }else{
  suma = n + sumanaturales(n-1);
 }
 return suma;
}

int main() {
 unsigned n;
 cout << "Suma de los n primeros números naturales." << endl;
 cout << "Introduce n: ";
 cin >> n;
 cout << "Suma = " << sumanaturales(n);
 return 0;
}


El valor de la función potencia x^n, se puede definir recursivamente del modo siguiente:
x^n =1                si n=0
x^n =x*x^(n-1)    si n>=1
Implementa una función potencia que calcule recursivamente el valor de xn con la siguiente cabecera:
unsigned potencia(unsigned x, unsigned n)
#include <iostream>
using namespace std;

void leerDatos(unsigned& x, unsigned& n){
 cout << "Introduce x: ";
 cin >> x;
 cout << "Introduce n: ";
 cin >> n;
}

unsigned potencia(unsigned x, unsigned n){
 unsigned pot;
 if(n == 0){
  pot = 1;
 }else{
  pot = x * potencia(x, n-1);
 }
 return pot;
}

int main() {
 unsigned x, n;
 cout << "Programa que calcula una potencia x^n" << endl; 
 leerDatos(x, n);
 cout << "El resultado es "<<potencia(x, n);
 return 0;
}

Implementa una función recursiva que calcule el producto de dos número naturales x e y. La cabecera sería la siguiente:
unsigned producto(unsigned x, unsigned y)
A la hora de diseñar la solución ten en cuenta que los únicos operadores aritméticos que puedes usar son la suma y la resta.

#include  <iostream>
using namespace std;

void leerDatos(unsigned& x, unsigned& y){
 cout << "Introduce x: ";
 cin >> x;
 cout << "Introduce y: ";
 cin >> y;
}

unsigned producto(unsigned x, unsigned y){
 unsigned prod;
 if(y == 0){
  prod = 0;
 }else{
  prod = x + producto(x, y-1);
 }
 return prod;
}

int main() {
 unsigned x, y;
 cout << "Producto de dos naturales. " << endl; // prints !!!Hello World!!!
 leerDatos(x,y);
 cout << x << " · "<< y << " = " << producto(x, y);
 return 0;
}
Implementa un procedimiento recursivo que imprima los dígitos de un número natural n en orden inverso. Por ejemplo, para n=675 la salida debería ser 576. La cabecera sería la siguiente:
void inverso (unsigned n)

#include <iostream>
using namespace std;

unsigned leerDato(){
 unsigned res;
 cout << "Introduce número: ";
 cin >> res;
 return res;
}


void inverso (unsigned n){
 if(n == 0){
  cout << " ";
 }else{
  cout << n%10;
  inverso(unsigned(n/10));
 }
}
int main() {

 cout << "Invertir un número." << endl; // prints !!!Hello World!!!
 unsigned n =leerDato();
 inverso(n);
 return 0;
}

Implementa una función recursiva que devuelva true si el número que se le pasa como parámetro es primo y false en caso contrario. La cabecera de la función sería la siguiente:
bool esPrimo (unsigned num, unsigned divisor)
en el primer parámetro le habríamos de pasar el número, y el segundo parámetro es un número para que hay que comprobar si es o no divisor. Inicialmente (en la llamada a la función desde main) el valor de ese parámetro es 2.
#include <iostream>
using namespace std;

unsigned leerDato(){
 unsigned res;
 cout << "Introduce número: ";
 cin >> res;
 return res;
}

bool esPrimo (unsigned num, unsigned divisor){
 if(divisor < num){

   if(num%divisor != 0) {
     return esPrimo(num, divisor+1); // Si no encontramos un divisor, seguimos probando
   } else {
     return false;  // Si encontramos un divisor de num, devolvemos false
   }
 }
 return true; //Devolvemos true si el divisor es mayor que el numero

}
int main() {
 unsigned n;
 bool b;
 cout << "Programa para saber si un número es o no primo." << endl; // prints !!!Hello World!!!
 n = leerDato();
 b= esPrimo(n, 2);
 if(b){
  cout << "El número es primo.";
 }else{
  cout << "El número no es primo.";
 }
 return 0;
}
Implementa un procedimiento recursivo al que se le pase como parámetro un número n en
base 10 (decimal), e imprima su valor en base 2 (binario). La cabecera sería la siguiente:
void decimalAbinario (unsigned n)
Por ejemplo para n=23, el procedimiento debería imprimir 10111.
#include <iostream>
using namespace std;

unsigned leerDato(){
 unsigned res;
 cout << "Introduce número: ";
 cin >> res;
 return res;
}


void decimalAbinario (unsigned n){
 if(n != 0){
  decimalAbinario(n/2);
  cout << n%2;
 }
}

int main() {
 unsigned n;
 cout << "Programa que pasa de decimal a binario." << endl; // prints !!!Hello World!!!
 n = leerDato();
 cout << "Su expresión en decimal es ";
 decimalAbinario(n);
 return 0;
}