Algoritmos de Ordenación
Ordenación por Inserción (Insertion Sort)
Procedimiento Ins
procedimiento Ins (var T[1..n])
para i := 2 hasta n hacer
x := T[i];
j := i - 1;
mientras j > 0 y T[j] > x hacer
T[j+1] := T[j];
j := j - 1
fin mientras;
T[j+1] := x;
fin para
fin procedimiento
Ordenación por Selección (Selection Sort)
Procedimiento Sel
procedimiento Sel (var T[1..n])
para i := 1 hasta n-1 hacer
minj := i;
minx := T[i];
para j := i+1 hasta n hacer
si T[j] < minx entonces
minj := j;
minx := T[j];
fin si
fin para;
T[minj] := T[i];
T[i] := minx;
fin para
fin procedimiento
Ordenación por Fusión (Merge Sort)
Procedimiento FR (Fusión Recursiva)
procedimiento FR(var T[izq..der], umbral: entero) // umbral para optimización híbrida
si izq + umbral < der entonces
centro := (izq + der) div 2;
FR(T[izq..centro], umbral);
FR(T[centro+1..der], umbral);
Fusion(T, centro, izq, der); // Se asume que Fusion necesita T, centro, izq y der
sino
Insercion(T, izq, der); // Se asume que Insercion opera en un rango
fin si
fin procedimiento
Procedimiento Fusion
procedimiento Fusion(var T: array, centro: entero, izq: entero, der: entero) // Parámetros añadidos para claridad
var aux: array[izq..der]; // Se asume un array auxiliar global o pasado
i := izq; j := centro + 1; k := izq; // j debe empezar en centro + 1
mientras i <= centro y j <= der hacer
si T[i] <= T[j] entonces
aux[k] := T[i]; i := i + 1;
sino
aux[k] := T[j]; j := j + 1;
fin si;
k := k + 1
fin mientras;
mientras i <= centro hacer
aux[k] := T[i]; i := i + 1; k := k + 1;
fin mientras;
mientras j <= der hacer
aux[k] := T[j]; j := j + 1; k := k + 1;
fin mientras;
para k := izq hasta der hacer
T[k] := aux[k]
fin para
fin procedimiento
Ordenación de Shell (Shell Sort)
Procedimiento Ordenacion de Shell
procedimiento OrdenacionDeShell(var T[1..n])
incremento := n;
repetir
incremento := incremento div 2;
para i := incremento + 1 hasta n hacer
tmp := T[i];
j := i;
seguir := verdadero;
mientras j - incremento > 0 y seguir hacer
si tmp < T[j - incremento] entonces
T[j] := T[j - incremento];
j := j - incremento;
sino
seguir := falso;
fin si
fin mientras;
T[j] := tmp;
fin para
hasta incremento = 1
fin procedimiento
Ordenación Rápida (Quick Sort)
Procedimiento QS
procedimiento QS (var T[1..n])
QSR(T, 1, n); // Se asume que QSR necesita los límites
Insercion(T, 1, n); // Se asume que Insercion opera en un rango
fin procedimiento
Procedimiento QSR (Quick Sort Recursivo)
procedimiento QSR(var T: array, i: entero, j: entero)
si i + umbral <= j entonces // umbral para optimización híbrida
mediana3(T, i, j);
pivote := T[j-1];
k := i;
m := j - 1;
repetir
repetir
k := k + 1
hasta T[k] >= pivote;
repetir
m := m - 1
hasta T[m] <= pivote;
intercambiar (T[k], T[m]);
hasta m <= k;
intercambiar (T[k], T[j-1]); // Colocar el pivote en su posición final
QSR(T, i, k-1);
QSR(T, k+1, j);
fin si
fin procedimiento
Procedimiento mediana3
procedimiento mediana3 (var T: array, i: entero, j: entero)
centro := (i + j) div 2;
si T[i] > T[centro] entonces intercambiar(T[i], T[centro]) fin si;
si T[i] > T[j] entonces intercambiar(T[i], T[j]) fin si;
si T[centro] > T[j] entonces intercambiar(T[centro], T[j]) fin si;
intercambiar(T[centro], T[j-1])
fin procedimiento
Estructuras de Datos y Operaciones
Montículos (Heaps)
Procedimiento Ordenación por Montículos (Heap Sort)
procedimiento OPM(var T[1..n])
var M: Monticulo; // Se asume que M es una estructura de Montículo
CrearM(T, M);
para i := 1 hasta n hacer
T[n-i+1] := EliminarMax(M); // EliminarMax devuelve el elemento y lo elimina
fin para
fin procedimiento
Procedimiento CrearM (Crear Montículo)
procedimiento CrearM(T[1..n], var M: Monticulo)
copiar T en M.vectorM; // Copia los elementos de T al vector interno de M
M.TamM := n; // Establece el tamaño del montículo
para i := n div 2 hasta 1 paso -1 hacer
undir (M, i);
fin para
fin procedimiento
Tipo Monticulo
tipo Monticulo = registro
TamM: 0..tamMax;
vectorM: vector[1..tamMax] de tipoElem;
fin registro
Procedimiento InicializarM
procedimiento InicializarM(var M: Monticulo)
M.TamM := 0
fin procedimiento
Función Mvacio (Montículo Vacío)
funcion Mvacio(M: Monticulo): booleano
devolver M.TamM = 0
fin funcion
Procedimiento Flotar (Heapify Up)
procedimiento Flotar(var M: Monticulo, i: entero)
mientras i > 1 y M.vectorM[i div 2] < M.vectorM[i] hacer
intercambiar(M.vectorM[i div 2], M.vectorM[i]);
i := i div 2
fin mientras
fin procedimiento
Procedimiento Insertar en Montículo
procedimiento insertar(x: tipoElem, var M: Monticulo)
si M.TamM = tamMax entonces
error "Montículo lleno"
sino
M.TamM := M.TamM + 1;
M.vectorM[M.TamM] := x;
Flotar(M, M.TamM);
fin si
fin procedimiento
Procedimiento Undir (Heapify Down)
procedimiento undir(var M: Monticulo, i: entero)
var k: entero;
repetir
k := i; // k es el índice del elemento más grande entre i y sus hijos
hijoIzq := 2 * i;
hijoDer := 2 * i + 1;
si hijoIzq <= M.TamM y M.vectorM[hijoIzq] > M.vectorM[k] entonces
k := hijoIzq;
fin si;
si hijoDer <= M.TamM y M.vectorM[hijoDer] > M.vectorM[k] entonces
k := hijoDer;
fin si;
si k <> i entonces // Si el elemento más grande no es el padre
intercambiar(M.vectorM[i], M.vectorM[k]);
i := k; // Continuar hundiendo desde la nueva posición
sino
i := k; // No se hizo ningún intercambio, salir del bucle
fin si
hasta k = i // Si i no cambió en una iteración, significa que el elemento está en su posición correcta
fin procedimiento
Función EliminarMax (Eliminar Mayor)
funcion EliminarMax(var M: Monticulo): tipoElem
si Mvacio(M) entonces
error "Montículo vacío"
sino
x := M.vectorM[1];
M.vectorM[1] := M.vectorM[M.TamM];
M.TamM := M.TamM - 1;
si M.TamM > 0 entonces
undir(M, 1);
fin si;
devolver x
fin si
fin funcion
Búsqueda Binaria (Binary Search)
Función BB (Búsqueda Binaria)
funcion BB(x: tipoElem, var a[1..n]): entero
devolver BBR(x, a, 1, n);
fin funcion
Función BBR (Búsqueda Binaria Recursiva)
funcion BBR(x: tipoElem, var a[1..n], izq: entero, der: entero): entero
si izq > der entonces
devolver 0 // Elemento no encontrado
sino si izq = der entonces
si x = a[izq] entonces
devolver izq
sino
devolver 0
fin si
sino
medio := (izq + der) div 2;
si x < a[medio] entonces
devolver BBR(x, a, izq, medio - 1)
sino si x > a[medio] entonces
devolver BBR(x, a, medio + 1, der)
sino
devolver medio // Elemento encontrado en medio
fin si
fin si
fin funcion
Suma de Subarray Máxima (Maximum Subarray Sum)
Función SSM
funcion SSM(var a[1..n]): entero
devolver SSMR(a, 1, n)
fin funcion
Función SSMR (Suma de Subarray Máxima Recursiva)
funcion SSMR(var a[izq..der], izq: entero, der: entero): entero
si izq = der entonces
si a[izq] > 0 entonces
devolver a[izq]
sino
devolver 0
fin si
sino
centro := (izq + der) div 2;
sol1 := SSMR(a, izq, centro);
sol2 := SSMR(a, centro + 1, der);
SMI := 0; SI := 0;
para i := centro hasta izq paso -1 hacer
SI := SI + a[i];
si SI > SMI entonces SMI := SI fin si;
fin para;
SMD := 0; SD := 0;
para i := centro + 1 hasta der hacer
SD := SD + a[i];
si SD > SMD entonces SMD := SD fin si;
fin para;
devolver max(sol1, sol2, SMI + SMD)
fin si
fin funcion
Pilas (Stacks)
Tipo Pila
tipo Pila = registro
cima: 0..tamMax;
vectorP: vector[1..tamMax] de tipoElem;
fin registro
Procedimiento crearP (Crear Pila)
procedimiento crearP(var P: Pila)
P.cima := 0
fin procedimiento
Función Pvacia (Pila Vacía)
funcion Pvacia(P: Pila): booleano
devolver P.cima = 0
fin funcion
Procedimiento Apilar (Push)
procedimiento Apilar(x: tipoElem, var P: Pila)
si P.cima = tamMax entonces
error "Pila llena"
sino
P.cima := P.cima + 1;
P.vectorP[P.cima] := x;
fin si
fin procedimiento
Función Cima (Top)
funcion Cima(P: Pila): tipoElem
si Pvacia(P) entonces
error "Pila vacía"
sino
devolver P.vectorP[P.cima]
fin si
fin funcion
Procedimiento Desapilar (Pop)
procedimiento Desapilar(var P: Pila)
si Pvacia(P) entonces
error "Pila vacía"
sino
P.cima := P.cima - 1
fin si
fin procedimiento
Colas (Queues)
Tipo Cola
tipo Cola = registro
cabeza: 1..tamMax;
finalC: 1..tamMax;
tamCola: 0..tamMax;
vectorC: vector[1..tamMax] de tipoElem; // Se asume tipoElem
fin registro
Procedimiento CrearC (Crear Cola)
procedimiento CrearC(var C: Cola)
C.tamCola := 0;
C.cabeza := 1;
C.finalC := tamMax; // O 0, dependiendo de la implementación circular
fin procedimiento
Función Cvacia (Cola Vacía)
funcion Cvacia(C: Cola): booleano
devolver C.tamCola = 0;
fin funcion
Procedimiento incrementar (Privado)
procedimiento incrementar(var x: entero) (*privado*)
si x = tamMax entonces
x := 1;
sino
x := x + 1;
fin si
fin procedimiento
Procedimiento insertar (Enqueue)
procedimiento insertar(x: tipoElem, var C: Cola)
si C.tamCola = tamMax entonces
error "Cola llena"
sino
C.tamCola := C.tamCola + 1;
incrementar(C.finalC);
C.vectorC[C.finalC] := x;
fin si
fin procedimiento
Función QuitarPrimero (Dequeue)
funcion QuitarPrimero(var C: Cola): tipoElem
si Cvacia(C) entonces
error "Cola vacía"
sino
C.tamCola := C.tamCola - 1;
var x: tipoElem;
x := C.vectorC[C.cabeza];
incrementar(C.cabeza);
devolver x
fin si
fin funcion
Función Primero (Front)
funcion Primero(C: Cola): tipoElem
si Cvacia(C) entonces
error "Cola vacía"
sino
devolver C.vectorC[C.cabeza]
fin si
fin funcion
Listas Enlazadas (Linked Lists)
Tipos de Lista Enlazada
tipo Pnodo = ^Nodo;
Lista = Pnodo;
Posicion = Pnodo;
Nodo = registro
Elemento: TipoElem;
Siguiente: Pnodo;
fin registro
Procedimiento CrearL (Crear Lista)
procedimiento CrearL(var L: Lista)
var tmp: Pnodo;
nuevo(tmp);
si tmp = nil entonces
error "Memoria agotada"
sino
tmp^.Elemento := {valor de nodo cabecera}; // O un valor nulo/sentinela
tmp^.Siguiente := nil;
L := tmp
fin si
fin procedimiento
Función Lvacia (Lista Vacía)
funcion Lvacia(L: Lista): booleano
devolver L^.Siguiente = nil
fin funcion
Función Buscar en Lista
funcion Buscar(x: TipoElem, L: Lista): Posicion
var p: Pnodo;
p := L^.Siguiente;
mientras p <> nil y p^.Elemento <> x hacer
p := p^.Siguiente
fin mientras;
devolver p
fin funcion
Función ultimoElem (Último Elemento)
funcion ultimoElem(p: Posicion): booleano
devolver p^.Siguiente = nil
fin funcion
Función BuscarAnterior
funcion BuscarAnterior(x: TipoElem, L: Lista): Posicion
var p: Pnodo;
p := L;
mientras p^.Siguiente <> nil y p^.Siguiente^.Elemento <> x hacer
p := p^.Siguiente
fin mientras;
devolver p
fin funcion
Procedimiento Eliminar de Lista
procedimiento Eliminar(x: TipoElem, var L: Lista)
var p: Posicion;
p := BuscarAnterior(x, L);
si ultimoElem(p) o p^.Siguiente^.Elemento <> x entonces // Añadir condición para asegurar que x fue encontrado
error "Elemento no encontrado"
sino
var tmp: Pnodo;
tmp := p^.Siguiente;
p^.Siguiente := tmp^.Siguiente;
liberar(tmp);
fin si
fin procedimiento
Procedimiento Insertar en Lista
procedimiento Insertar(x: TipoElem, var L: Lista, p: Posicion)
var tmp: Pnodo;
nuevo(tmp);
si tmp = nil entonces
error "Memoria agotada"
sino
tmp^.Elemento := x;
tmp^.Siguiente := p^.Siguiente;
p^.Siguiente := tmp;
fin si
fin procedimiento
Árboles Binarios de Búsqueda (Binary Search Trees – ABB)
Tipos de ABB
tipo Pnodo = ^Nodo;
Nodo = registro
Elemento: TipoElem;
izq, der: Pnodo;
fin registro
Procedimiento CrearABB
procedimiento CrearABB(var A: Pnodo)
A := nil
fin procedimiento
Función Buscar en ABB
funcion Buscar (x: TipoElem, A: Pnodo): Pnodo
si A = nil entonces
devolver nil
sino si x = A^.Elemento entonces
devolver A
sino si x < A^.Elemento entonces
devolver Buscar(x, A^.izq)
sino
devolver Buscar(x, A^.der)
fin si
fin funcion
Función BuscarMin en ABB
funcion BuscarMin(A: Pnodo): TipoElem
si A = nil entonces
devolver nil // O un valor que indique error/no encontrado
sino si A^.izq = nil entonces
devolver A^.Elemento
sino
devolver BuscarMin(A^.izq)
fin si
fin funcion
Procedimiento Insertar en ABB
procedimiento Insertar(x: TipoElem, var A: Pnodo)
si A = nil entonces
nuevo(A);
si A = nil entonces
error "Sin memoria"
sino
A^.Elemento := x;
A^.izq := nil;
A^.der := nil;
fin si
sino si x < A^.Elemento entonces
Insertar(x, A^.izq)
sino si x > A^.Elemento entonces
Insertar(x, A^.der)
// Si x = A^.Elemento, no se hace nada (no se permiten duplicados o se maneja de otra forma)
fin si
fin procedimiento
Procedimiento Visualizar ABB (Recorrido Inorden)
procedimiento Visualizar(A: Pnodo)
si A <> nil entonces
Visualizar(A^.izq);
Escribir(A^.Elemento);
Visualizar(A^.der);
fin si
fin procedimiento
Procedimiento Eliminar de ABB
procedimiento Eliminar(x: TipoElem, var A: Pnodo)
si A = nil entonces
error "Árbol vacío"
sino si x < A^.Elemento entonces
Eliminar(x, A^.izq)
sino si x > A^.Elemento entonces
Eliminar(x, A^.der)
sino // x es igual a A^.Elemento, se encontró el nodo a eliminar
var tmp: Pnodo;
si A^.izq = nil entonces // Caso 1: No tiene hijo izquierdo (o es una hoja)
tmp := A;
A := A^.der;
liberar(tmp);
sino si A^.der = nil entonces // Caso 2: No tiene hijo derecho (o es una hoja)
tmp := A;
A := A^.izq;
liberar(tmp);
sino // Caso 3: Tiene ambos hijos
var sucesor_val: TipoElem;
sucesor_val := BuscarMin(A^.der); // Encontrar el sucesor inorden (mínimo del subárbol derecho)
A^.Elemento := sucesor_val;
Eliminar(sucesor_val, A^.der); // Eliminar el sucesor del subárbol derecho
fin si
fin si
fin procedimiento
Función Altura de ABB
funcion altura(A: Pnodo): entero
si A = nil entonces
devolver -1
sino
devolver 1 + max(altura(A^.der), altura(A^.izq))
fin si
fin funcion
Procedimiento OrdenNivel (Recorrido por Niveles – BFS)
procedimiento OrdenNivel(A: Pnodo)
var C: Cola;
crearC(C);
si A <> nil entonces
insertar(A, C); // Insertar el nodo raíz en la cola
fin si;
mientras no Cvacia(C) hacer
var p: Pnodo;
p := QuitarPrimero(C);
escribir(p^.Elemento);
si p^.izq <> nil entonces
insertar(p^.izq, C);
fin si;
si p^.der <> nil entonces
insertar(p^.der, C);
fin si
fin mientras
fin procedimiento
Tablas de Dispersión (Hash Tables)
Funciones de Dispersión (Hash Functions)
Función Dispersion1
funcion Dispersion1(clave: cadena, tamClave: entero): entero
var valor: entero;
valor := ascii(clave[1]);
para i := 2 hasta tamClave hacer
valor := valor + ascii(clave[i]);
fin para;
devolver valor mod N // N es el tamaño de la tabla hash
fin funcion
Función Dispersion2
funcion Dispersion2(clave: cadena, tamClave: entero): entero
devolver (ascii(clave[1]) + 27 * ascii(clave[2]) + 729 * ascii(clave[3])) mod N
fin funcion
Función Dispersion3
funcion Dispersion3(clave: cadena, tamClave: entero): entero
var valor: entero;
valor := ascii(clave[1]);
para i := 2 hasta tamClave hacer
valor := (32 * valor + ascii(clave[i])) mod N;
fin para;
devolver valor
fin funcion
Dispersión Abierta (Encadenamiento Separado)
Tipos para Dispersión Abierta
tipo
indice = 0..N-1;
PosicionNodo = ^Nodo; // Renombrado para evitar conflicto con Posicion de Lista
Lista = PosicionNodo;
Nodo = registro
Elemento: TipoElem;
Siguiente: PosicionNodo;
fin registro;
TablaDispersion = vector[indice] de Lista;
Procedimiento IniciarT (Inicializar Tabla)
procedimiento IniciarT(var T: TablaDispersion)
para i := 0 hasta N-1 hacer
CrearL(T[i]); // Asume que CrearL inicializa una lista vacía con nodo cabecera
fin para
fin procedimiento
Función Buscar en Tabla de Dispersión Abierta
funcion Buscar(x: TipoElem, T: TablaDispersion): PosicionNodo
var i: indice;
i := Dispersion1(x, tamClave); // Se asume que x es una clave y se usa Dispersion1
devolver Buscar(x, T[i]); // Asume que Buscar es la función Buscar de Listas Enlazadas
fin funcion
Procedimiento InsertarElem en Tabla de Dispersión Abierta
procedimiento InsertarElem(x: TipoElem, var T: TablaDispersion)
var pos: PosicionNodo;
pos := Buscar(x, T);
si pos = nil entonces // Si el elemento no está ya en la tabla
var i: indice;
i := Dispersion1(x, tamClave); // Se asume que x es una clave y se usa Dispersion1
Insertar(x, T[i], T[i]); // Insertar al principio de la lista (después del nodo cabecera)
fin si
fin procedimiento
Dispersión Cerrada (Sondeo Abierto)
Tipos para Dispersión Cerrada
tipo
ClaseDeEntrada = (legitima, vacia, eliminada);
indice = 0..N-1;
Posicion = indice; // Renombrado para evitar conflicto con Posicion de Lista
Entrada = registro
Elemento: TipoElem;
Informacion: ClaseDeEntrada;
fin registro;
TablaDispersion = vector[indice] de Entrada;
Procedimiento InicializarT (Inicializar Tabla)
procedimiento InicializarT(var D: TablaDispersion)
para i := 0 hasta N-1 hacer
D[i].Informacion := vacia;
fin para
fin procedimiento
Función Buscar en Tabla de Dispersión Cerrada
funcion Buscar(x: TipoElem, D: TablaDispersion): Posicion
var i: entero;
i := 0;
var p: entero;
p := Dispersion1(x, tamClave); // Se asume que x es una clave y se usa Dispersion1
var posActual: entero;
posActual := p;
mientras D[posActual].Informacion <> vacia y D[posActual].Elemento <> x hacer
i := i + 1;
posActual := (p + FuncionResolucionColision(p, i)) mod N; // Se asume FuncionResolucionColision
fin mientras;
devolver posActual
fin funcion
Procedimiento Insertar en Tabla de Dispersión Cerrada
procedimiento Insertar(x: TipoElem, var D: TablaDispersion)
var pos: Posicion;
pos := Buscar(x, D);
si D[pos].Informacion <> legitima entonces
D[pos].Elemento := x;
D[pos].Informacion := legitima;
fin si
fin procedimiento
Procedimiento Eliminar de Tabla de Dispersión Cerrada
procedimiento Eliminar(x: TipoElem, var D: TablaDispersion)
var pos: Posicion;
pos := Buscar(x, D);
si D[pos].Informacion = legitima entonces
D[pos].Informacion := eliminada;
fin si
fin procedimiento
Conjuntos Disjuntos (Disjoint Sets)
Tipos para Conjuntos Disjuntos
tipo
Elemento = entero;
conj = entero; // Representa el representante del conjunto
conjDisj = vector[1..N] de entero; // N es el número total de elementos
Función Buscar1 (Sin compresión de caminos)
funcion Buscar1(C: conjDisj, x: Elemento): conj
devolver C[x]
fin funcion
Procedimiento Unir1 (Por tamaño/altura, simple)
procedimiento Unir1(var C: conjDisj, a: Elemento, b: Elemento)
var i, j, K: entero;
i := min(C[a], C[b]);
j := max(C[a], C[b]);
para K := 1 hasta N hacer
si C[K] = j entonces C[K] := i fin si;
fin para
fin procedimiento
Función Buscar2 (Con compresión de caminos)
funcion Buscar2(C: conjDisj, x: Elemento): conj
var r: Elemento;
r := x;
mientras C[r] <> r hacer
r := C[r]
fin mientras;
devolver r
fin funcion
Procedimiento Unir2 (Por rango/altura, simple)
procedimiento Unir2(var C: conjDisj, r1: conj, r2: conj)
si r1 < r2 entonces
C[r2] := r1
sino
C[r1] := r2
fin si
fin procedimiento
Procedimiento Unir3 (Por rango/altura con optimización)
procedimiento Unir3(var C: conjDisj, var A: array, r1: conj, r2: conj) // A es el array de rangos/alturas
si A[r1] = A[r2] entonces
A[r1] := A[r1] + 1;
C[r2] := r1;
sino si A[r1] > A[r2] entonces
C[r2] := r1;
sino
C[r1] := r2;
fin si
fin procedimiento
Función Buscar3 (Con compresión de caminos completa)
funcion Buscar3(var C: conjDisj, x: Elemento): conj
var r, i, j: Elemento;
r := x;
mientras C[r] <> r hacer
r := C[r]
fin mientras;
i := x;
mientras i <> r hacer
j := C[i];
C[i] := r;
i := j;
fin mientras;
devolver r
fin funcion
Algoritmos de Diseño
Algoritmos Voraces (Greedy Algorithms)
Función Voraz (Esquema General)
funcion voraz (C: conjunto): conjunto
var S: conjunto;
S := conjunto vacio;
mientras C <> conjunto vacio y no solucion(S) hacer
var x: tipoElem;
x := seleccionar(C);
C := C - {x};
si factible(S union {x}) entonces
S := S union {x};
fin si
fin mientras;
si solucion(S) entonces
devolver S
sino
devolver "no hay soluciones"
fin si
fin funcion
Función DevolverCambio (Problema del Cambio de Monedas)
funcion devolverCambio(n: entero): conjunto
var S: conjunto;
var ss: entero;
S := conjunto vacio;
ss := 0;
mientras ss <> n hacer
var x: entero;
x := mayor elemento de M: ss + x <= n; // M es el conjunto de monedas disponibles
si no existe tal elemento entonces
devolver "no hay soluciones"
fin si;
S := S union {moneda de valor x};
ss := ss + x;
fin mientras;
devolver S
fin funcion
Función MochilaFraccionaria (Knapsack Fraccionario)
funcion MochilaFraccionaria (w[1..n]: array, v[1..n]: array, W: entero): array
var x: array[1..n];
para i := 1 hasta n hacer
x[i] := 0;
fin para;
var peso: entero;
peso := 0;
mientras peso < W hacer
var i: entero;
i := el mejor objeto restante; // Objeto con mayor v[i]/w[i]
si peso + w[i] <= W entonces
x[i] := 1;
peso := peso + w[i];
sino
x[i] := (W - peso) / w[i];
peso := W;
fin si
fin mientras;
devolver x
fin funcion
Divide y Vencerás (Divide and Conquer)
Función DyV (Esquema General)
funcion DyV(x: tipoProblema): tipoSolucion
si x suficientemente pequeño entonces
devolver ad-hoc(x)
sino
descomponer x en casos más pequeños; // x1, x2, ..., xa
para i := 1 hasta a hacer
yi := DyV(xi);
fin para;
combinar todos yi para obtener solucion y de x;
devolver y
fin si
fin funcion
Programación Dinámica (Dynamic Programming)
Función Monedas (Problema del Cambio de Monedas)
funcion monedas(n: entero): entero
const v[1..m] = [1, 4, 6]; // Valores de las monedas
var c: array[1..m, 0..n];
para i := 1 hasta m hacer
c[i, 0] := 0;
fin para;
para i := 1 hasta m hacer
para j := 1 hasta n hacer
si i = 1 y j < v[i] entonces
c[1, j] := infinito;
sino si i = 1 entonces
c[1, j] := 1 + c[1, j - v[1]];
sino si j < v[i] entonces
c[i, j] := c[i-1, j];
sino
c[i, j] := min(c[i-1, j], 1 + c[i, j - v[i]]);
fin si
fin para
fin para;
devolver c[m, n]
fin funcion
Algoritmos de Grafos
Ordenación Topológica (Topological Sort)
Función OT1 (Basada en Grado de Entrada)
funcion OT1(G: Grafo): array
var GradoEntrada: array[1..n];
GradoEntrada := CalcularGrado(G); // Asume función CalcularGrado
var ordenTopologico: array[1..n];
para i := 1 hasta n hacer
ordenTopologico[i] := 0;
fin para;
var contador: entero;
contador := 0;
mientras contador <= n hacer // Debería ser contador < n
var v: nodo;
v := Buscar nodo grado 0 sin ordenTopologico asignado;
si v no encontrado entonces
devolver error "Grafo tiene un ciclo"
sino
ordenTopologico[v] := contador;
incrementar contador;
para cada W adyacente a v hacer
GradoEntrada[W] := GradoEntrada[W] - 1;
fin para
fin si
fin mientras;
devolver ordenTopologico
fin funcion
Función OT2 (Basada en Cola – Algoritmo de Kahn)
funcion OT2(G: Grafo): array
var GradoEntrada: array[1..n];
GradoEntrada := CalcularGrado(G);
var ordenTopologico: array[1..n];
para i := 1 hasta n hacer
ordenTopologico[i] := 0;
fin para;
var C: Cola;
crearC(C);
var contador: entero;
contador := 1;
para cada nodo v hacer
si GradoEntrada[v] = 0 entonces
insertar(v, C);
fin si
fin para;
mientras no Cvacia(C) hacer
var v: nodo;
v := QuitarPrimero(C);
ordenTopologico[v] := contador;
incrementar contador;
para cada w adyacente a v hacer
GradoEntrada[w] := GradoEntrada[w] - 1;
si GradoEntrada[w] = 0 entonces
insertar(w, C);
fin si
fin para
fin mientras;
si contador <= n entonces // Si no se visitaron todos los nodos, hay un ciclo
devolver error "Grafo tiene ciclo"
sino
devolver ordenTopologico
fin si
fin funcion
Árbol de Expansión Mínima (Minimum Spanning Tree – MST)
Función Kruskal
funcion Kruskal(G=(N, A): Grafo): conjunto
Ordenar A según longitudes crecientes;
var n: entero;
n := |N|; // Número de nodos
var T: conjunto;
T := conjunto vacio;
inicializar n conjuntos; // Cada nodo en su propio conjunto disjunto
repetir
var a: arista;
a := (u, v) : arista más corta de A sin considerar; // Obtener la arista más corta no procesada
var ConjuntoU, ConjuntoV: conj;
ConjuntoU := Buscar(u); // Representante del conjunto de u
ConjuntoV := Buscar(v); // Representante del conjunto de v
si ConjuntoU <> ConjuntoV entonces
fusionar(ConjuntoU, ConjuntoV); // Unir los conjuntos
T := T union {a};
fin si
hasta |T| = n - 1;
devolver T
fin funcion
Función Prim1 (Esquema Conceptual)
funcion Prim1 (G=(N, A): Grafo): conjunto
var T: conjunto;
T := conjunto vacio;
var B: conjunto;
B := {un nodo de N}; // Conjunto de nodos ya incluidos en el MST
mientras B <> N hacer
var a: arista;
a := (u, v) : arista de A con u en B y v no en B, de peso mínimo;
T := T union {a};
B := B union {v};
fin mientras;
devolver T
fin funcion
Función Prim2 (Implementación Detallada)
funcion Prim2(L[1..n, 1..n]: matriz): conjunto // L es la matriz de adyacencia/pesos
var distMin: array[1..n];
var proximo: array[1..n];
var T: conjunto;
T := conjunto vacio;
distMin[1] := 0; // Costo al nodo inicial (arbitrario, aquí nodo 1)
para i := 2 hasta n hacer
proximo[i] := 1; // El nodo 1 es el más cercano inicialmente
distMin[i] := L[i, 1]; // Distancia del nodo i al nodo 1
fin para;
repetir n - 1 veces
var min_val: entero;
min_val := infinito;
var k: entero; // Nodo con la distancia mínima actual
para j := 2 hasta n hacer
si distMin[j] >= 0 y distMin[j] < min_val entonces // distMin[j] >= 0 indica que no ha sido incluido
min_val := distMin[j];
k := j;
fin si
fin para;
T := T union {{proximo[k], k}}; // Añadir la arista al MST
distMin[k] := -1; // Marcar el nodo k como incluido en el MST
para j := 2 hasta n hacer
si L[j, k] < distMin[j] y distMin[j] >= 0 entonces // Si L[j,k] es menor y j no está en el MST
distMin[j] := L[j, k];
proximo[j] := k;
fin si
fin para
fin repetir;
devolver T
fin funcion
Camino Más Corto (Shortest Path)
Función Dijkstra
funcion Dijkstra(L[1..n, 1..n]: matriz): array // L es la matriz de adyacencia/pesos
var D: array[1..n]; // D[i] es la distancia más corta desde el origen al nodo i
var C: conjunto; // Conjunto de nodos no visitados
C := {2..n}; // Nodos a visitar, asumiendo origen en nodo 1
para i := 2 hasta n hacer
D[i] := L[1, i]; // Distancia inicial desde el nodo 1
fin para;
repetir n - 2 veces // Repetir para n-1 nodos (excluyendo el origen)
var v: nodo;
v := nodo de C que minimiza D[v];
C := C - {v}; // Eliminar v de los nodos no visitados
para cada w en C hacer
si D[v] + L[v, w] < D[w] entonces // Si se encuentra un camino más corto a w a través de v
D[w] := D[v] + L[v, w];
fin si
fin para
fin repetir;
devolver D
fin funcion
Recorridos de Grafos (Graph Traversal)
Procedimiento DFS_Recursivo (Recorrido en Profundidad Recursivo)
procedimiento DFS_Recursivo(v: nodo, var visita: entero, var preorden: array, var marca: array)
visita := visita + 1;
preorden[v] := visita; // Numerar en preorden
marca[v] := "visitado";
para cada w adyacente a v hacer
si marca[w] <> "visitado" entonces
DFS_Recursivo(w, visita, preorden, marca);
fin si
fin para;
escribir(v); // Para ordenación topológica inversa en DAGs
fin procedimiento
Procedimiento DFS_Completo (Para Grafos No Conexos)
procedimiento DFS_Completo(G=(N, A): Grafo)
var visita: entero;
var preorden: array[1..|N|];
var marca: array[1..|N|]; // "no visitado", "visitado"
para cada nodo v en N hacer
marca[v] := "no visitado";
fin para;
visita := 0;
para cada nodo v en N hacer
si marca[v] <> "visitado" entonces
DFS_Recursivo(v, visita, preorden, marca);
fin si
fin para
fin procedimiento
Procedimiento DFS_Iterativo (Recorrido en Profundidad Iterativo)
procedimiento DFS_Iterativo(v: nodo)
var P: Pila;
var marca: array; // Se asume inicializada a "no visitado"
crearP(P);
marca[v] := "visitado";
Apilar(v, P);
mientras no Pvacia(P) hacer
var u: nodo;
u := Cima(P); // No desapilar aún
var encontrado_adyacente_no_visitado: booleano;
encontrado_adyacente_no_visitado := falso;
para cada w adyacente a u hacer
si marca[w] <> "visitado" entonces
marca[w] := "visitado";
Apilar(w, P);
encontrado_adyacente_no_visitado := verdadero;
salir del para; // Solo apilar uno y continuar la exploración desde él
fin si
fin para;
si no encontrado_adyacente_no_visitado entonces
Desapilar(P); // Si no hay más adyacentes no visitados, desapilar
fin si
fin mientras
fin procedimiento
Procedimiento BFS (Recorrido en Amplitud)
procedimiento BFS(v: nodo)
var C: Cola;
var marca: array; // Se asume inicializada a "no visitado"
crearC(C);
marca[v] := "visitado";
insertar(v, C); // Insertar en cola
mientras no Cvacia(C) hacer
var u: nodo;
u := QuitarPrimero(C);
escribir(u); // O procesar el nodo
para cada w adyacente a u hacer
si marca[w] <> "visitado" entonces
marca[w] := "visitado";
insertar(w, C);
fin si
fin para
fin mientras
fin procedimiento
