Diferencia entre revisiones de «Práctica 1: Inducción (Algoritmos III)»
De Cuba-Wiki
Sin resumen de edición |
|||
| Línea 1: | Línea 1: | ||
==Ejercicio 01.01:== | ==Ejercicio 01.01:== | ||
<br>a) | <br>a) | ||
P(n) = Σ<sub>i=1..n</sub> i = n(n+1)/2 | |||
* CB: n = 1 | |||
Σ<sub>i=1..1</sub> i = 1 | |||
1(1+1)/2 = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ<sub>i=1..n+1</sub> i = Σ<sub>i=1..n</sub> i + n+1 = (HI) n(n+1)/2 + 2(n+1)/2 = (n+2)(n+1)/2 OK | |||
<br>b) | <br>b) | ||
P(n) = Σ<sub>i=0..n</sub> (2*i+1) = (n+1)<sup>2</sup> | |||
* CB: n = 0 | |||
Σ<sub>i=0..0</sub> (2*i+1) = 1 | |||
(0+1)<sup>2</sup> = 1 OK | |||
* PI: P(n)=>P(n+1) | |||
Σ<sub>i=0..n+1</sub> (2*i+1) = Σ<sub>i=0..n</sub> 2*i+1 + 2*(n+1)+1 = (HI) (n+1)<sup>2</sup> + 2n + 3 = n<sup>2</sup> + 2*n + 1 + 2n + 3 = n<sup>2</sup> + 4*n + 4 = (n+2)<sup>2</sup> OK | |||
<br>c) | <br>c) | ||
<br>d) | <br>d) | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
==Ejercicio 01.02:== | ==Ejercicio 01.02:== | ||
HI = Σ<sub>i=0..n</sub> 2<sup>i</sup> = 2<sup>n+1</sup>-1 | HI = Σ<sub>i=0..n</sub> 2<sup>i</sup> = 2<sup>n+1</sup>-1 | ||
Revisión del 21:18 11 nov 2006
Ejercicio 01.01:
a)
P(n) = Σi=1..n i = n(n+1)/2
- CB: n = 1
Σi=1..1 i = 1 1(1+1)/2 = 1 OK
- PI: P(n)=>P(n+1)
Σi=1..n+1 i = Σi=1..n i + n+1 = (HI) n(n+1)/2 + 2(n+1)/2 = (n+2)(n+1)/2 OK
b)
P(n) = Σi=0..n (2*i+1) = (n+1)2
- CB: n = 0
Σi=0..0 (2*i+1) = 1 (0+1)2 = 1 OK
- PI: P(n)=>P(n+1)
Σi=0..n+1 (2*i+1) = Σi=0..n 2*i+1 + 2*(n+1)+1 = (HI) (n+1)2 + 2n + 3 = n2 + 2*n + 1 + 2n + 3 = n2 + 4*n + 4 = (n+2)2 OK
c)
d)
e)
f)
Ejercicio 01.02:
HI = Σi=0..n 2i = 2n+1-1
- CB: n = 0
Σi=0..0 2i = 1
20+1-1 = 2-1 = 1 OK
- PI: P(n)=>P(n+1)
Σi=0..n+1 2i = Σi=0..n 2i + 2n+1 = (HI) 2n+1-1 + 2n+1 = 2 * 2n+1-1 = 2n+2-1 OK
