SOLUCIÓN DE EJERCICIOS
MATEMÁTICAS DISCRETAS – JOHNSONBAUGH 6 EDICIÓN
SOLUCIÓN PROBLEMA 40 CAPÍTULO 1.7 MATEMÁTICAS DISCRETAS JOHNSONBAUGH 6 EDICIÓN
40. Pruebe que, después de que termina el siguiente seudocódigo, a[h] = val; para toda p, i ≤ p < h, a[p] < val; y para toda p, h < p ≤ j, a[p] ≥ val. En particular, val está en la posición en el arreglo a[i], . . . , a[j] donde estaría si el arreglo fuera ordenado.
val = a[i ]
h = i
for k = i + 1 to j
if (a[k] < val) {
h = h + 1
swap(a[h], a[k])
}
swap(a[i ], a[h])
Sugerencia: Use el ciclo invariante: para toda p, i < p ≤ h, a[p] < val; y para toda p, h < p < k, a[p] ≥ val. (Un dibujo ayuda). Esta técnica se llama particionar. Esta versión particular se debe a Nico Lomuto. Las particiones se emplean para encontrar el k-ésimo, elemento más pequeño en cualquier arreglo y para construir un algoritmo para ordenar llamado quicksort. Un septomino en 3D es un cubo de tres dimensiones de 2 × 2 × 2 sin una esquina de 1 × 1 × 1. Un cubo deficiente es un cubo de k × k × k sin un cubo de 1 × 1 × 1.
Solución:
Solución 1: Canal
¿Te sirvió el ejercicio? Compártelo
¿Tienes Dudas u otra solución que agregar? Comenta
¿El ejercicio aún no está resuelto? Solicítalo comentando aquí y nuestra comunidad lo resolverá rápidamente. Si tienes la solución ¡Envíala! La comunidad estará agradecida.
¿Quiéres el ejercicio resuelto en menos de 48 horas? Paga desde $US 4 (4 DÓLARES) vía PayPal o desde $ 10.000 pesos (colombianos) vía Nequi si estás en Colombia, comunicándote al whatsapp +573203806207 para confirmar pago, y tendrás el ejercicio resuelto.
Un comentario en “Ejercicio 40 Capítulo 1.7 Matemáticas Discretas Johnsonbaugh 6 edición”