Ejercicio 40 Capítulo 1.7 Matemáticas Discretas Johnsonbaugh 6 edición

¿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.

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.