Exercicis de pensament computacional — Matemàtiques 1r Batxillerat

Q: Què és una funció recursiva i què és el cas base?

Una funció recursiva es crida a ella mateixa per resoldre un problema més petit. El cas base és l'entrada més senzilla, que es resol directament i fa que la recursió s'aturi; sense cas base, la funció no acabaria mai.

Q: Com es compara l'eficiència de dos algorismes?

Comptant les operacions que fan en funció de la mida n de les dades: per exemple, n, n(n−1)/2 o 2^n. Dos algorismes poden donar el mateix resultat però un tardar moltíssim més que l'altre quan n és gran.

Q: Per què un algorisme numèric s'atura quan dues aproximacions consecutives estan molt properes?

Perquè això indica que ja s'ha assolit la precisió que es volia. Es fa servir un llindar (per exemple, una milionèsima) i no una igualtat exacta, perquè els ordinadors treballen amb un nombre finit de decimals.

Q: Té a veure aquest tema amb la programació real?

Sí. Els mateixos algorismes (cerca, ordenació, bisecció, recursió) es fan servir en qualsevol llenguatge. Aquí s'escriuen en pseudocodi per concentrar-se en la idea i no en la sintaxi.

Aquest tema uneix les matemàtiques amb la informàtica: llegir un algorisme, seguir-ne l'execució i raonar si és correcte i eficient. Els algorismes s'escriuen en pseudocodi i no cal cap llenguatge de programació. Començaràs amb traces de bucles, condicionals i funcions recursives senzilles, com el factorial. Després treballaràs mètodes numèrics, com Horner, el mètode babilònic de l'arrel quadrada, la bisecció, les sumes de rectangles i la iteració de punt fix, que enllacen amb funcions, successions i límits. Als exercicis avançats compararàs el cost de diferents algorismes (recursió contra taula), ordenaràs una llista per selecció, derivaràs numèricament i justificaràs un algorisme amb un invariant. Errors típics: equivocar-te d'una volta al principi o al final del bucle, oblidar el cas base d'una recursió i dir que dos algorismes són iguals només perquè donen el mateix resultat.

Tens examen d'aquest tema? Fes un simulacre de 60 minuts com el de l'institut, amb solucions i criteris de correcció.Fes el simulacre →

Nivell bàsic

Exercici 1

Fes la traça de l'algorisme següent per a la llista L = (3, −2, 7, −5, 0, 4, −1) i digues què mostra:
s ← 0
c ← 0
per cada x de L
si x > 0 llavors s ← s + x
si no, si x < 0 llavors c ← c + 1
mostra s i c
a) Anota els valors de s i c després de tractar cada element.
b) Què calcula s i què calcula c?
c) Què passa amb el 0? Quina modificació caldria si volguéssim comptar-lo amb els negatius?

Mira la solucióAmaga la solucióde l'exercici 1

Apartat a)

Resultat

(s, c)

: (3, 0), (3, 1), (10, 1), (10, 2), (10, 2), (14, 2), (14, 3). Mostra

s = 14

c = 3

Resolució

Dades. Comences amb s = 0 i c = 0 i tractes els elements de L en ordre: si x > 0, sumes x a s; si no, si x < 0, sumes 1 a c.
Traça.
x s c
3 3 0
−2 3 1
7 10 1
−5 10 2
0 10 2
4 14 2
−1 14 3
El 0. Quan x = 0 no es compleix cap de les dues condicions, i s i c no canvien.
Conclusió. En acabar la llista, l'algorisme mostra s = 14 i c = 3.

x	s	c
3	3	0
−2	3	1
7	10	1
−5	10	2
0	10	2
4	14	2
−1	14	3

Apartat b)

Resultat

s és la suma dels elements positius (14) i c és el nombre d'elements negatius (3).

Resolució

Què fa s. Només canvia quan x > 0, i hi suma el valor de x: s = 3 + 7 + 4 = 14.
Què fa c. Només canvia quan x < 0, i hi suma 1 (no el valor): és un comptador dels negatius −2, −5 i −1.
Conclusió. s acumula la suma dels positius i c compta quants negatius hi ha.

Apartat c)

Resultat

El 0 no entra a cap condició i l'algorisme l'ignora; per comptar-lo amb els negatius, la segona condició ha de ser «si x ≤ 0» (i llavors

c = 4

Resolució

El 0. El 0 no és ni positiu ni negatiu: no compleix x > 0 ni x < 0, de manera que no modifica ni s ni c.
Modificació. Canvia la segona condició per «si no, si x ≤ 0 llavors c ← c + 1».
Nou resultat. Ara c compta −2, −5, 0 i −1, és a dir c = 4, i s continua valent 14.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 2

Considera l'algorisme:
n ← 1
per k des d'1 fins a 5
n ← n · k
mostra n
a) Fes la traça i digues què mostra.
b) Quina funció matemàtica calcula? Què mostraria si el bucle arribés fins a 8?
c) Què mostraria si el bucle anés de l'1 al 0 (no s'executés mai)? Té sentit amb la definició matemàtica?

Mira la solucióAmaga la solucióde l'exercici 2

Apartat a)

Resultat

n: 1, 2, 6, 24, 120. Mostra 120.

Resolució

Dades. n comença valent 1 i a cada volta es multiplica pel valor de k, que va d'1 a 5.
Traça.
k n
1 1 · 1 = 1
2 1 · 2 = 2
3 2 · 3 = 6
4 6 · 4 = 24
5 24 · 5 = 120
Conclusió. Quan acaba el bucle, mostra 120.

k	n
1	1 · 1 = 1
2	1 · 2 = 2
3	2 · 3 = 6
4	6 · 4 = 24
5	24 · 5 = 120

Apartat b)

Resultat

Calcula el factorial:

5! = 120

. Fins a 8 mostraria

8! = 40\,320

Resolució

Què calcula. El resultat és el producte de tots els enters d'1 a 5: $n = 1\cdot 2\cdot 3\cdot 4\cdot 5 = 5! = 120$
Fins a 8. El bucle multiplicaria també per 6, 7 i 8: $8! = 120\cdot 6\cdot 7\cdot 8 = 40\,320$ .
Conclusió. En general, si el bucle va d'1 fins a m, l'algorisme mostra m!.

Apartat c)

Resultat

Mostraria 1; coincideix amb la convenció

0! = 1

Resolució

Bucle buit. Si el bucle no s'executa mai, n no es modifica i conserva el valor inicial 1, que és el que mostra.
Definició matemàtica. Té sentit: per conveni, $0! = 1$ (el producte de zero factors val 1).
Conclusió. Per això s'inicialitza n a 1 i no a 0: amb 0, tot el producte seria 0, valgués el que valgués k.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 3

Es vol estudiar la funció f(x) = $x^{2}$ − x − 6 amb aquest algorisme:
per x des de −3 fins a 4
    y ← $x^{2}$ − x − 6
    si y = 0 mostra «arrel: » i x
    si y < 0 augmenta el comptador n
(El comptador n comença a 0.)
a) Calcula f(x) per a cada valor de x.
b) Quines arrels mostra l'algorisme?
c) Quin valor té n al final i què significa?

Mira la solucióAmaga la solucióde l'exercici 3

Apartat a)

Resultat

f(−3) = 6; f(−2) = 0; f(−1) = −4; f(0) = −6; f(1) = −6; f(2) = −4; f(3) = 0; f(4) = 6.

Resolució

Dades. El bucle recorre els enters de −3 a 4 i calcula $y = x^{2} - x - 6$ per a cada un.
Càlcul.
x −3 −2 −1 0 1 2 3 4
f(x) 6 0 −4 −6 −6 −4 0 6
Exemple. $f(-3) = 9 + 3 - 6 = 6$ i $f(-1) = 1 + 1 - 6 = -4$ . Fixa't que la taula és simètrica respecte de $x = \tfrac{1}{2}$ , el vèrtex de la paràbola.

x	−3	−2	−1	0	1	2	3	4
f(x)	6	0	−4	−6	−6	−4	0	6

Apartat b)

Resultat

Mostra «arrel: −2» i «arrel: 3».

Resolució

Condició. L'algorisme mostra x quan y = 0.
Càlcul. A la taula, f(x) = 0 només per a x = −2 i x = 3.
Comprovació. Factoritzant, $x^{2} - x - 6 = (x - 3)(x + 2)$ , que s'anul·la per a x = 3 i x = −2.

Apartat c)

Resultat

n = 4

: compta els enters de l'interval on

x^{2} - x - 6 \lt 0

, és a dir, de (−2, 3).

Resolució

Comptador. n augmenta cada vegada que y < 0.
Càlcul. f(x) és negatiu per a x = −1, 0, 1 i 2, per tant n = 4.
Significat. $(x - 3)(x + 2) \lt 0$ quan els dos factors tenen signes oposats, és a dir, si $-2 \lt x \lt 3$ . Per tant, n compta els enters que verifiquen $x^{2} - x - 6 \lt 0$ .

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 4

Considera l'algorisme:
x ← 100
k ← 0
mentre x > 1
x ← $\tfrac{x}{2}$
k ← k + 1
mostra k i x
a) Fes la traça dels valors successius de x.
b) Què mostra l'algorisme?
c) Relaciona el valor de k amb una potència de 2.

Mira la solucióAmaga la solucióde l'exercici 4

Apartat a)

Resultat

x: 100 → 50 → 25 → 12,5 → 6,25 → 3,125 → 1,5625 → 0,78125.

Resolució

Dades. Mentre x > 1, x es divideix entre 2 i k augmenta en 1.
Traça.
k 0 1 2 3 4 5 6 7
x 100 50 25 12,5 6,25 3,125 1,5625 0,78125
Condició de sortida. Hi ha 7 divisions: quan x = 0,78125, la condició x > 1 és falsa i el bucle s'atura.

k	0	1	2	3	4	5	6	7
x	100	50	25	12,5	6,25	3,125	1,5625	0,78125

Apartat b)

Resultat

Mostra

k = 7

x = 0{,}78125

Resolució

Valors finals. El bucle ha fet 7 voltes, de manera que k = 7, i l'últim valor de x és 0,78125.
Comprovació. $x = \dfrac{100}{2^{7}} = \dfrac{100}{128} = 0{,}78125$ .

Apartat c)

Resultat

k és el menor enter amb

2^{k} \geq 100

k = \lceil \log_{2} 100\rceil = 7

Resolució

Plantejament. Després de k voltes, $x = \tfrac{100}{2^{k}}$ . El bucle s'atura la primera vegada que $\tfrac{100}{2^{k}} \leq 1$ , és a dir, quan $2^{k} \geq 100$ .
Potències de 2. Com que $2^{6} = 64 \lt 100 \leq 128 = 2^{7}$ , el menor k és 7.
Conclusió. En general $k = \lceil \log_{2} 100\rceil = 7$ : l'algorisme compta quantes vegades cal dividir per 2 per baixar d'1.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 5

Compta quantes vegades s'executa l'ordre interior:
n ← 10
compta ← 0
per i des d'1 fins a n
per j des de i fins a n
compta ← compta + 1
mostra compta
a) Quantes voltes fa el bucle interior quan i = 1, i = 2 i i = 10?
b) Quin valor mostra?
c) Dona una fórmula en funció de n i aplica-la per a n = 100.

Mira la solucióAmaga la solucióde l'exercici 5

Apartat a)

Resultat

i = 1: 10 voltes; i = 2: 9 voltes; i = 10: 1 volta.

Resolució

Dades. Per a cada i, el bucle interior fa córrer j des de i fins a 10, és a dir, fa 10 − i + 1 voltes.
Càlcul. Quan i = 1, j va d'1 a 10: 10 voltes. Quan i = 2, de 2 a 10: 9 voltes. Quan i = 10, j només val 10: 1 volta.

Apartat b)

Resultat

Mostra 55.

Resolució

Plantejament. compta suma 1 cada vegada que s'executa l'ordre interior, per tant val la suma de les voltes de tots els i.
Càlcul. $10 + 9 + 8 + \dots + 1 = 55$

Apartat c)

Resultat

\text{compta} = \dfrac{n(n + 1)}{2}

; per a

n = 100

5050

repeticions.

Resolució

Fórmula. En general, compta = n + (n − 1) + … + 1, la suma dels n primers naturals: $n + (n-1) + \dots + 1 = \dfrac{n(n + 1)}{2}$
Comprovació. Per a n = 10: $\tfrac{10\cdot 11}{2} = 55$ , com a l'apartat b.
Càlcul. Per a n = 100: $\dfrac{100\cdot 101}{2} = 5050$ repeticions.
Conclusió. El nombre d'operacions creix com $n^{2}$ : si dobles n, la feina es multiplica gairebé per 4.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 6

Un programa decideix en quin quadrant del pla cartesià hi ha un punt (x, y):
si x = 0 o y = 0 mostra «sobre un eix»
si no, si x > 0 i y > 0 mostra «primer quadrant»
si no, si x < 0 i y > 0 mostra «segon quadrant»
si no, si x < 0 i y < 0 mostra «tercer quadrant»
si no mostra «quart quadrant»
Digues què mostra per als punts (−3, 2), (4, −1), (0, 5) i (−2, −2). Per què l'última línia no necessita cap condició?

Mira la solucióAmaga la solucióde l'exercici 6

Resultat

(−3, 2): «segon quadrant»; (4, −1): «quart quadrant»; (0, 5): «sobre un eix»; (−2, −2): «tercer quadrant». L'última línia no necessita condició perquè l'únic cas que queda és x > 0 i y < 0.

Resolució

Funcionament. Les condicions es proven en ordre i només s'executa la primera que és certa; les altres ja no es miren.
(−3, 2). x ≠ 0 i y ≠ 0; «x > 0 i y > 0» és fals; «x < 0 i y > 0» és cert: mostra «segon quadrant».
(4, −1). No és sobre cap eix, ni al primer, ni al segon, ni al tercer quadrant (x > 0): arriba a l'última línia i mostra «quart quadrant».
(0, 5) i (−2, −2). Per a (0, 5), x = 0 i mostra «sobre un eix». Per a (−2, −2), x < 0 i y < 0: mostra «tercer quadrant».
L'última línia. Si s'hi arriba, ja s'han descartat els eixos (x ≠ 0, y ≠ 0) i els tres primers quadrants. L'única combinació de signes que queda és x > 0 i y < 0, que és el quart quadrant: no cal comprovar-ho.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 7

Un programa recorre els enters de l'1 al 30 i compta els que verifiquen la condició «n és múltiple de 3 i n no és múltiple de 5».
a) Avalua la condició per a n = 12, n = 15 i n = 10.
b) Quins nombres de l'1 al 30 la compleixen? Quants són?
c) Escriu una condició equivalent amb «o» en comptes de «i», si afegim la negació de tota la frase (llei de De Morgan).

Mira la solucióAmaga la solucióde l'exercici 7

Apartat a)

Resultat

n = 12: certa; n = 15: falsa; n = 10: falsa.

Resolució

Condició. És una conjunció «A i no B», amb A = «n és múltiple de 3» i B = «n és múltiple de 5». Només és certa si les dues parts ho són.
n = 12. És múltiple de 3 (sí) i no és múltiple de 5 (sí): certa.
n = 15. És múltiple de 3, però també de 5, per tant «no múltiple de 5» és fals: falsa.
n = 10. No és múltiple de 3: la primera part ja és falsa, i la condició és falsa.

Apartat b)

Resultat

La compleixen 3, 6, 9, 12, 18, 21, 24 i 27: són 8 nombres.

Resolució

Múltiples de 3. De l'1 al 30 n'hi ha 10: 3, 6, 9, 12, 15, 18, 21, 24, 27 i 30.
Exclusions. D'aquests, són múltiples de 5 el 15 i el 30 (múltiples de 15), que no compleixen la condició.
Conclusió. Queden 10 − 2 = 8 nombres: 3, 6, 9, 12, 18, 21, 24 i 27.

Apartat c)

Resultat

La condició equival a «no (n no és múltiple de 3 o n és múltiple de 5)».

Resolució

Llei de De Morgan. La negació d'una «i» és la «o» de les negacions: no(A i C) = (no A) o (no C).
Aplicació. La negació de «A i no B» és «no A o B»: un nombre NO compleix la condició si «n no és múltiple de 3 o n és múltiple de 5».
Condició equivalent. Negant tota la frase un altre cop, la condició original és «no (n no és múltiple de 3 o n és múltiple de 5)».
Comprovació. Per a n = 15 es compleix «n no és múltiple de 3 o n és múltiple de 5» (és múltiple de 5), i per tant la condició original és falsa, com has vist a l'apartat a.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 8

L'Aina vol calcular la suma dels n primers termes de la progressió aritmètica de primer terme 3 i diferència 4 (3, 7, 11, 15, 19, …), però el seu programa dona un valor erroni:
demana n
s ← 0
per i des d'1 fins a n − 1
s ← s + (3 + 4 · (i − 1))
mostra s
a) Què mostra per a n = 5?
b) Quin és el valor correcte i quin és l'error?
c) Comprova el valor correcte amb la fórmula S = n( $a_{1}$ + $a_{n}$ )/2.

Mira la solucióAmaga la solucióde l'exercici 8

Apartat a)

Resultat

Mostra 36.

Resolució

Dades. El terme i-èsim que se suma és 3 + 4 · (i − 1). Amb n = 5, el bucle va d'1 fins a n − 1 = 4.
Càlcul. Suma els termes per a i = 1, 2, 3 i 4: $3 + 7 + 11 + 15 = 36$

Apartat b)

Resultat

El valor correcte és 55. L'error és «de fora d'un»: el bucle ha d'anar fins a n, no fins a n − 1.

Resolució

Valor correcte. Els 5 primers termes són 3, 7, 11, 15 i 19, que sumen 55.
Error. El bucle s'atura a n − 1 i no suma l'últim terme (el 19). És un error típic «de fora d'un» (off-by-one).
Correcció. Cal posar «per i des d'1 fins a n».

Apartat c)

Resultat

a_{5} = 19

S = \dfrac{5\cdot(3 + 19)}{2} = 55

: coincideix.

Resolució

Terme general. En una progressió aritmètica, $a_{n} = a_{1} + (n - 1)d$ : $a_{5} = 3 + 4\cdot 4 = 19$ .
Suma. $S = \dfrac{n(a_{1} + a_{n})}{2} = \dfrac{5\cdot(3 + 19)}{2} = \dfrac{5\cdot 22}{2} = 55$
Conclusió. Coincideix amb el valor del programa corregit.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 9

Una funció recursiva es defineix a partir d'ella mateixa:
funció fact(n)
si n = 0 retorna 1
si no retorna n · fact(n − 1)
a) Desplega la crida fact(5) fins al cas base i després recorre el camí de tornada per obtenir el resultat.
b) Quantes crides a fact es fan en total?
c) Què passaria si es cridés fact(−1)?

Mira la solucióAmaga la solucióde l'exercici 9

Apartat a)

Resultat

\text{fact}(5) = 120

Resolució

Anada. Cada crida en fa una altra amb n − 1: fact(5) = 5 · fact(4); fact(4) = 4 · fact(3); fact(3) = 3 · fact(2); fact(2) = 2 · fact(1); fact(1) = 1 · fact(0).
Cas base. fact(0) = 1: aquí s'atura la recursió.
Tornada. Es van completant els productes pendents: fact(1) = 1 · 1 = 1; fact(2) = 2 · 1 = 2; fact(3) = 3 · 2 = 6; fact(4) = 4 · 6 = 24; fact(5) = 5 · 24 = 120.

Apartat b)

Resultat

Es fan 6 crides (en general, n + 1).

Resolució

Recompte. Es crida fact(5), fact(4), fact(3), fact(2), fact(1) i fact(0): 6 crides.
En general. fact(n) fa una crida per a cada valor de n fins a 0, és a dir, n + 1 crides.

Apartat c)

Resultat

La recursió no s'aturaria mai: no s'arriba mai al cas base (en un ordinador real, error de desbordament de pila).

Resolució

Crides. fact(−1) cridaria fact(−2), després fact(−3), etc.: n va disminuint i mai no arriba a 0.
Conseqüència. La recursió no s'aturaria; en un ordinador real, la pila de crides s'ompliria i el programa acabaria amb un error de desbordament de pila.
Conclusió. Tota funció recursiva necessita un cas base al qual s'arribi sempre. Aquí es podria protegir amb «si n < 0, error».

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 10

Es vol calcular la mitjana d'una llista de nombres amb aquest algorisme:
demana la llista L, que té n elements
s ← 0
per cada x de L
s ← s + x
mostra s / n
a) Fes la traça per a L = (4, 8, 9, 15).
b) Què passaria si L fos la llista buida? Com ho evitaries?

Mira la solucióAmaga la solucióde l'exercici 10

Apartat a)

Resultat

s: 0 → 4 → 12 → 21 → 36; mostra

\tfrac{36}{4} = 9

Resolució

Dades. L = (4, 8, 9, 15), per tant n = 4; s comença a 0 i hi vas sumant cada element.
Traça. s: 0 → 4 → 12 → 21 → 36.
Resultat. Mostra $\dfrac{s}{n} = \dfrac{36}{4} = 9$ , que és la mitjana.

Apartat b)

Resultat

Amb la llista buida, n = 0 i es dividiria entre 0: error. S'evita amb una condició «si n = 0 mostra «no hi ha dades»».

Resolució

Llista buida. El bucle no s'executa, s = 0 i n = 0: l'última línia calcula 0 / 0.
Problema. La divisió entre 0 no està definida: el programa donaria un error (o un resultat sense sentit).
Solució. Afegeix una condició abans de dividir: «si n = 0 mostra «no hi ha dades»; si no mostra s / n».

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Nivell intermedi

Exercici 11

El mètode de Horner avalua un polinomi estalviant operacions. Per a p(x) = 2x³ − 5x² + 3x − 7:
b ← 2
b ← b · x − 5
b ← b · x + 3
b ← b · x − 7
mostra b
a) Fes la traça per a x = 3.
b) Comprova el resultat avaluant p(3) directament.
c) Quantes multiplicacions fa l'algorisme de Horner i quantes si avaluem els monomis un per un calculant cada potència per separat amb productes?

Mira la solucióAmaga la solucióde l'exercici 11

Apartat a)

Resultat

b: 2 → 1 → 6 → 11. Mostra 11.

Resolució

Dades. x = 3 i b comença valent el coeficient principal, 2. Cada pas fa b ← b · x + (coeficient següent).
Traça. $b = 2$ ; $b = 2\cdot 3 - 5 = 1$ ; $b = 1\cdot 3 + 3 = 6$ ; $b = 6\cdot 3 - 7 = 11$ .
Per què funciona. És el polinomi escrit de manera niuada: $p(x) = ((2x - 5)x + 3)x - 7$ .

Apartat b)

Resultat

p(3) = 54 - 45 + 9 - 7 = 11

: coincideix.

Resolució

Càlcul directe. $p(3) = 2\cdot 27 - 5\cdot 9 + 3\cdot 3 - 7 = 54 - 45 + 9 - 7 = 11$
Conclusió. Coincideix amb el valor que dona el mètode de Horner.

Apartat c)

Resultat

Horner fa 3 multiplicacions; avaluant monomi a monomi, 6.

Resolució

Horner. Hi ha una multiplicació per pas, i hi ha 3 passos: 3 multiplicacions.
Monomi a monomi. $2x^{3}$ : 2 productes per a $x^{3}$ i 1 pel coeficient (3); $-5x^{2}$ : 1 + 1 = 2; $3x$ : 1. En total, 3 + 2 + 1 = 6 multiplicacions.
Conclusió. Horner n'estalvia la meitat, i la diferència creix amb el grau (ho veuràs a l'exercici 17).

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 12

El mètode babilònic aproxima $\sqrt{a}$ amb aquest algorisme:
x ← valor inicial
repeteix 3 vegades
x ← $\tfrac{(x + a / x)}{2}$
mostra x
a) Aplica'l a a = 10 amb valor inicial x = 3 i anota x després de cada repetició (6 decimals).
b) Compara amb $\sqrt{10}$ = 3,162278 (6 decimals) i digues quin error té cada pas.
c) Per què té sentit que x i a / x siguin dues aproximacions de $\sqrt{a}$ , una per excés i una per defecte?

Mira la solucióAmaga la solucióde l'exercici 12

Apartat a)

Resultat

x: 3,166667 → 3,162281 → 3,162278.

Resolució

Dades. a = 10 i x = 3; cada repetició fa $x \leftarrow \dfrac{x + a/x}{2}$ .
Pas 1. $\dfrac{3 + 10/3}{2} = \dfrac{3 + 3{,}333333}{2} = 3{,}166667$ .
Pas 2. $\dfrac{3{,}166667 + 10/3{,}166667}{2} = \dfrac{3{,}166667 + 3{,}157895}{2} = 3{,}162281$ .
Pas 3. $\dfrac{3{,}162281 + 10/3{,}162281}{2} = 3{,}162278$ . Mostra x = 3,162278.

Apartat b)

Resultat

Errors: pas 1, 0,004389; pas 2, 0,000003; pas 3, menys d'una milionèsima.

Resolució

Error. L'error de cada pas és la diferència amb $\sqrt{10} \approx 3{,}162278$ .
Càlcul. Pas 1: 3,166667 − 3,162278 = 0,004389. Pas 2: 3,162281 − 3,162278 = 0,000003. Pas 3: menys d'1 milionèsim (ja coincideixen els 6 decimals).
Interpretació. L'error baixa molt de pressa: aproximadament s'eleva al quadrat a cada pas (el nombre de decimals correctes gairebé es dobla).

Apartat c)

Resultat

x \lt \sqrt{a}

, aleshores

a/x \gt \sqrt{a}

(i al revés), perquè

x\cdot \tfrac{a}{x} = a

; la mitjana queda entremig, més a prop de l'arrel.

Resolució

Producte. x i a/x multipliquen a: $x\cdot \tfrac{a}{x} = a = \sqrt{a}\cdot\sqrt{a}$ .
Raonament. Si x és més petit que $\sqrt{a}$ , llavors a/x ha de ser més gran que $\sqrt{a}$ perquè el producte sigui a; i al revés. Una és per defecte i l'altra per excés.
Exemple. Amb x = 3: $3 \lt \sqrt{10} \lt 10/3 = 3{,}333$ .
Conclusió. La seva mitjana queda entremig de les dues, més a prop de l'arrel: per això cada pas millora l'aproximació.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 13

El mètode de la bisecció cerca una arrel d'una funció contínua en un interval [a, b] on f(a) i f(b) tenen signes diferents:
repeteix
    m ← $\tfrac{(a + b)}{2}$
    si f(a) · f(m) ≤ 0 llavors b ← m
    si no a ← m
Aplica'l 4 vegades a f(x) = $x^{3}$ + x − 3 a l'interval [1, 2].
a) Comprova que f(1) i f(2) tenen signes diferents i digues per què hi ha una arrel.
b) Anota m i f(m) en cada repetició, i l'interval resultant.
c) Quina amplada té l'interval final? Dona una aproximació de l'arrel amb l'error màxim.

Mira la solucióAmaga la solucióde l'exercici 13

Apartat a)

Resultat

f(1) = −1 < 0 i f(2) = 7 > 0; com que f és contínua, pel teorema de Bolzano té una arrel a (1, 2).

Resolució

Càlcul. $f(1) = 1 + 1 - 3 = -1$ i $f(2) = 8 + 2 - 3 = 7$ : signes diferents.
Teorema de Bolzano. Si f és contínua a [a, b] i f(a) i f(b) tenen signes oposats, hi ha almenys un c ∈ (a, b) amb f(c) = 0.
Conclusió. f és un polinomi, per tant contínua: hi ha almenys una arrel a (1, 2).

Apartat b)

Resultat

m = 1,5 (f = 1,875) → [1; 1,5]; m = 1,25 (f = 0,203125) → [1; 1,25]; m = 1,125 (f = −0,451172) → [1,125; 1,25]; m = 1,1875 (f = −0,137939) → [1,1875; 1,25].

Resolució

Regla. Com que f(a) < 0, si f(m) > 0 l'arrel és a [a, m] (b ← m); si f(m) < 0 és a [m, b] (a ← m).
Repeticions.
m f(m) interval
1 1,5 1,875 > 0 [1; 1,5]
2 1,25 0,203125 > 0 [1; 1,25]
3 1,125 −0,451172 < 0 [1,125; 1,25]
4 1,1875 −0,137939 < 0 [1,1875; 1,25]
Exemple de càlcul. $f(1{,}25) = 1{,}953125 + 1{,}25 - 3 = 0{,}203125$ .

	m	f(m)	interval
1	1,5	1,875 > 0	[1; 1,5]
2	1,25	0,203125 > 0	[1; 1,25]
3	1,125	−0,451172 < 0	[1,125; 1,25]
4	1,1875	−0,137939 < 0	[1,1875; 1,25]

Apartat c)

Resultat

Amplada

0{,}0625 = \tfrac{1}{16}

; arrel

\approx 1{,}21875

amb error màxim

0{,}03125

Resolució

Amplada. 1,25 − 1,1875 = 0,0625 = 1/16. Cada repetició divideix l'amplada per 2: $\tfrac{1}{2^{4}} = \tfrac{1}{16}$ .
Aproximació. Prenent el punt mitjà, 1,21875, l'error és com a molt la meitat de l'amplada: 0,03125.
Comprovació. L'arrel real és 1,2134…, que efectivament és a [1,1875; 1,25] i a menys de 0,03125 de 1,21875.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 14

La funció següent calcula els nombres de Fibonacci de manera recursiva:
funció fib(n)
si n < 2 retorna n
si no retorna fib(n − 1) + fib(n − 2)
a) Calcula fib(6) i anota els valors de fib(2), fib(3), fib(4) i fib(5).
b) Dibuixa mentalment l'arbre de crides de fib(4) i compta quantes crides fa. Compta ara les de fib(6): n'hi ha 25.
c) Per a fib(20) es fan 21.891 crides, però només hi ha 21 valors diferents que calcular. Què es repeteix i com ho podries millorar?

Mira la solucióAmaga la solucióde l'exercici 14

Apartat a)

Resultat

\text{fib}(2) = 1

\text{fib}(3) = 2

\text{fib}(4) = 3

\text{fib}(5) = 5

\text{fib}(6) = 8

Resolució

Casos base. Si n < 2, fib(n) = n: fib(0) = 0 i fib(1) = 1.
Càlcul. Cada valor és la suma dels dos anteriors: fib(2) = 1 + 0 = 1; fib(3) = 1 + 1 = 2; fib(4) = 2 + 1 = 3; fib(5) = 3 + 2 = 5; fib(6) = 5 + 3 = 8.

Apartat b)

Resultat

fib(4) fa 9 crides; fib(6), 25, d'acord amb C(n) = 1 + C(n − 1) + C(n − 2).

Resolució

Arbre de fib(4). Hi ha una crida a fib(4); aquesta en fa una a fib(3) i una a fib(2); fib(3) en fa a fib(2) i fib(1); cada fib(2) (n'hi ha dues) fa fib(1) i fib(0).
Recompte. 1 (fib(4)) + 1 (fib(3)) + 2 (fib(2)) + 3 (fib(1)) + 2 (fib(0)) = 9 crides.
Recurrència. Si C(n) és el nombre de crides, C(n) = 1 + C(n − 1) + C(n − 2), amb C(0) = C(1) = 1.
Càlcul. C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15 i C(6) = 1 + 15 + 9 = 25, com diu l'enunciat.

Apartat c)

Resultat

Es recalculen moltes vegades els mateixos valors; es millora guardant-los en una taula (memorització) o amb un bucle que només fa n sumes.

Resolució

Què es repeteix. Es calculen una vegada i una altra els mateixos valors: per exemple, fib(2) es recalcula moltíssimes vegades dins de l'arbre de fib(20).
Memorització. Guardant en una taula els valors ja calculats, cada fib(k) es calcula una sola vegada: 21 valors en lloc de $21\,891$ crides.
Bucle. També pots fer un bucle que avanci des de fib(0) i fib(1) sumant els dos últims valors: llavors només cal fer n sumes.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 15

La funció següent suma les xifres d'un nombre enter positiu:
funció sx(n)
si n < 10 retorna n
si no retorna (residu de n entre 10) + sx(quocient de n entre 10)
a) Desplega sx(4857) i obtén el resultat.
b) Quin és el cas base i què fa que la recursió sempre s'acabi?
c) Calcula sx(2026).

Mira la solucióAmaga la solucióde l'exercici 15

Apartat a)

Resultat

\text{sx}(4857) = 24

Resolució

Anada. sx(4857) = 7 + sx(485); sx(485) = 5 + sx(48); sx(48) = 8 + sx(4).
Cas base. sx(4) = 4, perquè 4 < 10.
Tornada. sx(48) = 8 + 4 = 12; sx(485) = 5 + 12 = 17; sx(4857) = 7 + 17 = 24, és a dir, 7 + 5 + 8 + 4.

Apartat b)

Resultat

El cas base és n < 10 (una sola xifra); a cada crida n perd una xifra, i en un nombre finit de passos és menor que 10.

Resolució

Cas base. Quan n < 10, el nombre té una sola xifra i la suma de xifres és el mateix n.
Per què s'acaba. A cada crida, n se substitueix pel quocient entre 10, que té una xifra menys.
Conclusió. Després d'un nombre finit de crides (tantes com xifres menys una), n arriba a ser menor que 10 i la recursió s'atura.

Apartat c)

Resultat

\text{sx}(2026) = 10

Resolució

Desplegament. sx(2026) = 6 + sx(202) = 6 + 2 + sx(20) = 6 + 2 + 0 + sx(2).
Resultat. sx(2) = 2, per tant sx(2026) = 6 + 2 + 0 + 2 = 10.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 16

Es vol saber a partir de quin valor la suma 1 + 2 + 3 + … + n supera 500:
n ← 0
s ← 0
mentre s ≤ 500
n ← n + 1
s ← s + n
mostra n i s
a) Sense fer la traça sencera, planteja la desigualtat n(n + 1)/2 > 500 i resol-la.
b) Quins valors mostra l'algorisme?
c) Comprova que la suma d'1 a 31 no arriba a 500.

Mira la solucióAmaga la solucióde l'exercici 16

Apartat a)

Resultat

\dfrac{n(n+1)}{2} \gt 500 \iff n^{2} + n - 1000 \gt 0

, que es compleix per a

n \gt 31{,}13

: el menor enter és

n = 32

Resolució

Plantejament. Després de n voltes, $s = 1 + 2 + \dots + n = \tfrac{n(n + 1)}{2}$ . Vols el menor n amb $\tfrac{n(n+1)}{2} \gt 500$ .
Inequació. Multiplicant per 2: $n^{2} + n - 1000 \gt 0$ .
Arrel positiva. $n = \dfrac{-1 + \sqrt{1 + 4000}}{2} = \dfrac{-1 + \sqrt{4001}}{2} \approx 31{,}13$
Conclusió. La paràbola és positiva a la dreta d'aquesta arrel, per tant el menor enter que compleix la desigualtat és n = 32.

Apartat b)

Resultat

Mostra

n = 32

s = 528

Resolució

Valor de s. Quan el bucle s'atura, n = 32 i $s = \dfrac{32\cdot 33}{2} = 528$
Conclusió. L'algorisme mostra n = 32 i s = 528.

Apartat c)

Resultat

1 + 2 + \dots + 31 = 496 \leq 500

, per tant el bucle continua i s'atura en afegir el 32.

Resolució

Càlcul. $\dfrac{31\cdot 32}{2} = 496$ .
Condició. Com que 496 ≤ 500, la condició del mentre encara és certa i el bucle fa una volta més.
Conclusió. En afegir 32 s'obté 496 + 32 = 528 > 500 i s'atura, d'acord amb l'apartat b.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 17

Per avaluar un polinomi de grau n, p(x) = $a_{n}x^{n}$ + … + $a_{1}x$ + $a_{0}$ , comparem dos algorismes:
A) Calcular cada potència $x^{k}$ des de zero amb k − 1 productes, multiplicar-la per $a_{k}$ (1 producte més) i sumar tots els termes.
B) Horner: b ← $a_{n}$ ; per k des de n − 1 fins a 0: b ← b · x + $a_{k}$ .
a) Quantes multiplicacions fa l'algorisme A per a un polinomi de grau 10? I el B?
b) Dona la fórmula en funció de n per a cadascun i calcula-les per a n = 100.
c) Quin dels dos creix més de pressa quan n augmenta?

Mira la solucióAmaga la solucióde l'exercici 17

Apartat a)

Resultat

Grau 10: A fa 55 multiplicacions i B (Horner), 10.

Resolució

Algorisme A. El terme de grau k necessita k − 1 productes per a la potència i 1 pel coeficient, és a dir, k productes (el terme independent no en necessita cap).
Càlcul A. Per als termes de grau 1 a 10: $1 + 2 + \dots + 10 = 55$ multiplicacions.
Algorisme B. Horner fa una multiplicació a cada pas, i hi ha un pas per a k = 9, 8, …, 0: 10 multiplicacions.

Apartat b)

Resultat

\dfrac{n(n + 1)}{2}

(5050 per a

n = 100

); B:

n

(100 per a

n = 100

Resolució

Algorisme A. $1 + 2 + \dots + n = \dfrac{n(n + 1)}{2}$ ; per a n = 100, $\tfrac{100\cdot 101}{2} = 5050$ multiplicacions.
Algorisme B. Fa n multiplicacions; per a n = 100, 100.
Comprovació. Per a n = 3 surten 6 i 3, com a l'exercici 11.

Apartat c)

Resultat

A creix com

n^{2}

(quadràticament) i B com

n

(linealment): A creix molt més de pressa.

Resolució

Ordre de creixement. $\tfrac{n(n+1)}{2}$ es comporta com $\tfrac{n^{2}}{2}$ : és quadràtic. En canvi, n és lineal.
Comparació. Amb n = 100 la diferència ja és de 5050 contra 100.
Conclusió. El mètode de Horner és molt més eficient per a polinomis de grau alt.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 18

El mètode de Monte Carlo estima l'àrea d'una figura llançant punts a l'atzar. Es llancen 20 punts (x, y) dins del quadrat [0, 1] × [0, 1]:
(0,45; 0,56), (0,92; 0,47), (0,51; 0,59), (0,18; 0,51), (0,63; 0,79), (0,09; 0,30), (0,09; 0,81), (0,69; 0,04), (0,98; 0,96), (0,65; 0,62), (0,16; 0,02), (0,53; 0,06), (0,19; 0,24), (0,03; 0,46), (0,44; 0,84), (0,52; 0,64), (0,50; 0,66), (0,46; 0,28), (1,00; 1,00), (0,84; 0,71).
dins ← 0
per cada punt (x, y)
si $x^{2}$ + $y^{2}$ < 1 llavors dins ← dins + 1
mostra 4 · dins / 20
a) Quants punts cauen dins del quart de cercle $x^{2}$ + $y^{2}$ < 1? Quin valor mostra el programa?
b) Per què aquest valor és una estimació de π? (Pensa en l'àrea del quart de cercle i la del quadrat.)
c) Compara el valor amb π ≈ 3,1416 i digues si esperaries que millorés amb més punts.

Mira la solucióAmaga la solucióde l'exercici 18

Apartat a)

Resultat

Cauen dins 15 punts; el programa mostra

4\cdot \tfrac{15}{20} = 3

Resolució

Criteri. Un punt és dins del quart de cercle si $x^{2} + y^{2} \lt 1$ . És més ràpid buscar els que cauen fora ( $x^{2} + y^{2} \geq 1$ ).
Punts de fora.
punt x² + y²
(0,92; 0,47) 1,067
(0,63; 0,79) 1,021
(0,98; 0,96) 1,882
(1,00; 1,00) 2,000
(0,84; 0,71) 1,210
Recompte. Són 5 punts fora, per tant dins = 20 − 5 = 15. Els altres tenen sumes de quadrats menors que 1 (la més gran, (0,44; 0,84), amb 0,899).
Resultat. El programa mostra $4\cdot\dfrac{15}{20} = 3$ .

punt	x² + y²
(0,92; 0,47)	1,067
(0,63; 0,79)	1,021
(0,98; 0,96)	1,882
(1,00; 1,00)	2,000
(0,84; 0,71)	1,210

Apartat b)

Resultat

La fracció de punts que cauen dins s'acosta a

\dfrac{\text{àrea del quart de cercle}}{\text{àrea del quadrat}} = \dfrac{\pi/4}{1}

; multiplicant per 4 s'estima π.

Resolució

Àrees. El quart de cercle de radi 1 té àrea $\tfrac{\pi}{4}$ i el quadrat [0, 1] × [0, 1] té àrea 1.
Probabilitat. Si els punts són uniformes, la probabilitat que un caigui dins és $\tfrac{\pi/4}{1} = \tfrac{\pi}{4}$ , i la fracció dins/total s'hi acosta.
Conclusió. Per tant $4\cdot\tfrac{\text{dins}}{\text{total}}$ és una estimació de π.

Apartat c)

Resultat

3 té un error d'un 4,5 % respecte de π; amb més punts l'estimació millora (l'error baixa com

\tfrac{1}{\sqrt{N}}

Resolució

Error. $\dfrac{3{,}1416 - 3}{3{,}1416} \approx 0{,}045$ : un 4,5 %, prou allunyat de π.
Variabilitat. Amb només 20 punts, l'estimació depèn molt de l'atzar: cada punt de més o de menys canvia el resultat en 4/20 = 0,2.
Més punts. Sí que esperaries que millorés: l'error típic disminueix aproximadament com $\tfrac{1}{\sqrt{N}}$ .
Conclusió. Per guanyar una xifra decimal (dividir l'error per 10) fan falta unes 100 vegades més de punts: el mètode és senzill però lent.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 19

Per estimar l'àrea sota la paràbola y = $x^{2}$ entre x = 0 i x = 1 es divideix l'interval en n parts iguals i es sumen les àrees de rectangles:
h ← $\tfrac{1}{n}$
s ← 0
per i des de 0 fins a n − 1
s ← s + $(i \cdot h)^{2}$ · h
mostra s
a) Fes la traça per a n = 4 (rectangles amb l'altura al costat esquerre).
b) Quin és el valor que s'obtindria amb l'altura al costat dret? Calcula'l.
c) Per a n = 100 els resultats són 0,32835 (esquerra) i 0,33835 (dreta). Quina conclusió en treus sobre l'àrea real? (Sabem que és $\tfrac{1}{3}$ .)

Mira la solucióAmaga la solucióde l'exercici 19

Apartat a)

Resultat

s = 0{,}21875

Resolució

Dades. n = 4, h = 0,25. Els rectangles tenen base h i altura f(i · h) per a i = 0, 1, 2, 3 (costat esquerre).
Altures. f(0) = 0; f(0,25) = 0,0625; f(0,5) = 0,25; f(0,75) = 0,5625. La suma d'altures és 0,875.
Àrea. $s = 0{,}875\cdot 0{,}25 = 0{,}21875$ .

Apartat b)

Resultat

Amb l'altura a la dreta,

s = 0{,}46875

Resolució

Altures. Ara les altures són f(0,25), f(0,5), f(0,75) i f(1): 0,0625 + 0,25 + 0,5625 + 1 = 1,875.
Àrea. $s = 1{,}875\cdot 0{,}25 = 0{,}46875$ .
Relació. La diferència amb la suma per l'esquerra és $h\cdot(f(1) - f(0)) = 0{,}25$ .

Apartat c)

Resultat

L'àrea real queda entre les dues sumes:

0{,}32835 \lt A \lt 0{,}33835

, i ambdues tendeixen a

\tfrac{1}{3}

Resolució

Monotonia. Com que f és creixent a [0, 1], cada rectangle amb l'altura a l'esquerra queda per sota de la corba (suma per defecte) i amb l'altura a la dreta, per sobre (suma per excés).
Acotació. Per tant $0{,}32835 \lt A \lt 0{,}33835$ . La diferència entre les dues sumes és $h\cdot(f(1) - f(0)) = 0{,}01$ per a n = 100.
Conclusió. Quan n augmenta, la diferència $\tfrac{1}{n}$ tendeix a 0 i les dues sumes tendeixen a $\tfrac{1}{3} \approx 0{,}3333$ , que és l'àrea real (la integral).

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 20

Considera l'algorisme:
x ← 0
repeteix 5 vegades
x ← $\sqrt{2 + x}$
mostra x
a) Calcula els cinc valors mostrats (4 decimals).
b) Cap a quin valor sembla que tendeixen? Suposant que els valors s'acosten a un límit L, planteja l'equació L = $\sqrt{2 + L}$ i resol-la.
c) Per què només una de les dues solucions de l'equació té sentit aquí?

Mira la solucióAmaga la solucióde l'exercici 20

Apartat a)

Resultat

1,4142; 1,8478; 1,9616; 1,9904; 1,9976.

Resolució

Dades. x comença a 0 i a cada pas $x \leftarrow \sqrt{2 + x}$ .
Càlcul. $x_{1} = \sqrt{2} = 1{,}4142$ ; $x_{2} = \sqrt{2 + 1{,}4142} = 1{,}8478$ ; $x_{3} = \sqrt{3{,}8478} = 1{,}9616$ ; $x_{4} = \sqrt{3{,}9616} = 1{,}9904$ ; $x_{5} = \sqrt{3{,}9904} = 1{,}9976$ .

Apartat b)

Resultat

Tendeixen a

L = 2

; l'equació

L = \sqrt{2 + L}

porta a

L^{2} - L - 2 = 0

, amb solucions

L = 2

L = -1

Resolució

Observació. Els valors creixen i s'acosten a 2.
Plantejament. Si $x_{n} \to L$ , també $x_{n+1} \to L$ , i per continuïtat de l'arrel, $L = \sqrt{2 + L}$ .
Resolució. Elevant al quadrat: $L^{2} = 2 + L$ , és a dir, $L^{2} - L - 2 = 0 \;\Rightarrow\; (L - 2)(L + 1) = 0 \;\Rightarrow\; L = 2 \text{ o } L = -1$

Apartat c)

Resultat

Tots els termes són arrels quadrades (≥ 0), per tant el límit no pot ser −1:

L = 2

Resolució

Signe. Tots els termes són arrels quadrades, per tant són ≥ 0, i el límit també ha de ser ≥ 0.
Solució falsa. L = −1 és solució de l'equació elevada al quadrat però no de l'original: $\sqrt{2 + (-1)} = 1 \neq -1$ .
Conclusió. El límit és L = 2.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Nivell avançat

Exercici 21

Aquest algorisme multiplica dos enters positius només amb dobles, meitats i sumes:
demana a i b
p ← 0
mentre a ≥ 1
    si a és senar llavors p ← p + b
    a ← quocient de a entre 2
    b ← b · 2
mostra p
a) Fes la traça per a a = 37 i b = 43, anotant a, b i p a cada volta.
b) Comprova que el resultat és 37 · 43.
c) Explica per què funciona: relaciona els valors de a que són senars amb l'escriptura de 37 en binari.

Mira la solucióAmaga la solucióde l'exercici 21

Apartat a)

Resultat

(a, b, p) a cada volta: (37, 43, 43), (18, 86, 43), (9, 172, 215), (4, 344, 215), (2, 688, 215), (1, 1376, 1591). Mostra 1591.

Resolució

Dades. A cada volta: si a és senar, p ← p + b; després a es divideix per 2 (quocient) i b es duplica.
Traça.
volta a senar? p a i b nous
1 37 sí 43 18, 86
2 18 no 43 9, 172
3 9 sí 43 + 172 = 215 4, 344
4 4 no 215 2, 688
5 2 no 215 1, 1376
6 1 sí 215 + 1376 = 1591 0, 2752
Conclusió. Quan a = 0 la condició a ≥ 1 és falsa i s'atura: mostra 1591.

volta	a	senar?	p	a i b nous
1	37	sí	43	18, 86
2	18	no	43	9, 172
3	9	sí	43 + 172 = 215	4, 344
4	4	no	215	2, 688
5	2	no	215	1, 1376
6	1	sí	215 + 1376 = 1591	0, 2752

Apartat b)

Resultat

37\cdot 43 = 1591

: coincideix.

Resolució

Producte directe. $37\cdot 43 = 37\cdot 40 + 37\cdot 3 = 1480 + 111 = 1591$ .
Conclusió. És el mateix valor que mostra l'algorisme: ha multiplicat 37 per 43 fent només dobles, meitats i sumes.

Apartat c)

Resultat

37 = 100101_{2} = 32 + 4 + 1

; les voltes amb a senar són les xifres 1 del binari, i

p = 43\cdot(1 + 4 + 32) = 43\cdot 37

Resolució

Binari. $37 = 100101_{2} = 32 + 4 + 1$ . Dividir a per 2 i mirar si és senar és llegir les xifres binàries de dreta a esquerra.
Correspondència. Les voltes amb a senar (1a, 3a i 6a) corresponen a les xifres 1 del binari (1, 4 i 32), i en aquestes voltes b val 43 · 1, 43 · 4 i 43 · 32, és a dir, 43, 172 i 1376.
Distributiva. $p = 43 + 172 + 1376 = 43\cdot(1 + 4 + 32) = 43\cdot 37$
Conclusió. L'algorisme és la propietat distributiva aplicada a la descomposició de a en potències de 2.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 22

L'ordenació per selecció funciona així:
per i des d'1 fins a n − 1
busca la posició m del mínim entre els elements i, i + 1, …, n
si m ≠ i intercanvia els elements de les posicions i i m
a) Aplica-la a la llista (29, 10, 14, 37, 13) i escriu la llista després de cada passada.
b) Quantes comparacions entre elements es fan en total? Quants intercanvis?
c) Quantes comparacions faria per a una llista de n elements? (Ho has de justificar.)

Mira la solucióAmaga la solucióde l'exercici 22

Apartat a)

Resultat

(10, 29, 14, 37, 13) → (10, 13, 14, 37, 29) → (10, 13, 14, 37, 29) → (10, 13, 14, 29, 37).

Resolució

Passada 1 (i = 1). El mínim de tota la llista és 10 (posició 2); s'intercanvia amb el 29 → (10, 29, 14, 37, 13).
Passada 2 (i = 2). El mínim entre 29, 14, 37 i 13 és 13 (posició 5); s'intercanvia amb el 29 → (10, 13, 14, 37, 29).
Passada 3 (i = 3). El mínim entre 14, 37 i 29 és 14, que ja és a la seva posició: no hi ha intercanvi → (10, 13, 14, 37, 29).
Passada 4 (i = 4). El mínim entre 37 i 29 és 29; s'intercanvia → (10, 13, 14, 29, 37). La llista queda ordenada.

Apartat b)

Resultat

10 comparacions i 3 intercanvis.

Resolució

Comparacions. Per trobar el mínim de k elements cal comparar k − 1 elements amb el mínim provisional: a la passada 1, 4; a la 2, 3; a la 3, 2; a la 4, 1.
Total. $4 + 3 + 2 + 1 = 10$ comparacions.
Intercanvis. Passades 1, 2 i 4: 3 intercanvis (a la 3 no cal).

Apartat c)

Resultat

\dfrac{n(n - 1)}{2}

comparacions, independentment de l'ordre inicial.

Resolució

Raonament. A la passada i, es busca el mínim entre n − i + 1 elements, cosa que necessita n − i comparacions, sigui quin sigui l'ordre de la llista.
Suma. $(n - 1) + (n - 2) + \dots + 1 = \dfrac{n(n - 1)}{2}$
Comprovació. Per a n = 5: $\tfrac{5\cdot 4}{2} = 10$ , com has vist.
Conclusió. El nombre de comparacions creix com $n^{2}$ , independentment de l'ordre inicial de la llista (encara que ja estigui ordenada).

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 23

El nombre combinatori C(n, k) compleix C(n, 0) = C(n, n) = 1 i C(n, k) = C(n − 1, k − 1) + C(n − 1, k) (regla del triangle de Pascal). Es programa així:
funció C(n, k)
si k = 0 o k = n retorna 1
si no retorna C(n − 1, k − 1) + C(n − 1, k)
a) Calcula C(4, 2) desplegant les crides.
b) Per a C(6, 3) = 20, el programa fa 39 crides en total. Comprova la relació entre aquest nombre i el resultat.
c) Alternativament, es pot omplir el triangle de Pascal fila per fila fins a la fila 6. Quants valors cal calcular en total? Quin mètode és millor i per què?

Mira la solucióAmaga la solucióde l'exercici 23

Apartat a)

Resultat

C(4, 2) = 6

Resolució

Primera crida. C(4, 2) = C(3, 1) + C(3, 2).
C(3, 1). C(3, 1) = C(2, 0) + C(2, 1) = 1 + (C(1, 0) + C(1, 1)) = 1 + (1 + 1) = 3.
C(3, 2). C(3, 2) = C(2, 1) + C(2, 2) = (C(1, 0) + C(1, 1)) + 1 = 2 + 1 = 3.
Resultat. C(4, 2) = 3 + 3 = 6.

Apartat b)

Resultat

39 crides

= 2\cdot 20 - 1

: 20 casos base (fulles) i 19 crides que no ho són.

Resolució

Fulles. Els casos base retornen 1, i el resultat és la suma de tots aquests uns: per obtenir 20 hi ha d'haver 20 casos base (fulles de l'arbre de crides).
Nodes interiors. Cada crida que no és cas base en fa exactament dues. Un arbre binari així, amb 20 fulles, té 19 nodes interiors.
Relació. $20 + 19 = 39 = 2\cdot 20 - 1$ crides. En general, la recursió fa $2\,C(n, k) - 1$ crides.

Apartat c)

Resultat

Cal calcular 28 valors; és millor omplir el triangle, perquè cada valor es calcula un sol cop.

Resolució

Triangle. Les files 0 a 6 tenen 1, 2, …, 7 valors: 1 + 2 + … + 7 = 28 valors, cadascun amb una suma com a molt.
Comparació. Omplint el triangle, cada valor es calcula una sola vegada (28 valors); la recursió ingènua repeteix càlculs (39 crides per a C(6, 3)).
Conclusió. El triangle és millor, i la diferència augmenta per a n grans, perquè el nombre de crides de la recursió creix com el propi C(n, k).

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 24

Per aproximar la derivada de f en un punt a es calcula el quocient (f(a + h) − f(a)) / h amb valors de h cada cop més petits:
h ← 0,1
repeteix 3 vegades
    q ← (f(2 + h) − f(2)) / h
    mostra q
    h ← $\tfrac{h}{10}$
a) Fes-ho per a f(x) = $x^{3}$ . Escriu els tres valors de q.
b) Compara'ls amb f′(2) = 12 i calcula l'error de cada un. Quina fórmula té l'error en funció de h?
c) Per què no es pot fer h = 0 directament a l'algorisme?

Mira la solucióAmaga la solucióde l'exercici 24

Apartat a)

Resultat

q = 12{,}61

;

q = 12{,}0601

;

q = 12{,}006001

Resolució

Dades. $f(x) = x^{3}$ , a = 2 i $f(2) = 8$ . h val 0,1, 0,01 i 0,001.
h = 0,1. $\dfrac{2{,}1^{3} - 8}{0{,}1} = \dfrac{9{,}261 - 8}{0{,}1} = 12{,}61$ .
h = 0,01. $\dfrac{2{,}01^{3} - 8}{0{,}01} = \dfrac{8{,}120601 - 8}{0{,}01} = 12{,}0601$ .
h = 0,001. $\dfrac{2{,}001^{3} - 8}{0{,}001} = \dfrac{8{,}012006001 - 8}{0{,}001} = 12{,}006001$ .

Apartat b)

Resultat

Errors: 0,61; 0,0601; 0,006001. L'error és

6h + h^{2}

(gairebé

6h

Resolució

Errors. Restant f′(2) = 12: 0,61; 0,0601 i 0,006001.
Desenvolupament. $(2 + h)^{3} = 8 + 12h + 6h^{2} + h^{3}$ , per tant $\dfrac{(2 + h)^{3} - 8}{h} = 12 + 6h + h^{2}$
Fórmula de l'error. L'error és $6h + h^{2}$ , gairebé 6h quan h és petit.
Conclusió. Cada vegada que h es divideix per 10, l'error també es divideix per 10 aproximadament.

Apartat c)

Resultat

Amb h = 0 el quocient seria 0/0, indeterminat; la derivada és el límit quan h tendeix a 0, i l'algorisme només s'hi acosta.

Resolució

Indeterminació. Amb h = 0 tindries $\tfrac{f(2) - f(2)}{0} = \tfrac{0}{0}$ , que no té valor (i l'ordinador donaria un error).
Definició de derivada. $f'(a) = \displaystyle\lim_{h\to 0}\dfrac{f(a + h) - f(a)}{h}$ : és un límit, no una substitució.
Conclusió. L'algorisme s'hi acosta prenent h cada cop més petit, però no pot arribar-hi.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 25

Es vol calcular $\sqrt{2}$ amb el mètode babilònic, però aturant-se quan dues aproximacions consecutives difereixin en menys d'una milionèsima:
x ← 1
repeteix
    y ← $\tfrac{(x + 2 / x)}{2}$
    si |y − x| < 0,000001 llavors atura el bucle
    x ← y
mostra y
a) Fes la traça de les cinc primeres iteracions, anotant y i |y − x|. Quantes en fa l'algorisme?
b) Quina precisió té el resultat final respecte de $\sqrt{2}$ = 1,41421356…?
c) Què passaria si el criteri fos «y = x» (igualtat exacta) en un ordinador? Per què és millor un llindar?

Mira la solucióAmaga la solucióde l'exercici 25

Apartat a)

Resultat

y: 1,5; 1,416667; 1,414216; 1,41421356; 1,414213562, amb diferències 0,5; 0,083333; 0,002451; 0,0000021; 1,6 · 10⁻¹². Fa 5 iteracions.

Resolució

Dades. x = 1; cada iteració calcula $y = \tfrac{x + 2/x}{2}$ , compara |y − x| amb 0,000001 i, si no s'atura, fa x ← y.
Iteracions 1 i 2. $y = \tfrac{1 + 2}{2} = 1{,}5$ , amb |y − x| = 0,5. Després $y = \tfrac{1{,}5 + 1{,}333333}{2} = 1{,}416667$ , amb diferència 0,083333.
Iteracions 3 i 4. y = 1,414216, amb diferència 0,002451. Després y = 1,41421356, amb diferència 0,0000021 (> 0,000001, continua).
Iteració 5. y = 1,414213562, amb diferència aproximadament $1{,}6\cdot 10^{-12}$ (< 0,000001): s'atura.
Conclusió. L'algorisme fa 5 iteracions i mostra y ≈ 1,414213562.

Apartat b)

Resultat

L'error final és minúscul (menys de 10⁻¹¹), molt més precís que el llindar demanat.

Resolució

Comparació. El resultat coincideix amb √2 = 1,41421356… en tots els decimals mostrats; l'error és menor que 10⁻¹¹.
Per què. La convergència és molt ràpida: la diferència s'eleva aproximadament al quadrat a cada pas (0,0024 → 0,000002 → 10⁻¹²).
Conclusió. Quan el criteri s'activa, l'aproximació ja és molt millor que la milionèsima demanada.

Apartat c)

Resultat

Amb «y = x» el bucle podria no acabar mai, per la precisió finita de l'ordinador; un llindar garanteix que s'atura quan la millora és irrellevant.

Resolució

Precisió finita. Els ordinadors representen els decimals amb un nombre finit de xifres, i els arrodoniments fan que dues aproximacions consecutives puguin no coincidir mai exactament.
Risc. Amb la igualtat exacta, el bucle podria no acabar mai si els valors oscil·len entre dos nombres molt propers.
Conclusió. Amb un llindar es garanteix que l'algorisme s'atura quan la millora ja és irrellevant.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 26

Un nombre és perfecte si és igual a la suma dels seus divisors propis (els divisors menors que ell). Per exemple, 6 = 1 + 2 + 3. Per buscar-los fins a 500 es programa:
per n des de 2 fins a 500
    s ← 0
    per d des d'1 fins a n − 1
        si n és múltiple de d llavors s ← s + d
    si s = n mostra n
a) Comprova a mà que 28 és perfecte.
b) L'algorisme troba 6, 28 i 496. Quantes proves «n és múltiple de d» es fan en total? (Suma n − 1 per a n = 2, …, 500.)
c) Si el bucle de d només anés fins a n / 2 (tots els divisors propis són ≤ n/2), quantes proves es farien? Quin estalvi suposa?

Mira la solucióAmaga la solucióde l'exercici 26

Apartat a)

Resultat

Divisors propis de 28: 1, 2, 4, 7 i 14, que sumen 28: és perfecte.

Resolució

Divisors. Els divisors de 28 són 1, 2, 4, 7, 14 i 28; els propis (menors que 28) són 1, 2, 4, 7 i 14.
Suma. 1 + 2 + 4 + 7 + 14 = 28.
Conclusió. La suma coincideix amb el nombre: 28 és perfecte.

Apartat b)

Resultat

124\,750

proves.

Resolució

Plantejament. Per a cada n, el bucle de d fa n − 1 proves. Per a n = 2, …, 500 són 1, 2, …, 499 proves.
Càlcul. $1 + 2 + \dots + 499 = \dfrac{499\cdot 500}{2} = 124\,750$

Apartat c)

Resultat

62\,500

proves: aproximadament la meitat, un estalvi del 50 %.

Resolució

Justificació. Un divisor propi d de n compleix d ≤ n/2, ja que n/d ≥ 2. Per tant, n'hi ha prou de provar d = 1, …, ⌊n/2⌋.
Càlcul. $\sum_{n=2}^{500}\lfloor n/2\rfloor = 2\cdot(1 + 2 + \dots + 249) + 250 = 62\,500$ proves.
Estalvi. És aproximadament la meitat de $124\,750$ : un estalvi del 50 %.
Millora més gran. Provant només fins a $\sqrt{n}$ i sumant cada divisor d juntament amb n/d, es fan unes 7226 proves en total, més de 17 vegades menys que al principi.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 27

Una persona puja una escala de n graons i a cada pas pot pujar 1, 2 o 3 graons. Sigui E(n) el nombre de maneres diferents de pujar-la (l'ordre dels passos compta).
a) Justifica que E(n) = E(n − 1) + E(n − 2) + E(n − 3) i troba E(0), E(1) i E(2).
b) Calcula E(3), E(4), …, E(10).
c) Escriu l'algorisme iteratiu que calcula E(n) guardant només les tres últimes dades i digues quantes sumes fa per a n = 10.

Mira la solucióAmaga la solucióde l'exercici 27

Apartat a)

Resultat

E(n) = E(n − 1) + E(n − 2) + E(n − 3) classificant segons l'últim pas; E(0) = 1, E(1) = 1 i E(2) = 2.

Resolució

Classificació. L'últim pas d'una pujada pot ser d'1, 2 o 3 graons, i aquests tres casos no se solapen.
Recompte. Si l'últim pas és d'1, abans has pujat n − 1 graons (E(n − 1) maneres); si és de 2, n − 2 graons (E(n − 2)); si és de 3, n − 3 graons (E(n − 3)). Per tant, E(n) = E(n − 1) + E(n − 2) + E(n − 3).
Casos base. E(0) = 1 (no pujar és una manera, el cas base); E(1) = 1 (1); E(2) = 2 (1 + 1 i 2).

Apartat b)

Resultat

E(3) = 4, E(4) = 7, E(5) = 13, E(6) = 24, E(7) = 44, E(8) = 81, E(9) = 149, E(10) = 274.

Resolució

Regla. Cada valor és la suma dels tres anteriors.
Càlcul. E(3) = 2 + 1 + 1 = 4; E(4) = 4 + 2 + 1 = 7; E(5) = 7 + 4 + 2 = 13; E(6) = 13 + 7 + 4 = 24; E(7) = 24 + 13 + 7 = 44; E(8) = 44 + 24 + 13 = 81; E(9) = 81 + 44 + 24 = 149; E(10) = 149 + 81 + 44 = 274.
Comprovació. E(3) = 4: 1 + 1 + 1, 1 + 2, 2 + 1 i 3.

Apartat c)

Resultat

a ← 1, b ← 1, c ← 2; per i des de 3 fins a n: d ← a + b + c; a ← b; b ← c; c ← d; resultat c. Per a n = 10 fa 16 sumes.

Resolució

Algorisme. a ← 1, b ← 1, c ← 2 (E(0), E(1), E(2))
per i des de 3 fins a n
d ← a + b + c
a ← b; b ← c; c ← d
mostra c
Recompte. Per a n = 10 el bucle fa 8 voltes (i = 3, …, 10) i 2 sumes per volta: 16 sumes.
Comparació. Amb la recursió directa, el nombre de sumes creixeria de manera exponencial amb n, perquè es recalcularien els mateixos valors moltes vegades.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 28

Considera l'algorisme:
s ← 0
k ← 0
mentre s ≤ 1,6
k ← k + 1
s ← s + $\tfrac{1}{k^{2}}$
mostra k i s
a) Fes la traça dels quatre primers valors de s (4 decimals).
b) L'algorisme mostra k = 22 i s ≈ 1,6005. Què indica això? Comprova que la suma fins a k = 21 queda per sota d'1,6.
c) La suma 1 + $\tfrac{1}{4}$ + $\tfrac{1}{9}$ + … tendeix a $\tfrac{\pi^{2}}{6} \approx 1{,}6449$ . Si el llindar de l'algorisme fos 1,7 en lloc d'1,6, s'aturaria? Raona-ho amb una cota.

Mira la solucióAmaga la solucióde l'exercici 28

Apartat a)

Resultat

s: 1; 1,25; 1,3611; 1,4236.

Resolució

Dades. A cada volta k augmenta en 1 i s'hi suma $\tfrac{1}{k^{2}}$ .
Càlcul. k = 1: s = 1; k = 2: s = 1 + 0,25 = 1,25; k = 3: s = 1,25 + 0,1111 = 1,3611; k = 4: s = 1,3611 + 0,0625 = 1,4236.

Apartat b)

Resultat

La suma

1 + \tfrac{1}{4} + \dots + \tfrac{1}{k^{2}}

supera 1,6 per primera vegada amb

k = 22

; fins a

k = 21

val

1{,}5984 \lt 1{,}6

Resolució

Significat. El bucle s'atura la primera vegada que s > 1,6: k = 22 és el primer nombre de termes amb què la suma supera 1,6.
Comprovació. Fins a k = 21 la suma és 1,5984 < 1,6 (el bucle continua); amb k = 22 s'hi afegeix $\tfrac{1}{484} \approx 0{,}0021$ i s'arriba a 1,6005.

Apartat c)

Resultat

No s'aturaria: per a tot n, la suma total és menor que

S_{n} + \tfrac{1}{n}

; amb

n = 22

S \lt 1{,}6005 + 0{,}0455 = 1{,}646 \lt 1{,}7

Resolució

Cota d'un terme. Per a k ≥ 2, $\dfrac{1}{k^{2}} \lt \dfrac{1}{k(k - 1)} = \dfrac{1}{k - 1} - \dfrac{1}{k}$ .
Suma telescòpica. Sumant de k = n + 1 en endavant, els termes es cancel·len: $\sum_{k = n+1}^{\infty}\left(\dfrac{1}{k-1} - \dfrac{1}{k}\right) = \dfrac{1}{n}$ Per tant, la suma total és menor que $S_{n} + \tfrac{1}{n}$ per a qualsevol n.
Càlcul. Amb n = 22: $S \lt 1{,}6005 + \tfrac{1}{22} = 1{,}6005 + 0{,}0455 = 1{,}646 \lt 1{,}7$ .
Conclusió. La suma no arriba mai a 1,7 i, amb aquest llindar, el bucle no s'acabaria mai. (El valor exacte del límit, $\tfrac{\pi^{2}}{6} \approx 1{,}6449$ , es demostra a la universitat.)

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 29

Un sistema de monedes fictici té monedes de valor 1, 3 i 4. Per tornar la quantitat t amb el mínim de monedes, un algorisme «voraç» fa:
per cada moneda m en l'ordre 4, 3, 1
mentre t ≥ m
entrega m i t ← t − m
a) Aplica'l a t = 6. Quantes monedes entrega?
b) Troba una manera de tornar 6 amb menys monedes. Què demostra això sobre l'algorisme voraç?
c) Un algorisme alternatiu calcula m(t), el mínim de monedes per a cada t = 1, 2, …, 6, amb la regla m(t) = 1 + el mínim de m(t − 1), m(t − 3) i m(t − 4) (si existeixen), amb m(0) = 0. Calcula la taula.

Mira la solucióAmaga la solucióde l'exercici 29

Apartat a)

Resultat

Entrega 4 + 1 + 1: 3 monedes.

Resolució

Moneda de 4. 6 ≥ 4: entrega un 4 i queda t = 2. Ara 2 < 4.
Moneda de 3. 2 < 3: no n'hi cap.
Moneda d'1. Entrega 1 (t = 1) i 1 (t = 0).
Conclusió. Entrega 3 monedes: 4 + 1 + 1.

Apartat b)

Resultat

6 = 3 + 3, amb 2 monedes: l'algorisme voraç no sempre troba el mínim.

Resolució

Contraexemple. 6 = 3 + 3: només 2 monedes, menys que les 3 de l'algorisme voraç.
Què demostra. Triar sempre la moneda més gran possible no sempre porta a la solució òptima. Funciona amb alguns sistemes (com el de les monedes d'euro), però no amb tots.
Conclusió. Un sol contraexemple basta per demostrar que l'algorisme no és correcte en general.

Apartat c)

Resultat

m(0) = 0, m(1) = 1, m(2) = 2, m(3) = 1, m(4) = 1, m(5) = 2, m(6) = 2.

Resolució

Regla. m(t) = 1 + mín{m(t − 1), m(t − 3), m(t − 4)}, fent servir només els que existeixen (t − c ≥ 0), amb m(0) = 0.
Càlcul. m(1) = 1 + m(0) = 1; m(2) = 1 + m(1) = 2; m(3) = 1 + mín(m(2), m(0)) = 1; m(4) = 1 + mín(m(3), m(1), m(0)) = 1; m(5) = 1 + mín(m(4), m(2), m(1)) = 2; m(6) = 1 + mín(m(5), m(3), m(2)) = 1 + 1 = 2.
Taula.
t 0 1 2 3 4 5 6
m(t) 0 1 2 1 1 2 2
Conclusió. m(6) = 2, que coincideix amb 3 + 3. La taula guarda els resultats dels problemes més petits i els reutilitza (programació dinàmica).

t	0	1	2	3	4	5	6
m(t)	0	1	2	1	1	2	2

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Exercici 30

Aquest algorisme calcula el quocient i el residu de la divisió de a entre b amb restes successives:
q ← 0
r ← a
mentre r ≥ b
r ← r − b
q ← q + 1
mostra q i r
a) Fes-lo per a a = 137 i b = 12 i comprova que a cada volta es compleix b · q + r = a.
b) Demostra que la igualtat b · q + r = a (un invariant del bucle) es manté a cada volta i es compleix a l'inici.
c) Utilitza l'invariant i la condició de sortida per justificar que al final 0 ≤ r < b i, per tant, que q i r són el quocient i el residu de la divisió.

Mira la solucióAmaga la solucióde l'exercici 30

Apartat a)

Resultat

(q, r): (0, 137), (1, 125), (2, 113), …, (10, 17), (11, 5); mostra

q = 11

r = 5

, i

137 = 12\cdot 11 + 5

Resolució

Dades. a = 137 i b = 12. Comences amb q = 0 i r = 137, i mentre r ≥ 12 restes 12 a r i sumes 1 a q.
Traça. (q, r): (0, 137), (1, 125), (2, 113), (3, 101), (4, 89), (5, 77), (6, 65), (7, 53), (8, 41), (9, 29), (10, 17), (11, 5).
Comprovació. A cada línia 12 · q + r = 137; per exemple, 12 · 10 + 17 = 137.
Final. S'atura perquè 5 < 12. Mostra q = 11 i r = 5, i en efecte 137 = 12 · 11 + 5.

Apartat b)

Resultat

A l'inici b · 0 + a = a, i si b · q + r = a abans d'una volta, després b · (q + 1) + (r − b) = a: la igualtat es manté.

Resolució

Inici. Amb q = 0 i r = a: b · 0 + a = a. Es compleix.
Una volta. Suposa que abans d'una volta $b\cdot q + r = a$ . La volta canvia r per r − b i q per q + 1: $b\cdot(q + 1) + (r - b) = b\cdot q + b + r - b = b\cdot q + r = a$
Conclusió. Per inducció, la igualtat es compleix a l'inici i després de cada volta: és un invariant del bucle.

Apartat c)

Resultat

En sortir, r < b (condició falsa) i r ≥ 0 (només es resta b si r ≥ b); amb a = b · q + r, q i r són el quocient i el residu.

Resolució

Condició de sortida. El bucle només s'atura quan «r ≥ b» és fals, és a dir, r < b.
r no és negatiu. Només restes b quan r ≥ b, de manera que després de restar r − b ≥ 0. Així 0 ≤ r < b.
Divisió entera. Amb l'invariant, a = b · q + r i 0 ≤ r < b: aquesta és la definició de quocient i residu.
Acabament. També s'atura sempre, perquè r disminueix b ≥ 1 unitats a cada volta i no pot baixar indefinidament.

Nivell Batxillerat: t'ajudem amb el dubte? Pregunta-ho per WhatsApp · Ensenya-ho a casa

Preguntes freqüents

Què és una funció recursiva i què és el cas base?

Una funció recursiva es crida a ella mateixa per resoldre un problema més petit. El cas base és l'entrada més senzilla, que es resol directament i fa que la recursió s'aturi; sense cas base, la funció no acabaria mai.

Com es compara l'eficiència de dos algorismes?

Comptant les operacions que fan en funció de la mida n de les dades: per exemple, n, n(n−1)/2 o 2^n. Dos algorismes poden donar el mateix resultat però un tardar moltíssim més que l'altre quan n és gran.

Per què un algorisme numèric s'atura quan dues aproximacions consecutives estan molt properes?

Perquè això indica que ja s'ha assolit la precisió que es volia. Es fa servir un llindar (per exemple, una milionèsima) i no una igualtat exacta, perquè els ordinadors treballen amb un nombre finit de decimals.

Té a veure aquest tema amb la programació real?

Sí. Els mateixos algorismes (cerca, ordenació, bisecció, recursió) es fan servir en qualsevol llenguatge. Aquí s'escriuen en pseudocodi per concentrar-se en la idea i no en la sintaxi.

Tornar a Matemàtiques