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?