Ejercicio 3

El siguiente ejercicio fue propuesto en la asignatura Sistémico I del grado Técnico en Sistemas de la Universidad Politécnico Jaime Izasa Cadavid. El problema original dice:

Ejército Rodeado por Fuerza enemiga

Problema
Un ejército se encuentra rodeado por una gran fuerza enemiga. La única forma de salvarse es que un soldado escape a buscar ayuda en el único caballo disponible.

Se utiliza el siguiente método para elegir cuál soldado escapa a pedir ayuda. Los soldados forman un círculo. Se elige un soldado inicial y un número n. Se cuenta n a partir del siguiente soldado al soldado inicial. El enésimo soldado sale del círculo. El siguiente soldado desde donde se empieza a contar es el siguiente soldado al que salió. Se vuelve a contar n a partir del siguiente soldado de éste soldado (el siguiente soldado al que salió). Este enésimo soldado también sale del círculo. Se repite este proceso hasta que quede un sólo soldado en el círculo. Este soldado es el que escapa. El conteo se hace en el sentido de las manecillas del reloj.

Usted debe implementar la solución a este problema usando una lista doble.

Entrada
3 Juan Jose Pedro Jose 2

Salida
Sale Juan
Sale Jose
Escapa Pedro

El primer número de la entrada, 3, dice cuántos soldados forman el círculo. El círculo está formado por Juan, Jose y Pedro en el sentido de las manecillas del reloj. El último nombre de la entrada, para este caso Jose, es el nombre del soldado desde donde se inicia el conteo. El número que aparece al final de la entrada, en este caso 2, es el número de veces que se cuenta.

Solución
Se implementan 3 clases: Node, Circular_Link y Test_Circular_Link (contiene main). Dentro de la clase Circular_Link se implementan varios métodos, siendo relevante para esta actividad el método delete_n(int n, String name). Dicho método busca la posición del nombre a partir del cual debe empezar la cuenta para determinar quien sale del circulo. Observar que el método empleado para adicionar elementos al Circular_Link se llama add_Front(String name), luego, si quiero introducir los nombres: Juan, Jose, Pedro; debo hacerlo de forma contraria: Pedro, Jose, Juan.

Clase Node

package circularlink;

public class Node {
    private final String name;
    Node next;
    Node previous;
    
    public Node(String name){
        this.name = name;
        this.next = null;
        this.previous = null;
    }
    
    public Node(Node previous, String name, Node next){
        this.previous = previous;
        this.name = name;
        this.next = next;
    }
    
    public String GetData(){
        return this.name;
    }
}

Clase Circular Link

package circularlink;


public class CircularLink {
    private Node head, tail;
    private int number_participants;
    private int count;
    private int size;
    
    public CircularLink(){
        size = 0;
        head = null;
        tail = null;
    }
    
    public void addFront(String name){
        Node current;
        if(head == null){
            head = new Node(null,name,null);
            tail = head;
        }else{
            current = new Node(null,name,head);
            head.previous = current;
            head = current;
        }
            tail.next = head;
            head.previous = tail;
        size++;
    }
    
    public Node get_position(Node mynode, String name){
        int num_person = 0;
        while((num_person < size) || !(mynode.GetData().equals(name))){
           if(num_person > size){
               System.err.println("Incorrect name");
               break;
           }
           mynode = mynode.next;
           num_person++;
        }
        return mynode;
    }
    
    public void delete_n(int n, String name){
        if(n < 0){System.err.println("Negative element.");return;}
        if(n > size){System.err.println("Element doesnt exists.");return;}
        // Wich is zero ??
        
        Node start = get_position(head,name);
        while(start.next != start){
            for (int i = 0; i < n; i++) {
            start = start.next;
            }
            if(start.next != start){
                System.out.println("Sale :" + start.GetData());
                start.next.previous = start.previous;
                start.previous.next = start.next;
                start = start.next;
                size--;
            }
            if(size == 1){
                System.out.println("Escapa: " + start.GetData());
            }
            
        }
    }
    
    public int Get_Size(){
        return size;
    }
}

Clase Test_Circular_Link

package circularlink;

import java.util.Scanner;

public class Test_Circular_Link {
    Scanner read = new Scanner(System.in);
    
    public void Process(){
        CircularLink CLink = new CircularLink();
        System.out.printf("%20s %n","Welcome, define data input: ");
        int num_elements = read.nextInt();
        int i = 0;
        while(i < num_elements){
            CLink.addFront(read.next());
            i++;
        }
        String start = read.next();
        int count = read.nextInt();
        CLink.delete_n(count, start);
    }
    
    public static void main(String arg[]){
        Test_Circular_Link TCL = new Test_Circular_Link();
        TCL.Process();
    }
    
}

Code Formatted by ToGoTutor

Para obtener los mismos resultados planteados en el apartado Salida, los datos que se deben introducir son: 3 Pedro Jose Juan Jose 2. Esto se debe al método empleado para introducir elementos al Link Circular es addFront(..).