P.03 Búsqueda binaria

En una lista ordenada de n elementos, una manera de hallar un valor dado es recorrer exhaustivamente la lista.
Un elemento dado, entonces, será hallado recorriendo -en promedio- n/2 elementos (demuestre el aserto).
Es decir, en una lista de 1000 elementos, hallar uno cualquiera exigirá recorrer -reitero, en promedio- 500 elementos.

Siendo una lista ordenada, podemos efectuar una búsqueda binaria.
Consiste, básicamente, en ir dividiendo la lista en mitades, hasta acotar la lista a dos o un elemento.

Por ejemplo, en una lista ordenada de números impares que parte de 1 (y termina en 1999), hallar el número x = 599.

Declaro las variables punto medio (pm), punto inicial (pi), punto final (pf).

pi = 1
pf = 1999

while
pm = (pi + pf) / 2 = (1 + 1999) / 2 = 1000

Si x > pm, entonces pi = pm, y vuelvo al while

Si x < pm, entonces pf = pm, y vuelvo al while

Si x = pm, hallado el elemento.


La búsqueda binaria implica recorrer log(2) 1000 = 8 elementos ( 2**8 = 1024 ). Es decir, en vez de hacer 500 búsquedas, hago 8 búsquedas...

Ejercicio:

Construya un programa Java que permita ingresar un número y hallarlo en un arreglo de de 500 enteros con la progresión cuyo término general es 2n + 1 y que parte de 1. (Determine el término 500).

C.03 Pendiente de una recta

Ejemplo
Hallar la ecuación para la recta de pendiente 3 que pasa por el punto (1, -2)
m=(y - y1) / (x - x1)
y - y1 = m(x - x1)
y - (-2) = 3(x - (1))
y + 2 = 3x - 3
y = 3x -5

Forma general de la ecuación de la recta: Ax + By + C = 0
Forma punto-pendiente: y - y1 = m(x - x1)
Forma pendiente-intersección: y = mx + b, donde el punto (0, b) es la intersección con el eje y.

Ejercicios
1. Dada la ecuación general 3y + x - 6 = 0, hallar la forma pendiente-intersección.
2. Se quiere construir una cinta transportadora que ascienda 1m por cada 3m de avance horizontal.
    a) Determine la pendiente de la cinta;
    b) Sabiendo que la cinta se instala entre dos pisos, con una distancia vertical de 10m, hallar su longitud.
3. Hallar la ecuación pendiente-intersección de:
    a) 2x - y - 3 = 0
    b) x + 2 y + 6 = 0
    c) y - 1 = 3(x + 4)

P.02 Ejercicios

1. Ingresar 3 enteros distintos entre sí y ordenarlos de menor a mayor.

2. Calcular la suma de los primeros 20 múltiplos de 7.

Enviarme el código Java.

AV.02 Introducción a los vectores

C.02 Ejercicios

C.01 La gráfica de una ecuación

Sea la ecuación 3x + y = 7
Para graficarla podemos usar el procedimiento analítico y el numérico.

Analítico: 3x + y = 7 <==> y = 7 - 3x

Numérico: hacemos una tabla

x | -3   -2   -1   0   1   2   3   4
-------------------------------
y | 16  13   10   7  4   1  -2  -5

Siendo una función lineal (grado 1 o exponente de x = 1), necesitamos 2 puntos cualesquiera para graficarla.

Lo más simple es igualar y = 0:
7 - 3x = 0
3x = 7
x = 7/3
Con lo cual tenemos el punto (7/3, 0)

Y después igualamos x = 0
y = 7 - 3x0 = 7
Con lo cual tenemos el punto (0, 7).

1. Favor graficar.

2. Analizar y graficar y = - x/2 + 2

P.01 Vuelto de caja

El 18/07 envié el siguiente código:


package vuelto_caja;

import java.util.Scanner;

public class Vuelto_caja {

    public static void main(String[] args) {
        Scanner buffer=new Scanner(System.in);
        int [] arr = {10000,5000,2000,1000,500,100,50,10,5,1};
        Integer [] billete = new Integer[10];
        int compra, vuelto, pago = 0;
        System.out.println("Favor ingrese el valor de la compra");
        compra=buffer.nextInt();
        do{
            System.out.println("Favor ingrese el valor pagado");
            pago = buffer.nextInt();
            if(pago < compra)
                System.out.println("monto insuficiente, reintente");
        }while(pago < compra);
        vuelto = pago - compra;
        System.out.println("Su vuelto es "+vuelto);
        for(int i = 0; i < 10; i++){
            billete[i] = vuelto / arr[i];
            vuelto %= arr[i];
        }
        for(int i = 0; i < 10; i++)
            System.out.println("Denominación "+arr[i]+" son: "+billete[i]);
    }
}

Para el arreglo 'billete' usé la clase Integer.
Para los efectos de la funcionalidad deseada, ¿hace diferencia si en vez de usar la clase Integer hubiera usado la primitiva 'int' (int [] billete = {0,0,0,0,0,0,0,0,0,0})? Hagan la prueba.
¿Cuál es la diferencia entre clase y primitiva?

AV.01 Pista de carreras

Para uno o dos jugadores. Imprimir el dibujo.

- Parte el jugador A.
- Deben llegar a la meta.
- Cada jugador mueve su posición según las siguientes reglas, avanzando de un punto a otro:

• Cada nuevo punto en la cuadrícula y el segmento de recta que lo conecta con el punto anterior en la cuadrícula debe encontrarse completamente dentro de la pista.
• Dos jugadores no pueden ocupar el mismo punto en la cuadrícula en el mismo turno. (Esta es la regla de “no colisión”.)
• Cada nuevo movimiento se relaciona con el movimiento anterior del modo siguiente: si un jugador se mueve a unidades horizontalmente y b unidades verticalmente en un movimiento, entonces en el siguiente movimiento debe moverse entre a – 1 y a + 1 unidades horizontalmente, y entre b – 1 y b + 1 unidades verticalmente. (Esta es la regla “aceleración/desaceleración”.) Note que esta regla fuerza al primer movimiento a ser 1 unidad verticalmente y/o 1 unidad horizontalmente.
• Un jugador que choque con otro o deje la pista, es eliminado. El ganador es el primer jugador en cruzar la línea de meta. Si más de un jugador cruza la línea de meta en el mismo turno, quien las sobrepase más es el ganador.

Escanear la solución y enviármela.