Programming
T04-1D-A03. Rotar N posiciones un array
Enunciado
Escribe un programa en Java que desplace de manera circular los elementos de un array de enteros, a la izquierda o a la derecha, el número de posiciones que se le diga. Un desplazamiento circular quiere decir que los elementos que salen por un lado del array, entran por el otro.
Ejemplo:
- Dado el array de enteros {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, desplazarlo 3 posiciones a la derecha, daría el siguiente resultado: {8, 9, 10, 1, 2, 3, 4, 5, 6, 7}
- Dado el array de enteros {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, desplazarlo 4 posiciones a la izquierda, daría el siguiente resultado: {5, 6, 7, 8, 9, 10, 1, 2, 3, 4}
ENTRADA
La entrada comienza con un número indicando cuántos casos de prueba habrá que procesar.
Cada uno de los casos estará formado por:
- Una primera línea con el número L de elementos del array, donde L > 0
- Una segunda con los L elementos de dicho array separados por un espacio.
- Una tercera línea con el número N de posiciones que hay que desplazar el array, un espacio, y una D o una I, para indicar si el desplazamiento es a derecha o a izquierda.
SALIDA
Por cada caso de prueba, el programa escribirá el contenido del array una vez realizado el desplazamiento pedido.
RESTRICCIONES
Se resolverá el problema haciendo uso de la siguiente descomposición funcional:
- Una función que reciba un array de enteros y un número entero positivo como argumento y realizará la rotación de dicho array N posiciones a la derecha. La función lanzará la excepción IllegalArgumentException en caso de que el número recibido como argumento sea un número negativo.
- Una función que reciba un array de enteros y un número entero positivo como argumento y realizará la rotación de dicho array N posiciones a la izquierda. La función lanzará la excepción IllegalArgumentException en caso de que el número recibido como argumento sea un número negativo.
El programa principal, para cada caso, imprimirá el resultado de rotar la cadena las N posiciones a derecha o a izquierda.
OPTIMIZACIÓN ALGORÍTMICA
JuezLTI no lo va a tener en cuenta a la hora de dar como correcto o no el ejercicio, pero vamos a intentar programar de la manera más óptima posible, reduciendo al máximo el tiempo de ejecución. Para ello, debes observar y plasmar en tu algoritmo, esta circunstancia:
- Rotar las mismas posiciones que el tamaño del array, o un múltiplo del tamaño del array, es dejar el array como está
- Rotar el tamaño del array + 1, o un múltiplo del tamaño del array + 1, es como rotar el array 1 posición.
- Rotar el tamaño del array + 2, o un múltiplo del tamaño del array + 2, es como rotar el array 2 posiciones.
- Rotar el tamaño del array + N, o un múltiplo del tamaño del array + N, es como rotar el array N posiciones.
Es decir,
- Rotar 5 posiciones, 10 posiciones, 15 posiciones, 20 posiciones, etc., un array de tamaño 5 es dejarlo como está (es como rotar 0 posiciones).
- Rotar 6 posiciones, 11 posiciones, 16 posiciones, 21 posiciones, etc., un array de tamaño 5 es dejarlo como rotarlo 1 posición
- Rotar 7 posiciones, 12 posiciones, 17 posiciones, 22 posiciones, etc., un array de tamaño 5 es dejarlo como rotarlo 2 posiciones
¿Qué operación matemática es la que me da esta relación entre las rotaciones equivalentes?
Solución
import java.util.Scanner;
/**
*
* @author AulaVirtual
*/
public class RotarN {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Scanner sc = new Scanner(System.in);
int numCasos = 0;
int arraySize;
int[] array;
int posiciones;
char direccion;
numCasos = sc.nextInt();
for (int i = 1; i <= numCasos; i++) {
arraySize = sc.nextInt();
array = new int[arraySize];
for (int j = 0; j < array.length; j++) {
array[j] = sc.nextInt();
}
posiciones = sc.nextInt();
direccion = sc.next().charAt(0);
if (direccion == 'D') {
try {
rotarDerechaN(array, posiciones);
} catch (IllegalArgumentException ex) {
System.out.println("Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array");
}
} else if (direccion == 'I') {
try {
rotarIzquierdaN(array, posiciones);
} catch (IllegalArgumentException ex) {
System.out.println("Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array");
}
}
for (int num:array){
System.out.print(num + " ");
}
System.out.println();
}
}
public static void rotarDerechaN(int[] array, int numPosiciones) {
int auxiliar;
if (numPosiciones < 0) {
throw new IllegalArgumentException();
} else {
for (int i = 1; i <= numPosiciones; i++) {
auxiliar = array[array.length - 1];
for (int j = array.length - 1; j > 0; j--) {
array[j] = array[j - 1];
}
array[0] = auxiliar;
}
}
}
public static void rotarIzquierdaN(int[] array, int numPosiciones) {
int auxiliar;
if (numPosiciones < 0) {
throw new IllegalArgumentException();
} else {
for (int i = 1; i <= numPosiciones; i++) {
auxiliar = array[0];
for (int j = 0; j < array.length - 1; j++) {
array[j] = array[j + 1];
}
array[array.length - 1] = auxiliar;
}
}
}
}
Input
8 10 1 2 3 4 5 6 7 8 9 10 3 D 10 1 2 3 4 5 6 7 8 9 10 4 I 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 D 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10 I 5 1 2 3 4 5 -4 I 5 1 2 3 4 5 -2 D 5 1 2 3 4 5 6 D 5 1 2 3 4 5 10 I
8 10 1 2 3 4 5 6 7 8 9 10 3 D 10 1 2 3 4 5 6 7 8 9 10 4 I 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 D 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 10 I 5 1 2 3 4 5 -4 I 5 1 2 3 4 5 -2 D 5 1 2 3 4 5 6 D 5 1 2 3 4 5 10 I
Output
8 9 10 1 2 3 4 5 6 7 5 6 7 8 9 10 1 2 3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array 1 2 3 4 5 Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array 1 2 3 4 5 5 1 2 3 4 1 2 3 4 5
8 9 10 1 2 3 4 5 6 7 5 6 7 8 9 10 1 2 3 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10 Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array 1 2 3 4 5 Las posiciones a rotar deben ser un numero positivo. No se ha rotado el array 1 2 3 4 5 5 1 2 3 4 1 2 3 4 5
