Ejercicio Maratónico #2

Dados dos número n y m, mostrar la sumatoria desde 0 hasta un número i, siendo i cada número entre n y m.

Solución al ejercicio maratónico en php

<?php
$n=POST['n'];
$m=POST['m'];
$suma=0;

for($i=$n;$i<=$m;$i=$i+1){//Evalua todos los números entre n y m
if($i<10){
$suma=$suma+$i;
}
if($i>=10){
$auxiliar=$i//Para no alterar el número en el que vamos
while($auxiliar>10){//Saca dígito por dígito y lo suma
$suma=$suma+var_dump((int)($auxiliar%10));//Saca la unidad del numero que haya en //auxiliar y lo suma
$auxiliar=$auxiliar/10;//Reduce el numero;
}
}
}
echo"$suma";
?>

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