Espirales. Graficar Espiral Logarítmica.

La espiral logarítmica es una curva matemática que se genera a partir de la relación logarítmica entre su distancia radial y su ángulo polar.


Código java (LogarithmicSpiral.java):

package logarithmicspiral;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import javax.swing.JComponent;
import javax.swing.JFrame;

public class LogarithmicSpiral extends JComponent {

@Override
  protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2d = (Graphics2D) g;

    int width = getWidth();
    int height = getHeight();

    g2d.translate(width / 2, height / 2);
    g2d.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);

    double theta = 0.5;
    double a = 1;
    double b = 0.12;

    int x1 = 0;
    int y1 = 0;

    g2d.setColor(Color.BLUE);

    for (int i = 0; i <= 500; i++) {
      double r = a * Math.exp(b * theta);
      int x2 = (int) (r * Math.cos(theta));
      int y2 = (int) (r * Math.sin(theta));

      g2d.setStroke(new BasicStroke((float) i / 100));
      g2d.drawLine(x1, y1, x2, y2);

      x1 = x2;
      y1 = y2;

      theta += 0.1;
    }
  }

  public static void main(String[] args) {
    JFrame frame = new JFrame();
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.add(new LogarithmicSpiral());
    frame.setSize(800, 800);
    frame.setLocationRelativeTo(null);
    frame.setVisible(true);
  }

}


Resultado:

Permutaciones. Algoritmo lexicográfico.

El algoritmo lexicográfico es un algoritmo de generación de permutaciones que genera todas las permutaciones de un conjunto de elementos en orden lexicográfico. Es similar al algoritmo de Heap, pero en lugar de usar una estructura de datos específica, utiliza una técnica de backtracking para generar las permutaciones. Tiene una complejidad temporal de O(n! * n).


Código Java (LexicographicPermutation.java):

import java.util.Arrays;

public class LexicographicPermutation {
    private static int[] elements = {1, 2, 3, 4, 5, 6, 7, 8};
    private static boolean[] used = new boolean[elements.length];

    public static void main(String[] args) {
        lexicographicPermutation(new int[elements.length], 0);
    }

    private static void lexicographicPermutation(int[] permutation, int index) {
        if (index == elements.length) {
            System.out.println(Arrays.toString(permutation));
            return;
        }

        for (int i = 0; i < elements.length; i++) {
            if (!used[i]) {
                used[i] = true;
                permutation[index] = elements[i];
                lexicographicPermutation(permutation, index + 1);
                used[i] = false;
            }
        }
    }
}


Resultado:

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]

Permutaciones. Algoritmo de Heap.

El algoritmo de Heap es un algoritmo de generación de permutaciones que utiliza una estructura de datos conocida como heap. La idea es generar todas las permutaciones de un conjunto de elementos en orden lexicográfico. Tiene una complejidad temporal de O(n!).


Código Java (HeapPermutation.java):

import java.util.Arrays;

public class HeapPermutation {
    private static int[] elements = {1, 2, 3, 4};

    public static void main(String[] args) {
        heapPermutation(elements.length);
    }

    private static void heapPermutation(int size) {
        if (size == 1) {
            System.out.println(Arrays.toString(elements));
            return;
        }

        for (int i = 0; i < size; i++) {
            heapPermutation(size - 1);

            if (size % 2 == 1) {
                int temp = elements[0];
                elements[0] = elements[size - 1];
                elements[size - 1] = temp;
            } else {
                int temp = elements[i];
                elements[i] = elements[size - 1];
                elements[size - 1] = temp;
            }
        }
    }
}


Resultado:

[1, 2, 3, 4]
[2, 1, 3, 4]
[3, 1, 2, 4]
[1, 3, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[4, 2, 3, 1]
[2, 4, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]
[2, 3, 4, 1]
[3, 2, 4, 1]
[4, 1, 3, 2]
[1, 4, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[1, 3, 4, 2]
[3, 1, 4, 2]
[4, 1, 2, 3]
[1, 4, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 2, 4, 3]
[2, 1, 4, 3]

Conversión de Infijo a Postfijo usando pilas (v.4). Mejorar formato de entrada.

Se incorpora mejoras en la función de limpieza y formateo que permite ajustar la calidad y la precisión de la expresión de entrada, eliminando cualquier elemento innecesario y corrigiendo posibles errores de formateo.


Código Java (InfijoPostfijo.java):

package infijopostfijo;

import java.util.Scanner;
import java.util.Stack;

public class InfijoPostfijo {

    public static void main(String[] args) {

        // Declaración de las pilas
        Stack<String> E = new Stack<>(); // Pila entrada
        Stack<String> P = new Stack<>(); // Pila temporal para operadores
        Stack<String> S = new Stack<>(); // Pila salida

        // Entrada de datos
        System.out.println("> Ingresa expresión algebraica a convertir:");
        Scanner leer = new Scanner(System.in);

        // Pasar expresión algebraica a la Pila de entrada (E)
        String[] arrayInfix = formato(leer.nextLine()).split(" ");
        for (int i = arrayInfix.length - 1; i >= 0; i--) {
            E.push(arrayInfix[i]);
        }

        // Conversor Infijo a Postfijo
        while (!E.isEmpty()) {
            switch (prioridad(E.peek())) {
                case 1 ->
                    P.push(E.pop());
                case 2 -> {
                    while (!P.peek().equals("(")) {
                        S.push(P.pop());
                    }
                    P.pop();
                    E.pop();
                }
                case 3, 4 -> {
                    while (prioridad(P.peek()) >= prioridad(E.peek())) {
                        S.push(P.pop());
                    }
                    P.push(E.pop());
                }
                case 5 ->
                    P.push(E.pop());
                default ->
                    S.push(E.pop());
            }
        }

        // Mostrar resultado:
        System.out.println("> Expresión en notación Postfija:\n" + S.toString().replaceAll("[\\]\\[,]", ""));

    }

    // Prioridad de los operadores
    private static int prioridad(String op) {
        return switch (op) {
            case "^" -> 5;
            case "*", "/" -> 4;
            case "+", "-" -> 3;
            case ")" -> 2;
            case "(" -> 1;
            default -> 99;
        };
    }

    // Formato expresión algebraica
    private static String formato(String expr) {
        expr = expr.trim();
        expr = expr.charAt(0) == '-' ? "0-" + expr.substring(1) : expr;
        expr = expr.replaceAll("\\(-(\\d)", "(0-$1");
        expr = expr.replaceAll("(\\d)\\(", "$1*(");
        expr = expr.replaceAll("\\)(\\d)", ")*$1");
        expr = expr.replaceAll("([\\+|\\-|\\*|\\/|\\(|\\)|\\^|])", " $1 ");
        expr = expr.replaceAll("\\s+", " ");
        return "( " + expr + " )";
    }

}


Resultado:

run:
> Ingresa expresión algebraica a convertir:
-4(56-3+5)/2-(45+34)+(-23*(-52)6+2)-1   
> Expresión en notación Postfija:
0 4 56 3 - 5 + * 2 / - 45 34 + - 0 23 0 52 - * 6 * - 2 + + 1 -
BUILD SUCCESSFUL (total time: 2 seconds)

Problema del viajante de comercio TSP (IV). Cálculo mediante método Vecino Cercano.

El algoritmo de vecino más cercano funciona de la siguiente manera:

    .Se elige una ciudad de inicio.
    .Se selecciona la ciudad más cercana a la ciudad actual, y se añade al camino.
    .Se repite el proceso anterior hasta que se haya visitado todas las ciudades.
    .Se regresa al lugar de origen para completar el ciclo.

El algoritmo de vecino más cercano es una forma rápida y sencilla de encontrar una solución para el TSP, pero no garantiza que sea la solución óptima. En general, el algoritmo tiende a dar buenos resultados para problemas pequeños, pero puede no ser tan efectivo para problemas más grandes.


Código (TSP_MainVecinoCercano.java):

package tsp_mainvecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSP_MainVecinoCercano {

    public static void main(String[] args) {

        int n = 12;
        int[][] distances = new int[n][n];

        // Generar distancias aleatorias
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) {
                    distances[i][j] = 0;
                } else {
                    distances[i][j] = (int) (Math.random() * 999 + 1);
                    distances[j][i] = distances[i][j];
                }
            }
        }

        // Imprimir matriz de distancias
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%5d ", distances[i][j]);
            }
            System.out.println();
        }

        TSP_VecinoCercano tsp = new TSP_VecinoCercano(distances);
        List<Integer> path = tsp.findOptimalPath();

        // Pone nombre a los nodos siguiendo la secuencia del abcedario
        List<String> nodeNames = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char letter = (char) ('A' + i);
            nodeNames.add(String.valueOf(letter));
        }

        // Imprimir ruta y distancia recorrida
        System.out.println("\n> Ruta:");
        path.forEach(node -> {
            System.out.print(nodeNames.get(node) + " ");
        });
        System.out.println("\n> La distancia total recorrida es:");
        int totalDistance = 0;
        for (int i = 0; i < path.size() - 1; i++) {
            int node1 = path.get(i);
            int node2 = path.get(i + 1);
            totalDistance += distances[node1][node2];
        }
        System.out.println(totalDistance);
    }

}


Código 2 (TSP_VecinoCercano.java):

package tsp_mainvecinocercano;

import java.util.ArrayList;
import java.util.List;

public class TSP_VecinoCercano {

    private final int[][] distances;

    public TSP_VecinoCercano(int[][] distances) {
        this.distances = distances;
    }

    public List<Integer> findOptimalPath() {
        List<Integer> path = new ArrayList<>();
        path.add(0); // Empezamos en el nodo 0

        int currentNode = 0;
        for (int i = 0; i < distances.length - 1; i++) {
            int minDistance = Integer.MAX_VALUE;
            int nextNode = -1;
            for (int j = 0; j < distances.length; j++) {
                if (distances[currentNode][j] < minDistance && !path.contains(j)) {
                    minDistance = distances[currentNode][j];
                    nextNode = j;
                }
            }
            path.add(nextNode);
            currentNode = nextNode;
        }

        // Volvemos al nodo de origen
        path.add(0);

        return path;
    }

}


Resultado:

run:
    0   138   758   967   823   983   914   935   369   522   282   990
  138     0   997   828   997   770   963   398   590   668   312   716
  758   997     0   849   945   774   952    47   859    52   438   582
  967   828   849     0   556   800   501   589   928   149   409   912
  823   997   945   556     0   856   172   696   375   240   335   887
  983   770   774   800   856     0   213    39   549   694   102    65
  914   963   952   501   172   213     0   164    79   243   646   907
  935   398    47   589   696    39   164     0   205   571   392   504
  369   590   859   928   375   549    79   205     0   167   253   203
  522   668    52   149   240   694   243   571   167     0   475   578
  282   312   438   409   335   102   646   392   253   475     0   314
  990   716   582   912   887    65   907   504   203   578   314     0

> Ruta:
A B K F H C J D G I L E A
> La distancia total recorrida es:
3332
BUILD SUCCESSFUL (total time: 0 seconds)

Conversión de Infijo a Postfijo usando pilas (v.3). Añadir operador de potencia ^.

En esta nueva versión añadimos el operador de potencia ^ que faltaba.
Hay que tener en cuenta que el operador de potencia ^ tiene una prioridad muy alta en las expresiones matemáticas, lo que significa que se evalúa antes que los otros operadores.


Código Java (InfijoPostfijo,java):

package infijopostfijo;

import java.util.Scanner;
import java.util.Stack;

public class InfijoPostfijo {

    public static void main(String[] args) {

        // Declaración de las pilas
        Stack<String> E = new Stack<>(); // Pila entrada
        Stack<String> P = new Stack<>(); // Pila temporal para operadores
        Stack<String> S = new Stack<>(); // Pila salida

        // Entrada de datos
        System.out.println("> Ingresa expresión algebraica a convertir:");
        Scanner leer = new Scanner(System.in);

        // Pasar expresión algebraica a la Pila de entrada (E)
        String[] arrayInfix = formato(leer.nextLine()).split(" ");
        for (int i = arrayInfix.length - 1; i >= 0; i--) {
            E.push(arrayInfix[i]);
        }

        // Conversor Infijo a Postfijo
        while (!E.isEmpty()) {
            switch (prioridad(E.peek())) {
                case 1 -> P.push(E.pop());
                case 2 -> {
                    while (!P.peek().equals("(")) {
                        S.push(P.pop());
                    }
                    P.pop();
                    E.pop();
                }
                case 3, 4 -> {
                    while (prioridad(P.peek()) >= prioridad(E.peek())) {
                        S.push(P.pop());
                    }
                    P.push(E.pop());
                }                
                case 5 -> P.push(E.pop());                
                default -> S.push(E.pop());
            }
        }

        // Mostrar resultado:
        System.out.println("> Resultado en notación postfija:\n" + S.toString().replaceAll("[\\]\\[,]", ""));
        
    }

    // Prioridad de los operadores
    private static int prioridad(String op) {
        return switch (op) {
            case "^" -> 5;
            case "*", "/" -> 4;
            case "+", "-" -> 3;
            case ")" -> 2;
            case "(" -> 1;
            default -> 99;
        };
    }

    // Formato expresión algebraica
    private static String formato(String s) {
        return "( " + s.replaceAll("([\\+|\\-|\\*|\\/|\\(|\\)|\\^|])", " $1 ").replaceAll("\\s+", " ") + " )";
    }
}


Resultado:

run:
> Ingresa expresión algebraica a convertir:
(((34/2)+(43-5-32))^2*2+45-3+(34*2)/5)-1
> Resultado en notación postfija:
 34 2 / 43 5 - 32 - + 2 ^ 2 * 45 + 3 - 34 2 * 5 / + 1 -
BUILD SUCCESSFUL (total time: 3 seconds)

Conversión de Infijo a Postfijo usando pilas (v.2)

Código java (InfijoPostfijo.java):

package infijopostfijo;

import java.util.Scanner;
import java.util.Stack;

public class InfijoPostfijo {

    public static void main(String[] args) {

        // Declaración de las pilas
        Stack<String> E = new Stack<>(); // Pila entrada
        Stack<String> P = new Stack<>(); // Pila temporal para operadores
        Stack<String> S = new Stack<>(); // Pila salida

        // Entrada de datos
        System.out.println("> Ingresa una expresión algebraica: ");
        Scanner leer = new Scanner(System.in);

        // Pasar expresión algebraica a la Pila de entrada (E)
        String[] arrayInfix = formato(leer.nextLine()).split(" ");
        for (int i = arrayInfix.length - 1; i >= 0; i--) {
            E.push(arrayInfix[i]);
        }

        // Conversor Infijo a Postfijo
        while (!E.isEmpty()) {
            switch (prioridad(E.peek())) {
                case 1 -> P.push(E.pop());
                case 2 -> {
                    while (!P.peek().equals("(")) {
                        S.push(P.pop());
                    }
                    P.pop();
                    E.pop();
                }
                case 3, 4 -> {
                    while (prioridad(P.peek()) >= prioridad(E.peek())) {
                        S.push(P.pop());
                    }
                    P.push(E.pop());
                }                
                default -> S.push(E.pop());
            }
        }

        // Mostrar resultado:
        System.out.println("> Expresión Postfija:\n" + S.toString().replaceAll("[\\]\\[,]", ""));

    }

    // Prioridad de los operadores
    private static int prioridad(String op) {
        return switch (op) {
            case "*", "/" -> 4;
            case "+", "-" -> 3;
            case ")" -> 2;
            case "(" -> 1;
            default -> 99;
        };
    }

    // Formato expresión algebraica
    private static String formato(String s) {
        return "( " + s.replaceAll("([\\+|\\-|\\*|\\/|\\(|\\)])", " $1 ").replaceAll("\\s+", " ") + " )";
    }
}


Resultado:

run:
> Ingresa una expresión algebraica:
2*(23+6)-1
> Expresión Postfija:
2 23 6 + * 1 -
BUILD SUCCESSFUL (total time: 7 seconds)

Validación DNI de España.

Código java (AI_DniValidator.java):

package ai_dnivalidator;

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class AI_DniValidator {

    private static final String DNI_PATTERN = "^[0-9]{8}[A-Z]$";

    public static boolean isValid(String dni) {
        Pattern pattern = Pattern.compile(DNI_PATTERN);
        Matcher matcher = pattern.matcher(dni);
        if (!matcher.matches()) {
            return false;
        }
        String letras = "TRWAGMYFPDXBNJZSQVHLCKE";
        int modulo = Integer.parseInt(dni.substring(0, 8)) % 23;
        char letraEsperada = letras.charAt(modulo);
        char letraObtenida = dni.charAt(8);
        return letraEsperada == letraObtenida;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Ingresa un DNI: ");
        String dni = scanner.nextLine().toUpperCase();
        System.out.println(isValid(dni) ? "DNI válido" : "DNI inválido");
    }

}


Resultado:

run:
Ingresa un DNI: 12345678z
DNI válido
BUILD SUCCESSFUL (total time: 5 seconds)