Ejercicio maratónico

Dados dos valores n y m, con m>n. Hallar la suma de los dígitos de los números entre n y m. Además debe verificar que se cumpla la siguiente condición: 1<=n<m<=10⁹. Por ejemplo:
                                  8  9     10       11       12
Entre 8 y 12: Suma= 8+9+(1+0)+(1+1)+(1+2)=23

                                      19      20       21
Entre 19 y 21: Suma= (1+9)+(2+0)+(2+1)

Actividad ciclos

Realizar un programa con un menú con tres opciones:

1. Pedir 5 números al usuario y luego calcular el promedio

2. Pedir un número n y hallar la suma de los números desde 1 hasta n, es decir, 1+2+...+n (WHILE)

3. Pedir un número n y hallar la multiplicación de los números desde 1 hasta n, es decir, 1*2*...*n. Además debe realizarse por lo menos una multiplicación. (DO WHILE)

           

Ejercicios sobre ciclos

Realice algoritmos en PHP que dibujen las siguientes figuras. Opcionalmente puede pedir al usuario el tamaño de las figuras, es decir, el número de filas o columnas que desea.

* * * * *

* * * * *

* * * * *

* * * * *

* * * * *

*

*

*

*

* * * * *

* x * x *

* x * x *

* x * x *

* x * x *

* x * x *

- -  * - -

- -  * - -

* * * * *

- -  * - -

- -  * - -

*

- *

- - *

- *

*

* - - - *

- * - * -

- - * - -

- * - * -

* - - - *

Radix Sort y su complejidad temporal.

"En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros." (Extraído de http://es.wikipedia.org/wiki/Ordenamiento_Radix).

A continuación se presenta un programa con tres ejemplos diferentes de algoritmos de ordenamiento Radix y se evalúa cuanto tarda cada uno en ordenar tres arreglos generados al azar. Este programa fue hecho en el IDE Netbeans 6.9.

EL CÓDIGO



public class Main {

    /**

     * @param args the command line arguments

     */

    public static void main(String[] args) {

        // TODO code application logic here

        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 1024);
        }
        int[] arr2 = new int[10000];
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = (int) (Math.random() * 1024);
        }
        int[] arr3 = new int[10000];
        for (int i = 0; i < arr3.length; i++) {
            arr3[i] = (int) (Math.random() * 1024);
        }
        System.out.println("Con un ejemplo Radix Sort: ");
        pruebaTiempoEjecucion(arr, 1);
        System.out.println("Con Radix Sort optimizado: ");
        pruebaTiempoEjecucion(arr3, 3);
        System.out.println("Con mi Radix Sort: ");
        pruebaTiempoEjecucion(arr2, 2);

//        System .out.print("original: ");

//        for(int i=0;i<arr.length;i++){

//            arr[i] = (int)(Math .random() * 1024);

//            System .out.print(arr[i] + " ");

//        }

//        radixSort1(arr);

//        System.out.println("El arreglo original");

//        for (int i = 0; i < arr2.length; i++) {

//            System.out.print(arr2[i] + " ");

//        }

//        System.out.println("");

//        int[] ord = radixSort(arr2);

//        System.out.println("El arreglo ordenado por radixSort");

//        for (int i = 0; i < ord.length; i++) {

//            System.out.print(ord[i] + " ");

//        }

    }

    public static void pruebaTiempoEjecucion(int[] arr, int op) {

        switch (op) {
            case 1:
                double antes = System.currentTimeMillis();
                radixSort1(arr);
                double despues = System.currentTimeMillis();
                System.out.println(despues - antes + " Milisegundos ");
                break;
            case 2:
                double antes1 = System.currentTimeMillis();
                int[] ord = radixSort(arr);
                double despues1 = System.currentTimeMillis();
                System.out.println(despues1 - antes1 + " Milisegundos ");
                break;
            case 3:
                double antes2 = System.currentTimeMillis();
                radixSortC(arr, arr.length);
                double despues2 = System.currentTimeMillis();
                System.out.println(despues2 - antes2 + " Milisegundos ");
                break;
        }

    }

    public static int[] aVector(int[][] x, int n, int m) {//Paso una matriz a vector
        ArrayList<Integer> aux = new ArrayList<Integer>();
       
        for (int k = 0; k < n; k++) {
            for (int l = 0; l < m; l++) {
                if (x[k][l] != 0) {
                    aux.add(x[k][l]);
                } else {
                    l = m;
                }
            }
        }
        int[] ord = new int[aux.size()];
        for(int i=0;i<aux.size();i++){
            ord[i]=aux.get(i);
        }

        return ord;
    }

    /*

     * Operaciones Elementales OE=38

     * Complejidad O:6+4n(8n(4n)+3n+3+4n(6n))=O(n^3)

     */

    public static int[] radixSort(int[] aux) {

        /*LSD es la matriz donde se ordenaran los datos de acuerdo

         *al digito que se esté analizando, bien sea el primero, los

         *de la mitad o el último*/

        int[][] lsd = new int[10][aux.length];//3OE
        int[] x = aux;//2OE//Vector donde se organizarán los datos
        for (int d = 1; d < 5; d++){//4OE //Máximo 4 dígitos
            for (int i = 0; i < x.length; i++) {//4OE//Analiza el número en la posición i
                int pos = 0;//1OE
                int digit = digito(x[i], d);//3OE//Extrae el dígito que se necesita
                while (lsd[digit][pos] != 0){ //2OE
                    pos++;//2OE
                }
                lsd[digit][pos] = x[i];//3OE//Ubica el número de acuerdo al dígito analizado
            }
            x = aVector(lsd, 10, x.length);//3OE//Ordena la matriz LSD en el vector

            /*Se reinicia la matriz LSD para que no haya redundancia de datos*/

            for (int i = 0; i < 10; i++) {//4OE
                for (int j = 0; j < x.length; j++) {//4OE
                    lsd[i][j] = 0;//2OE
                }
            }
        }
        return x;//1OE

    }

    /*

     * Extraído de:

     * http://es.wikipedia.org/wiki/Ordenamiento_Radix

     * Y transformado a Java

     * Operaciones Elementales OE=98

     * Complejidad O:7+10n+9+4n(8n+22n+7n+2+1n(8n)+7n+3)+9n=O(n^3)

     */

    public static void radixSortC(int x[], int n) {
        int[] front = new int[10];//2OE
        int[] rear = new int[10];//2OE
        int[][] node = new int[n][2];//2OE
        int exp, first, i, j, k, p = 0, q, y;//1OE

        /* Inicializar una lista vinculada */

        for (i = 0; i < n - 1; i++) {//4OE
            node[i][0] = x[i];//3OE
            node[i][1] = i + 1;//3OE
        } /* fin del for */
        node[n - 1][0] = x[n - 1];//5OE
        node[n - 1][1] = -1;//3OE
        first = 0;//1OE /* first es la cabeza de la lista vinculada */
        for (k = 1; k < 5; k++) {//4OE

            /* Suponer que tenemos números de cuatro dígitos */

            for (i = 0; i < 10; i++) {//4OE

                /*Inicializar colas */

                rear[i] = -1;//2OE
                front[i] = -1;//2OE
            } /*fin del for */

            /* Procesar cada elemento en la lista */

            while (first != -1) {//1OE
                p = first;//1OE
                first = node[first][1];//2OE
                y = node[p][0];//2OE

                /* Extraer el kâsimo dÁgito */

                exp = (int) Math.pow(10, k - 1);//4OE       /* elevar 10 a la (k-1)ésima potencia */
                j = (y / exp) % 10;//3OE

                /* Insertar y en queue[j] */

                q = rear[j];//2OE
                if (q == -1) {//1OE
                    front[j] = p;//2OE
                } else {
                    node[q][1] = p;//2OE
                }
                rear[j] = p;//2OE
            } /*fin del while */

            /* En este punto, cada registro está en su cola basándose en el dígito k

            Ahora formar una lista única de todos los elementos de la cola.

            Encontrar el primer elemento. */

            for (j = 0; j < 10 && front[j] == -1; j++);//7OE
            ;
            first = front[j];//2OE

            /* Vincular las colas restantes */

            while (j <= 9) {//1OE    /* Verificar si se ha terminado */

                /*Encontrar el elemento siguiente */

                for (i = j + 1; i < 10 && front[i] == -1; i++);//8OE
                ;
                if (i <= 9) {//1OE
                    p = i;//1OE
                    node[rear[j]][1] = front[i];//4OE
                } /* fin del if */
                j = i;//1OE
            } /* fin del while */
            node[rear[p]][1] = -1;//3OE
        } /* fin del for */

        /* Copiar de regreso al archivo original */

        for (i = 0; i < n; i++) {//4OE
            x[i] = node[first][0];//3OE
            first = node[first][1];//2OE
        } /*fin del for */
    } /* fin de radixsort*/

    /**

     * http://foro.elhacker.net/java/algoritmo_radix_sort_en_java-t276529.0.html

     * @param arr

     */

    public static void radixSort1(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        int[][] np = new int[arr.length][2];
        int[] q = new int[0x100];
        int i, j, k, l, f = 0;
        for (k = 0; k < 4; k++) {
            for (i = 0; i < (np.length - 1); i++) {
                np[i][1] = i + 1;
            }
            np[i][1] = -1;
            for (i = 0; i < q.length; i++) {
                q[i] = -1;
            }
            for (f = i = 0; i < arr.length; i++) {
                j = ((0xFF << (k << 3)) & arr[i]) >> (k << 3);
                if (q[j] == -1) {
                    l = q[j] = f;
                } else {
                    l = q[j];
                    while (np[l][1] != -1) {
                        l = np[l][1];
                    }
                    np[l][1] = f;
                    l = np[l][1];
                }
                f = np[f][1];
                np[l][0] = arr[i];
                np[l][1] = -1;
            }
            for (l = q[i = j = 0]; i < 0x100; i++) {
                for (l = q[i]; l != -1; l = np[l][1]) {
                    arr[j++] = np[l][0];
                }
            }
        }
    }

    public static void mostrar(int[][] x, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(x[i][j] + " ");
            }
            System.out.println("");
        }
    }

    public static int digito(int x, int digito) {
        for (int i = 0; i < digito - 1; i++) {
            x = x / 10;
        }
        return x % 10;
    }
}

Para dibujar el segundo triángulo propuesto anteriormente.

Aquí el algoritmo para dibujar el siguiente triángulo:

- - - -*

- - -**

- -***

- ****

*****

public class Main {

   

    public static void main(String[] ){

        dibujarTriangulo2();

    }

    private static void dibujarTriangulo2() {

        int n=5;//Se define el número de columnas

        for (int i = 1; i <= 5; i++) {//Enumerar las Filas del triángulo

            for(int j=1;j<=n-1;j++){//Hay n-1 espacios en cada columna

                System.out.print(" ");//Aumenta un espacio

            }

            for(int k=1;k<=i;k++){//Hay tantas columnas como la fila en la que esté.

                System.out.print("x");//Imprime x para formar el triángulo

            }

            System.out.println();//Cambia de Fila

            n--;//Cada vez hay menos espacios

        }

    }

}

ÉXITOS

Dibujando Triángulos con ciclos Para (for)

Hoy les presento un sencillo problema para mejorar nuestra compresiones de los ciclos for, extramdamente útiles durante la manipulación de arreglos unidimensional como los vectores o n-dimensionales como las matrices y otros más complejos. El problema consiste en dibujar el siguiente triángulo en la consola:

- - - -*

- - -**

- -***

- ****

*****

Los guiones (-) representan un espacio vacío.

Una pista para resolver el problema planteado es, poder dibujar un triángulo de la siguiente manera

*

**

***

****

*****

Para dibujarlo solo implementaremos el siguiente algoritmo programado en JAVA:

public class Main {

    public static void main(String[] args) {

        dibujarTriangulo1();      

    }

    private static void dibujarTriangulo1() {

        for(int i=1;i<=5;i++){//Enumerar las Filas del triángulo

            for(int j=1;j<=i;j++){//Hay tantas columnas como la fila en la que esté.

                System.out.print("x");//Imprime x para formar el triángulo

            }

            System.out.println();//Cambia de Fila

        }

    }

}

Espero que tenga propuestas para dibujarlo y nuevas propuestas.

ÉXITOS

Algoritmos Recursivos

Como programadores, todos conocemos los métodos iterativos. Los más generales, son los generados a partir de estructuras de control como el while, el for, el do while y otros que puedan existir en diferentes lenguajes. Sin embargo existen otros algoritmos que llamamos recursivos, que al igual que los iterativos generan un bucle en busca de la solución a un problema, para el cual es necesario hacer repeticiones. 

Tengamos en cuenta que un método recursivos es un método que se llama así mismo, es un método que se define en terminos de lo que es. Siempre es complicado entender esto, pero hoy veremos ejemplos sencillos que nos den una idea la recursión. Sin embargo, ¿qué debemos elegir, recursión o iteración?. La recursión es un proceso más elaborado que fundamenta algoritmos más complejos como el bactracking y algoritmos para la inteligencia artificial (IA). Sin embargo es código que consume bastantes recursos, es decir, consume mucha memoria, ya que por cada llamado de un método recursivo, se están realizando n veces el mismo proceso. ¿Pero si es un método que se llama así mismo, cuando acaba?. Para programar un método recursivo, es obligatorio crear una condición de escape, al igual que se hace en un while, o un for o un do while. A continuación veremos dos formas de generar el factorial de un número de manera iterativa y recursiva.

Para los que no saben, el factorial de un número, que se define como n!; es la multiplicación de todos los números naturales hasta el número en cuestión, es decir,

n!= 1*2*3*....*n 

El siguiente código esta hecho en lenguaje de programación java, en el IDE Netbeans 6.9 que pueden obtener aquí http://netbeans.org/. Pero no se preocupen, que igualmente funciona en cualquier otro lenguaje.

Ejemplo 1: Método iterativo para obtener el factorial de un número

public class ejemplo{

public static void main(String[] args) {//Método main
        Scanner scan= new Scanner(System.in);//Objeto lector de datos
        int n;//Variable que representa el número al cual se le calculará el factorial
        System.out.println("Ingrese un numero: ");
        n=scan.nextInt();//Lectura del número ingresado por el usuario

        if(n==0)

            return 1;//El factorial de 0 es 1

        else

        {

            int x=1;//Acumulador
            for(int i=1;i<=n;i++)//Cálucla el factorial de un número iterando hasta n
                x*=i;//Igual a x=x*i;

            return x;

        }

        System.out.println("El factorial de "+n+" es: "+ x);//Muestra el número en consola

    }

}

Ejemplo 2: Método recursivo para obtener el factorial de un número
public class ejemplo2{

public static void main(String[] args) {//Método main
        Scanner scan= new Scanner(System.in);//Objeto lector de datos
        int n;//Variable que representa el número al cual se le calculará el factorial
        System.out.println("Ingrese un numero: ");
        n=scan.nextInt();//Lectura del número ingresado por el usuario

         int factorial=factorialRecursivo(n);//LLamada al método recursivo para calcular el factorial de un número
       System.out.println("El factorial de "+n+" es: "+ factorial);//Muestra el número en consola

    }
     public static int factorialRecursivo(int n){
     if(n==0||n==1)//Condición de escape, el factorial de 1 o de 0 siempre es 1. Acaba la recursión. Fin del ciclo
          return 1;
     else
          return n*factorialRecursivo(n-1);//Continua calculando el factorial buscando el factorial del número anterior n-1
     }
}

ÉXITOS PROGRAMANDO AMIGOS MÍOS