SOLUCIÓN AO PROBLEMA DE COMO CRUZAR UN RÍO POR UNHA PONTE
Problema-solución / Imaxe: marketingdirecto.com/
Lembrades a pregunta do problema? Como realizarán os cruces, dun a outro lado do río, para tardar o mínimo tempo posible en cruzalo todos? Calcular tamén o tempo mínimo para o caso de n persoas.
Resolvéstelo? Imos ver a solución:
Chamaremos “beira A” á beira no que inicialmente se atopan e “beira B” á beira contraria, que será o do destino. Tamén denotaremos a cada persoa polo tempo que tarda en cruzar.
A estratexia que leva ao tempo mínimo consiste no seguinte:
- Se as dúas persoas 1 e 2 atópanse na “beira A”, cruzarán ambas.
- Se algunha das persoas 1 e 2 atópanse na “beira B”, cruzará a persoa 1 para devolver a lanterna ás da “beira A”.
- Se só una das persoas 1 ou 2 atópanse na “beira A”, cruzarán as dúas persoas que máis tempo tardan.
Con esta estratexia, podemos establecer a seguinte fórmula recursiva:
T(n) = T(n – 2) + n + 5.
Para iso, con n persoas, pasan primeiro as persoas 1 e 2 (dous minutos), volve a persoa 1 (un minuto), pasan as persoas n e n – 1 ( n minutos) e volve a persoa 2 (dous minutos). Neste momento, o problema redúcese ao de n – 2 persoas.
Aplicando sucesivamente esta fórmula, obtense a fórmula explícita
T(2 n + 1) = n2 + 7 n – 2; T(2 n) = n2 + 6 n – 5.
No caso proposto (n = 5), é T = 16 minutos.
FONTE: zientzia-astea.org/es
0 comentarios