Exercicis de pensament computacional — Matemàtiques 1r Batxillerat

a) x = 3: s = 3, c = 0. x = −2: s = 3, c = 1. x = 7: s = 10, c = 1. x = −5: s = 10, c = 2. x = 0: s = 10, c = 2 (no compleix cap condició). x = 4: s = 14, c = 2. x = −1: s = 14, c = 3. Mostra s = 14 i c = 3.
b) s és la suma dels elements positius (3 + 7 + 4 = 14) i c és el nombre d'elements negatius (−2, −5 i −1).
c) El 0 no és ni positiu ni negatiu: no entra a cap de les dues condicions i l'algorisme l'ignora. Per comptar-lo amb els negatius, la segona condició hauria de ser «si x ≤ 0» (i llavors c = 4).

a) k = 1: n = 1; k = 2: n = 2; k = 3: n = 6; k = 4: n = 24; k = 5: n = 120. Mostra 120.
b) Calcula el factorial: 5! = 5 · 4 · 3 · 2 · 1 = 120. Amb 8: 8! = 40.320.
c) Si el bucle no s'executa mai, n continua valent 1 i mostra 1. Coincideix amb la convenció matemàtica 0! = 1, i és la raó per la qual s'inicialitza n a 1 i no a 0 (amb 0 tot el producte seria 0).

a) f(−3) = 6; f(−2) = 0; f(−1) = −4; f(0) = −6; f(1) = −6; f(2) = −4; f(3) = 0; f(4) = 6.
b) Mostra «arrel: −2» i «arrel: 3».
c) f(x) és negatiu per a x = −1, 0, 1 i 2, per tant n = 4. Compta els enters que verifiquen $x^{2}$ − x − 6 < 0, és a dir, els enters de l'interval (−2, 3): factoritzant, (x − 3)(x + 2) < 0 si −2 < x < 3.

a) x: 100 → 50 → 25 → 12,5 → 6,25 → 3,125 → 1,5625 → 0,78125. Hi ha 7 divisions, i quan x = 0,78125 la condició x > 1 és falsa.
b) Mostra k = 7 i x = 0,78125.
c) k és el menor enter tal que $\tfrac{100}{2^{k}} \leq 1$, és a dir, $2^{k}$ ≥ 100. Com que $2^{6}$ = 64 < 100 ≤ 128 = $2^{7}$, k = 7. En general k = ⌈log₂ 100⌉ = 7.

a) 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.
b) 10 + 9 + 8 + … + 1 = 55. Mostra 55.
c) En general és n + (n − 1) + … + 1 = n(n + 1)/2. Per a n = 100: 100 · $\tfrac{101}{2} = 5$.050 repeticions. El nombre d'operacions creix com $n^{2}$.

(−3, 2): x ≠ 0 i y ≠ 0; x > 0 és fals; x < 0 i y > 0 és cert. Mostra «segon quadrant».
(4, −1): ni primer, ni segon, ni tercer; arriba al final: «quart quadrant».
(0, 5): x = 0, per tant «sobre un eix».
(−2, −2): x < 0 i y < 0. Mostra «tercer quadrant».
L'última línia no necessita condició perquè, un cop descartats els eixos i els tres quadrants anteriors, l'únic cas possible és x > 0 i y < 0, que és el quart quadrant.

a) n = 12: múltiple de 3 (sí) i no múltiple de 5 (sí): certa. n = 15: múltiple de 3 (sí) però també múltiple de 5, per tant «no múltiple de 5» és fals: falsa. n = 10: no és múltiple de 3: falsa.
b) Compleixen la condició 3, 6, 9, 12, 18, 21, 24 i 27: són 8 nombres (els múltiples de 3 són 10, i s'exclouen el 15 i el 30).
c) La negació de «A i no B» és «no A o B». Per tant, un nombre NO compleix la condició si «n no és múltiple de 3 o n és múltiple de 5». Per a n = 15 es compleix aquesta negació, i la condició original és falsa, com hem vist.

a) El bucle va d'1 a 4: suma 3 + 7 + 11 + 15 = 36.
b) Els 5 primers termes són 3, 7, 11, 15 i 19, que sumen 55. L'error és un error «de fora d'un»: el bucle s'atura a n − 1 i no suma l'últim terme. Cal posar «per i des d'1 fins a n».
c) a₅ = 3 + 4 · 4 = 19, i S = 5 · (3 + 19) / 2 = 5 · 22 / 2 = 55. Coincideix amb el valor corregit.

a) 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); fact(0) = 1 (cas base).
De tornada: 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.
b) Es fan 6 crides: fact(5), fact(4), fact(3), fact(2), fact(1) i fact(0), és a dir, n + 1 crides.
c) fact(−1) cridaria fact(−2), després fact(−3), etc.: mai no arribaria a 0 i la recursió no s'aturaria (en un ordinador real acabaria amb un error de desbordament de pila). Tota funció recursiva necessita un cas base al qual s'arribi sempre.

a) n = 4; s: 0 → 4 → 12 → 21 → 36. Mostra $\tfrac{36}{4} = 9$.
b) Si L és buida, n = 0 i l'última línia divideix entre 0, que no està definit: el programa donaria un error. Es pot evitar afegint una condició: «si n = 0 mostra «no hi ha dades»; si no mostra s / n».

a) b = 2; b = 2 · 3 − 5 = 1; b = 1 · 3 + 3 = 6; b = 6 · 3 − 7 = 11. Mostra 11.
b) p(3) = 2 · 27 − 5 · 9 + 3 · 3 − 7 = 54 − 45 + 9 − 7 = 11. Coincideix.
c) Horner fa 3 multiplicacions. Avaluant monomi a monomi: 2x³ necessita 2 productes per a $x^{3}$ i 1 pel coeficient (3); −5x² necessita 1 + 1 = 2; 3x necessita 1; en total 3 + 2 + 1 = 6 multiplicacions. La diferència creix amb el grau: vegeu l'exercici 17.

a) x = 3 → $\tfrac{(3 + 10/3)}{2}$ = $\tfrac{(3 + 3{,}333333)}{2} = 3{,}166667$. Després: $\tfrac{(3{,}166667 + 10/3{,}166667)}{2} = 3{,}162281$. Finalment x = 3,162278.
b) Errors respecte de $\sqrt{10}$ ≈ 3,162278: pas 1: 0,004389; pas 2: 0,000003; pas 3: menys d'1 milionèsim. L'error baixa molt de pressa (aproximadament s'eleva al quadrat en cada pas).
c) Si x és més petit que $\sqrt{a}$, llavors a / x és més gran que $\sqrt{a}$, i al revés. La seva mitjana queda entremig, més a prop de l'arrel. Per exemple, 3 < $\sqrt{10}$ < 3,333.

a) f(1) = −1 < 0 i f(2) = 7 > 0. Com que f és contínua (és un polinomi), pel teorema de Bolzano té almenys una arrel a (1, 2).
b) 1) m = 1,5; f(m) = 1,875 > 0; l'arrel és a [1; 1,5].
2) m = 1,25; f(m) = 0,203125 > 0; interval [1; 1,25].
3) m = 1,125; f(m) = −0,451172 < 0; interval [1,125; 1,25].
4) m = 1,1875; f(m) = −0,137939 < 0; interval [1,1875; 1,25].
c) L'amplada és 1,25 − 1,1875 = 0,0625 = 1/16: cada repetició la divideix per 2. Prenent el punt mitjà, 1,21875, l'error és com a molt 0,03125. (L'arrel real és 1,2134.)

a) fib(0) = 0, fib(1) = 1, fib(2) = 1, fib(3) = 2, fib(4) = 3, fib(5) = 5, fib(6) = 8.
b) 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); fib(2) (les dues vegades) fa fib(1) i fib(0); en total fib(4) fa 9 crides. El nombre de crides C(n) satisfà C(n) = 1 + C(n − 1) + C(n − 2): C(0) = C(1) = 1, C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15, C(6) = 25.
c) Es calculen una vegada i una altra els mateixos valors (per exemple, fib(2) es recalcula moltes vegades). Es millora guardant els valors ja calculats en una taula (memorització) o fent un bucle que avanci des de fib(0) i fib(1): llavors només cal fer n sumes.

a) sx(4857) = 7 + sx(485); sx(485) = 5 + sx(48); sx(48) = 8 + sx(4); sx(4) = 4 (cas base). De tornada: 7 + 5 + 8 + 4 = 24.
b) El cas base és n < 10 (una sola xifra). A cada crida n es divideix per 10 (quocient), de manera que perd una xifra: després d'un nombre finit de crides arriba a ser menor que 10.
c) sx(2026) = 6 + sx(202) = 6 + 2 + sx(20) = 6 + 2 + 0 + sx(2) = 10.

a) n(n + 1)/2 > 500 equival a $n^{2}$ + n − 1000 > 0. L'arrel positiva de $n^{2}$ + n − 1000 = 0 és n = $\tfrac{(-1 + \sqrt{4001})}{2} \approx 31{,}13$. Per tant, l'enter més petit que ho compleix és n = 32.
b) Mostra n = 32 i s = 32 · $\tfrac{33}{2} = 528$.
c) La suma fins a 31 és 31 · $\tfrac{32}{2} = 496$ ≤ 500, així que el bucle continua; en afegir 32 s'obté 528 > 500 i s'atura.

a) A: el terme de grau k necessita k − 1 productes per a la potència i 1 pel coeficient, és a dir, k productes. Per als termes de grau 1 a 10: 1 + 2 + … + 10 = 55 multiplicacions. B: una multiplicació per cada pas, 10.
b) A: 1 + 2 + … + n = n(n + 1)/2; per a n = 100, 5.050 multiplicacions. B: n; per a n = 100, 100 multiplicacions.
c) A creix com $n^{2}$ (quadràticament) i B creix com n (linealment). Amb n = 100 la diferència ja és de 5.050 contra 100, de manera que el mètode de Horner és molt més eficient per a polinomis de grau alt.

a) Cauen fora els punts amb $x^{2}$ + $y^{2}$ ≥ 1: (0,92; 0,47) amb 1,067; (0,63; 0,79) amb 1,021; (0,98; 0,96) amb 1,882; (1,00; 1,00) amb 2,000; (0,84; 0,71) amb 1,210 (la suma de quadrats és el valor que apareix després d'«amb»). Són 5 punts. Per tant dins hi ha 15 punts, i el programa mostra 4 · $\tfrac{15}{20} = 3$.
b) L'àrea del quart de cercle és $\tfrac{\pi}{4}$ i la del quadrat és 1. Si els punts són uniformes, la fracció que cau dins s'acosta a $\tfrac{\pi}{4}$, i per això 4 · dins / total estima π.
c) 3 és prou allunyat de 3,1416 (un error d'un 4,5 %). Amb només 20 punts l'estimació té molta variabilitat; l'error típic disminueix aproximadament com $\tfrac{1}{\sqrt{N}}$, de manera que per guanyar una xifra decimal fan falta unes 100 vegades més de punts.

a) h = 0,25. Altures: f(0) = 0; f(0,25) = 0,0625; f(0,5) = 0,25; f(0,75) = 0,5625. Suma d'altures: 0,875. Àrea = 0,875 · 0,25 = 0,21875.
b) Amb l'altura a la dreta: f(0,25) + f(0,5) + f(0,75) + f(1) = 0,0625 + 0,25 + 0,5625 + 1 = 1,875, i l'àrea és 1,875 · 0,25 = 0,46875.
c) Com que f és creixent, la suma per l'esquerra és per defecte i la de la dreta és per excés: l'àrea real queda entremig (0,32835 < A < 0,33835). La diferència entre les dues sumes és h · (f(1) − f(0)) = 0,01 per a n = 100. Quan n augmenta, les dues tendeixen a 1/3 ≈ 0,3333.

a) x₁ = √2 = 1,4142; x₂ = √(2 + 1,4142) = 1,8478; x₃ = 1,9616; x₄ = 1,9904; x₅ = 1,9976.
b) Els valors creixen i s'acosten a 2. Si x_n → L, també x_n+1 → L, i per continuïtat de l'arrel L = √(2 + L). Elevant al quadrat: L² = 2 + L, és a dir L² − L − 2 = 0, amb solucions L = 2 i L = −1.
c) Tots els termes són arrels quadrades, per tant són ≥ 0: el límit no pot ser −1 (que és una solució de l'equació elevada al quadrat però no de l'original, ja que √(2 + (−1)) = 1 ≠ −1). El límit és L = 2.

a) Volta 1: a = 37 (senar), p = 43; passa a a = 18, b = 86.
Volta 2: a = 18 (parell), p = 43; a = 9, b = 172.
Volta 3: a = 9 (senar), p = 43 + 172 = 215; a = 4, b = 344.
Volta 4: a = 4 (parell), p = 215; a = 2, b = 688.
Volta 5: a = 2 (parell), p = 215; a = 1, b = 1376.
Volta 6: a = 1 (senar), p = 215 + 1376 = 1591; a = 0 i s'atura. Mostra 1591.
b) 37 · 43 = 1591.
c) 37 = 100101 en base 2 = 32 + 4 + 1. Les voltes amb a senar corresponen a les xifres 1 del binari (1, 4, 32), i en aquestes voltes b val 43 · 1, 43 · 4 i 43 · 32, és a dir 43, 172 i 1376. La suma és 43 · (1 + 4 + 32) = 43 · 37. L'algorisme és la distributiva aplicada a la descomposició de a en potències de 2.

a) Passada 1 (i = 1): el mínim és 10 (posició 2); s'intercanvia amb 29 → (10, 29, 14, 37, 13).
Passada 2 (i = 2): el mínim entre 29, 14, 37, 13 és 13 (posició 5); s'intercanvia amb 29 → (10, 13, 14, 37, 29).
Passada 3 (i = 3): el mínim entre 14, 37, 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). Llista ordenada.
b) A la passada 1 es comparen 4 elements amb el mínim provisional, a la 2, 3; a la 3, 2; a la 4, 1: 4 + 3 + 2 + 1 = 10 comparacions. S'han fet 3 intercanvis.
c) Per a n elements: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparacions. Per a n = 5 són 10, com hem vist. El nombre de comparacions creix com $n^{2}$, independentment de l'ordre inicial de la llista.

a) C(4, 2) = C(3, 1) + C(3, 2). C(3, 1) = C(2, 0) + C(2, 1) = 1 + (C(1, 0) + C(1, 1)) = 1 + 2 = 3. C(3, 2) = C(2, 1) + C(2, 2) = 2 + 1 = 3. Per tant C(4, 2) = 3 + 3 = 6.
b) Cada crida que no és cas base fa dues crides; i com que els casos base retornen 1, i el resultat és la suma d'aquests uns, hi ha 20 casos base (fulles de l'arbre). Un arbre binari amb 20 fulles té 19 nodes interiors: 20 + 19 = 39 crides = 2 · 20 − 1.
c) El triangle fins a la fila 6 té 1 + 2 + … + 7 = 28 valors, cadascun amb una suma com a molt. És millor omplir el triangle: cada valor es calcula una sola vegada (28 valors), mentre que la recursió ingènua repeteix càlculs (39 crides, i molt més per a n grans, perquè el nombre de crides creix com el propi C(n, k)).

a) h = 0,1: (2,1³ − 8) / 0,1 = (9,261 − 8) / 0,1 = 12,61. h = 0,01: (2,01³ − 8) / 0,01 = (8,120601 − 8) / 0,01 = 12,0601. h = 0,001: (8,012006001 − 8) / 0,001 = 12,006001.
b) Errors: 0,61; 0,0601; 0,006001. Desenvolupant, ((2 + h)³ − 8)/h = 12 + 6h + h², per tant l'error és 6h + h²: gairebé 6h. Cada vegada que h es divideix per 10, l'error també es divideix per 10 aproximadament.
c) Amb h = 0 el quocient seria 0/0, indeterminat. La derivada és precisament el límit del quocient quan h tendeix a 0: l'algorisme s'hi acosta però no pot arribar-hi.

a) Iteració 1: y = $\tfrac{(1 + 2)}{2} = 1{,}5$; |y − x| = 0,5.
Iteració 2: y = $\tfrac{(1{,}5 + 1{,}333333)}{2} = 1{,}416667$; diferència 0,083333.
Iteració 3: y = 1,414216; diferència 0,002451.
Iteració 4: y = 1,41421356; diferència 0,0000021 (> 0,000001, continua).
Iteració 5: y = 1,414213562; diferència aproximadament 1,6 · 10⁻¹² (< 0,000001, s'atura). Fa 5 iteracions.
b) Després de l'última iteració l'error és minúscul (menys de 10⁻¹¹); és molt més precís que el llindar demanat, perquè la convergència és molt ràpida (la diferència s'eleva aproximadament al quadrat a cada pas).
c) Els ordinadors representen els decimals amb una precisió finita; amb la igualtat exacta el bucle podria no acabar mai si els valors oscil·len entre dos nombres molt propers. Amb un llindar es garanteix que l'algorisme s'atura quan la millora ja és irrellevant.

a) Els divisors propis de 28 són 1, 2, 4, 7 i 14, i 1 + 2 + 4 + 7 + 14 = 28.
b) La suma 1 + 2 + … + 499 = 499 · $\tfrac{500}{2} = 124$.750 proves.
c) Per a cada n s'haurien de fer ⌊n/2⌋ proves; el total és 62.500, és a dir, la meitat aproximadament: l'estalvi és del 50 %. Una millora més gran és provar només fins a $\sqrt{n}$ i sumar cada divisor d juntament amb n/d: llavors es fan unes 7.226 proves en total, més de 17 vegades menys que al principi.

a) L'últim pas d'una pujada pot ser d'1, 2 o 3 graons. Si és d'1, abans s'havien pujat n − 1 graons (E(n − 1) maneres); si és de 2, n − 2 graons; si és de 3, n − 3 graons. Per tant, E(n) = E(n − 1) + E(n − 2) + E(n − 3). E(0) = 1 (no pujar és una manera, el cas base), E(1) = 1 (1) i E(2) = 2 (1 + 1, 2).
b) 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.
c) 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; el resultat és c. Per a n = 10 es fan 8 voltes i 2 sumes per volta: 16 sumes (en lloc d'un nombre que creix de manera exponencial amb la recursió directa).

a) 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.
b) La suma 1 + 1/4 + … + 1/k² supera 1,6 per primera vegada quan k = 22. Fins a k = 21 la suma és 1,5984 < 1,6; amb k = 22 s'hi afegeix 1/484 ≈ 0,0021 i s'arriba a 1,6005.
c) No. Per a k > n, 1/k² < 1/(k(k − 1)) = 1/(k − 1) − 1/k, i la suma d'aquests termes (telescòpica) de k = n + 1 en endavant és menor que 1/n. Per tant, la suma total és menor que S_n + 1/n per a qualsevol n. Amb n = 22: S < 1,6005 + 0,0455 = 1,646 < 1,7. La suma no arriba mai a 1,7 i, amb aquest llindar, el bucle no s'acabaria mai. (El valor exacte del límit, π²/6 ≈ 1,6449, es demostra a la universitat.)

a) t = 6: entrega 4 (t = 2); 3 no hi cap; entrega 1 (t = 1) i 1 (t = 0). Entrega 3 monedes: 4 + 1 + 1.
b) 6 = 3 + 3, només 2 monedes. L'algorisme voraç tria sempre la moneda més gran possible i no sempre troba el mínim; funciona amb alguns sistemes (com el de les monedes d'euro), però no amb tots. Un sol contraexemple basta per demostrar que no és correcte en general.
c) m(0) = 0; m(1) = 1 + m(0) = 1; m(2) = 1 + m(1) = 2; m(3) = 1 + min(m(2), m(0)) = 1; m(4) = 1 + min(m(3), m(1), m(0)) = 1; m(5) = 1 + min(m(4), m(2), m(1)) = 2; m(6) = 1 + min(m(5), m(3), m(2)) = 1 + 1 = 2. Hem trobat m(6) = 2, que coincideix amb 3 + 3. La taula guarda els resultats de problemes més petits i els reutilitza.

a) Valors de (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). A cada línia: 12 · q + r = 137 (per exemple 12 · 10 + 17 = 137). S'atura perquè 5 < 12. Mostra q = 11 i r = 5, i en efecte 137 = 12 · 11 + 5.
b) A l'inici, b · 0 + a = a. Si abans d'una volta b · q + r = a, després de la volta el nou residu és r − b i el nou quocient és q + 1, i b · (q + 1) + (r − b) = b · q + b + r − b = b · q + r = a. Per tant la igualtat es manté.
c) El bucle només s'atura quan r ≥ b és fals, és a dir r < b. A més r no és mai negatiu: només restem b quan r ≥ b. Així 0 ≤ r < b i a = b · q + r: aquesta és la definició de quocient i residu. També s'atura sempre, perquè r disminueix b ≥ 1 unitats a cada volta.