13 Ordenamiento Burbuja Algoritmo Arreglos Unidimensionales PROGRAM Ordenamiento_Burbuja; CONST Largo = 5; VAR A: ARRAY[1..Largo] OF INTEGER; i,j: INTEGER; BEGIN FOR i:=1 TO Largo DO BEGIN WRITE(‘Ingrese elemento ’,i,‘ : ’); READLN(A[i]) END; FOR i:=Largo DOWNTO 2 DO FOR j:=1 TO i-1 DO IF A[j] > A[j+1] THEN Intercambiar(A[j],A[j+1]); FOR i:=1 TO Largo DO WRITELNA(A[i]) END. (Gp:) i: indica la cantidad de casillas a comparar en cada vuelta. j: indica la cantidad de compa- raciones que se hacen por vuelta.
14 Búsqueda Existen numerosos métodos para buscar un dato entre los elementos de un arreglo, algunos más rápidos que otros.
Por ejemplo, el método “carretero” consiste en comparar uno a uno el dato buscado con cada elemento del arreglo.
Escriba un programa que busque la posición en la que se encuentra el entero 15, dentro de un arreglo que contiene (ordenadamente) los números: 3,6,7,10,15,17,18 (7 en total) (solución en diapositiva siguiente) Arreglos Unidimensionales
15 PROGRAM busqueda_carretera; CONST Largo = 15; TYPE vector = ARRAY[1..Largo] OF INTEGER; VAR X: vector; i, pos, num: INTEGER; FUNCTION buscar(A: vector; dato: INTEGER): INTEGER; VAR j: INTEGER; BEGIN j := 1; WHILE (j < = Largo) AND (A[j] < > dato) DO j := j + 1; buscar := j END; BEGIN FOR i := 1 TO Largo DO BEGIN WRITE(‘Ingrese número: ’); READLN(X[i]) END WRITE(‘Ingrese número a buscar: ’); READLN(num); pos := buscar(X, num); IF pos > Largo THEN WRITELN(‘No se encuentra el número’) ELSE WRITELN(‘El número ’,num,’ está en la posición ’, pos) END. Búsqueda …solución Arreglos Unidimensionales (Gp:) Función que implementa la búsqueda carretera.
16 Búsqueda Binaria Este algoritmo permite buscar un dato entre los elementos de un arreglo considerablemente más rápido que la búsqueda carretera. Se basa en subdividir progresivamente el arreglo en 2 partes, buscando en aquella donde se encuentre el número. El arreglo donde se buscará debe estar ordenado. Ejemplo: Arreglos Unidimensionales medio Si A[Medio] = 15, entonces Encontrado = TRUE Si A[Medio] < 15, entonces Primero = Medio + 1 Si A[Medio] > 15, entonces Ultimo = Medio – 1 medio (Gp:) Encontrado = TRUE
(Gp:) 3 (Gp:) 6 (Gp:) 7 (Gp:) 10 (Gp:) 15 (Gp:) 17 (Gp:) 18 (Gp:) primero (Gp:) último (Gp:) A
(Gp:) 3 (Gp:) 6 (Gp:) 7 (Gp:) 10 (Gp:) 15 (Gp:) 17 (Gp:) 18 (Gp:) primero (Gp:) último (Gp:) A
(Gp:) 3 (Gp:) 6 (Gp:) 7 (Gp:) 10 (Gp:) 15 (Gp:) 17 (Gp:) 18 (Gp:) primero, ultimo, medio (Gp:) A
17 Búsqueda Binaria …solución Arreglos Unidimensionales FUNCTION busqueda_binaria(A: vector; dato: INTEGER): INTEGER; VAR primero, ultimo, medio: INTEGER; encontrado: BOOLEAN; BEGIN primero := 1; ultimo := Largo; encontrado := FALSE; WHILE (primero < = ultimo) AND NOT(encontrado) DO BEGIN medio := (primero + ultimo) DIV 2; IF A[medio] = dato THEN encontrado := TRUE ELSE IF A[medio] < dato THEN primero := medio + 1 ELSE ultimo := medio – 1 END; IF encontrado THEN busqueda_binaria := medio ELSE busqueda_binaria = -1 END; Escribiremos sólo la función busqueda_binaria.
18 Arreglos Bidimensionales (Gp:) 1 (Gp:) 2 (Gp:) N (Gp:) 1 (Gp:) 2 (Gp:) M (Gp:) Declaración: TYPE matriz = ARRAY[1..N,1..M] OF REAL; VAR A: matriz;
Asignación: A[i,j] := valor; Los arreglos bidimensionales se caracterizan por tener dos índices, representando una matriz.
19 Recorrido: el recorrido se efectúa con 2 FOR anidados, y se puede hacer de dos maneras. Arreglos Bidimensionales (Gp:) 1) FOR i := 1 TO N FOR j := 1 TO M READLN(A[i,j]) (Gp:) x (Gp:) x (Gp:) x (Gp:) x (Gp:) 1 (Gp:) 2 (Gp:) N (Gp:) 1 (Gp:) 2 (Gp:) M (Gp:) i (Gp:) j (Gp:) Recorrido hacia el lado, se va llenando el arreglo por filas.
(Gp:) 2) FOR j := 1 TO M FOR i := 1 TO N READLN(A[i,j]) (Gp:) x (Gp:) x (Gp:) x (Gp:) 1 (Gp:) 2 (Gp:) N (Gp:) 1 (Gp:) 2 (Gp:) M (Gp:) i (Gp:) j (Gp:) Recorrido hacia abajo, se va llenando el arreglo por columnas.
20 1. Modificar el algoritmo de ordenamiento burbuja para ordenar los elementos en forma descendente.
2. Se tienen 2 arreglos unidimensionales de tamaño N, en nombre[i] y promedio[i] se almacena el nombre y el promedio del alumno i, respectivamente. Realizar un programa que liste los 10 alumnos con menor promedio.
Ayuda, considere la variable “nombre” del tipo: tipo_nombre = array[1..N] OF STRING[30] Tarea Nº 2
21 3. Se tienen dos arreglos A y B con números enteros, de largo N y M respectivamente, los cuales están ordenados ascendentemente. Realizar un procedimiento que mezcle los dos arreglos en uno nuevo, de manera que éste también se encuentre ordenado. Tarea Nº 2 (Gp:) 4. Usando recurrencia, calcular el i-ésimo elemento en la serie:
22 5. Se desea controlar los resultados de los alumnos en las diferentes asignaturas. Escriba un programa que lea las notas obtenidas en las distintas asignaturas. Además se debe visualizar en pantalla el nombre, calificaciones, promedio por asignatura y general de cada estudiante. Asuma que en el curso hay 50 alumnos, y que cada uno de ellos tiene 6 asignaturas. Tarea Nº 2
| Página siguiente |