Exercicis de patrons i pensament computacional — Matemàtiques Aplicades a les Ciències Socials 1r Batxillerat

Escriu les dades ordenades: 1 triangle i 3 escuradents, 2 i 5, 3 i 7.
Mira la variació: de 3 a 5 hi van 2 i de 5 a 7 també 2. Cada triangle nou només n'afegeix 2, no 3.
Entén per què: el triangle nou aprofita un costat de l'anterior.
Anomena't la variable: n = nombre de triangles.
Escriu la regla partint del primer: el primer costa 3 i cada un dels n - 1 següents costa 2. Queda a_n = 3 + 2(n-1) = 2n + 1.
Comprova-la: amb n = 3 dona 2·3 + 1 = 7, que és el que et diuen.
Respon: per a 40 triangles calen 2·40 + 1 = 81 escuradents.

Anomena la variable amb les unitats: t = minuts transcorreguts.
Identifica la part fixa: els 1.200 litres que ja hi ha, que no depenen de t.
Identifica la part variable: 45 litres per minut, o sigui 45·t.
Escriu la regla: V(t) = 1200 + 45t, amb V en litres.
Comprova-la amb el punt de partida: V(0) = 1200, que és el que hi havia. Quadra.
Respon: V(20) = 1200 + 45·20 = 1200 + 900 = 2100 litres.

Comprova primer el que et diuen: les diferències són 3, 6, 12, i efectivament no són constants.
Digues què s'ha de mirar quan les diferències fallen: el QUOCIENT entre cada terme i l'anterior.
Calcula'ls: $\tfrac{6}{3} = 2$, $\tfrac{12}{6} = 2$ i $\tfrac{24}{12} = 2$. El quocient sí que és constant.
Interpreta-ho: quan el quocient és constant, la regla és exponencial, amb raó r = 2.
Escriu-la: $a_{n}$ = 3 · 2ⁿ⁻¹.
Comprova-la: amb n = 4 dona 3 · $2^{3}$ = 24, que és el que hi ha.
Respon: $a_{8}$ = 3 · $2^{7}$ = 3 · 128 = 384.

Entre el terme 3 i el terme 7 hi ha 7 - 3 = 4 salts de mida d: a₇ = a₃ + 4d.
27 = 11 + 4d, d'on 4d = 16 i d = 4.
Primer terme: a₃ = a₁ + 2d, així que a₁ = 11 - 8 = 3.
Terme general: a_n = a₁ + (n - 1)·d = 3 + 4(n - 1) = 4n - 1.
Comprovació: a₃ = 4·3 - 1 = 11 i a₇ = 4·7 - 1 = 27.

a) Aritmètica: cada terme s'obté sumant 5 a l'anterior (12 - 7 = 17 - 12 = 22 - 17 = 5). Diferència d = 5.
b) Geomètrica: cada terme s'obté multiplicant l'anterior per 3 (6/2 = 18/6 = 54/18 = 3). Raó r = 3.
c) Cap de les dues: les diferències (3, 5, 7) no són constants i els quocients (4; 2,25; 1,78...) tampoc. Són els quadrats perfectes, a_n = n²; les diferències augmenten de 2 en 2, és a dir, les diferències segones són constants.

Anem actualitzant les variables a cada volta del bucle. Al principi, s = 0.
i = 1: s = 0 + 1 = 1; i = 2: s = 1 + 4 = 5; i = 3: s = 5 + 9 = 14; i = 4: s = 14 + 16 = 30; i = 5: s = 30 + 25 = 55.
L'algorisme mostra 55.
Calcula la suma dels quadrats dels cinc primers nombres naturals: 1² + 2² + 3² + 4² + 5² = 55.

Cada cel·la aplica la fórmula a la de damunt:
A1 = 2; A2 = 3·2 + 1 = 7; A3 = 3·7 + 1 = 22; A4 = 3·22 + 1 = 67; A5 = 3·67 + 1 = 202.
Definició recursiva: $a_{1}$ = 2 i $a_{n+1}$ = 3·$a_{n}$ + 1 (per a n ≥ 1).
Observació: no és aritmètica ni geomètrica (7 - 2 = 5 i 22 - 7 = 15; $\tfrac{7}{2} = 3{,}5$ i $\tfrac{22}{7} \approx 3{,}14$), però la recursió permet calcular qualsevol terme a partir de l'anterior.

L'algorisme suma 1 cada vegada que troba un parell, de manera que compta els parells (2, 4, 6, 8 i 10: són 5) en lloc de sumar-los.
Correcció: dins del «si», la instrucció ha de ser s ← s + i.
Amb l'error corregit: 2 + 4 + 6 + 8 + 10 = 30.
Comprovació amb una fórmula: els parells formen una progressió aritmètica de 5 termes i la suma és 5·$\tfrac{(2 + 10)}{2} = 30$.

Fila 0: 1 (suma 1); fila 1: 1 1 (suma 2); fila 2: 1 2 1 (suma 4).
Fila 3: 1 3 3 1 (suma 8); fila 4: 1 4 6 4 1 (suma 16); fila 5: 1 5 10 10 5 1 (suma 32).
Patró: les sumes són 1, 2, 4, 8, 16, 32; cada fila suma el doble que l'anterior (successió geomètrica de raó 2), és a dir, la fila n suma $2^{n}$.
Predicció: la fila 10 suma $2^{10}$ = 1024.

És aritmètica amb a₁ = 7 i d = 5, de manera que a_n = 7 + (n - 1)·5.
Volem que a_n = 252: 7 + 5(n - 1) = 252, d'on 5(n - 1) = 245 i n - 1 = 49.
Per tant n = 50: la successió té 50 termes.
Comprovació: a₅₀ = 7 + 49·5 = 7 + 245 = 252.

Calcula els primers termes amb la fórmula que et donen: $a_{1}$ = 3, $a_{2}$ = 8, $a_{3}$ = 13.
Mira què passa d'un terme al següent: de 3 a 8 hi van 5 i de 8 a 13 també. La diferència és constant i val 5.
Escriu la recursiva amb les seves dues parts: $a_{1}$ = 3 com a punt de partida i $a_{n+1}$ = $a_{n}$ + 5 com a regla.
Comprova que coincideixen en un terme que no hagis fet servir per construir-la: amb l'explícita, $a_{5}$ = 5·5 - 2 = 23; amb la recursiva, continuant la llista, 13, 18, 23. Donen el mateix.
Fixa't d'on surt cada nombre: el 5 de la recursiva és el coeficient de n a l'explícita, i el punt de partida NO és el -2 sinó $a_{1}$ = 3.

Escriu les diferències entre cada terme i l'anterior: 3, 5, 7, 9.
Mira si són constants: no ho són, o sigui que la regla NO és lineal.
Fes ara les diferències d'aquestes diferències: 2, 2, 2. Aquesta segona columna sí que és constant.
Interpreta-ho: quan la segona columna de diferències és constant, la regla és de segon grau.
Busca-la mirant els valors: 5 és 1 + 4, 8 és 4 + 4, 13 és 9 + 4, 20 és 16 + 4. Els primers sumands són els quadrats.
Escriu la regla: a_n = n² + 4.
Comprova-la amb dues posicions: a₄ = 16 + 4 = 20 i a₅ = 25 + 4 = 29. Quadren.

Identifica les dues parts de tota recurrència: el punt de partida i la regla per avançar.
El punt de partida és el deute inicial i va escrit a mà a la primera cel·la: 1200.
La regla és 'el que devia menys el que he tornat', i va com a fórmula a la cel·la de sota, referida a la de dalt: cel·la anterior menys 150.
Arrossega aquesta segona cel·la cap avall: cada fila aplicarà la regla al resultat de l'anterior.
Comprova amb el cap abans de fiar-te de la taula: $\tfrac{1200}{150} = 8$, o sigui que han de ser 8 mesos justos.
Comprova un valor intermedi: al mes 4 el deute ha de ser 1200 - 150·4 = 600 euros.
Respon: s'acaba de pagar al mes 8, que és la primera fila que dona zero.

Descriu el primer: començar a zero i anar sumant 1, 2, 3, ... fins a 200. Són 200 sumes.
Descriu el segon: aplicar $S_{n}$ = n·$\tfrac{(a_{1} + a_{n})}{2}$, que amb aquestes dades és 200·$\tfrac{(1 + 200)}{2}$. És una suma, una multiplicació i una divisió.
Calcula el resultat amb el segon: 200 · $\tfrac{201}{2} = 20100$.
Compara'ls: el segon fa moltíssims menys passos i, en fer-ne menys, també té menys llocs on equivocar-se.
Mira què passaria amb 10.000 nombres, que és la comparació que decideix: el primer passaria a 10.000 sumes i el segon continuaria fent-ne tres.
Conclou: quan la mida creix, el segon guanya per molt. Amb nombres petits la diferència no es nota.

A cada ronda el nombre de receptors es multiplica per 3: 3, 9, 27, ... és una successió geomètrica amb $a_{1}$ = 3 i r = 3, de terme general $a_{n}$ = $3^{n}$.
Sisena ronda: $a_{6}$ = $3^{6}$ = 729 persones.
Total: suma dels 6 primers termes, $S_{6}$ = $a_{1}$·$\tfrac{(r^{6} - 1)}{(r - 1)} = 3$·$\tfrac{(729 - 1)}{2} = 3$·$\tfrac{728}{2} = 1092$ persones.
Comprovació: 3 + 9 + 27 + 81 + 243 + 729 = 1092.

Cada any el capital es multiplica per 1,03: C₀ = 1000 i C_n+1 = 1,03·C_n. És una successió geomètrica de raó 1,03, de manera que C_n = 1000·1,03ⁿ.
Volem 1000·1,03ⁿ > 2000, és a dir, 1,03ⁿ > 2. Amb logaritmes: n > ln 2 / ln 1,03 = 0,6931/0,02956 = 23,45.
Per tant calen 24 anys.
Comprovació (també es pot fer copiant la fórmula =1,03*A1 cap avall en un full de càlcul): 1000·1,03²³ = 1973,59 € (no arriba a 2000) i 1000·1,03²⁴ = 2032,79 € (ja supera els 2000 €).

Cal comprovar que la fórmula compleix les dues condicions de la definició.
Primer terme: $2^{1}$ + 1 = 3 = $a_{1}$. Correcte.
Pas recursiu: si $a_{n}$ = $2^{n}$ + 1, llavors 2·$a_{n}$ - 1 = 2·($2^{n}$ + 1) - 1 = $2^{n+1}$ + 2 - 1 = $2^{n+1}$ + 1, que és la fórmula per a n + 1. Correcte.
Per tant és cert.
Comprovació numèrica: la recurrència dona 3, 2·3 - 1 = 5, 2·5 - 1 = 9, 2·9 - 1 = 17, 2·17 - 1 = 33, que són $2^{1}$ + 1, $2^{2}$ + 1, $2^{3}$ + 1, $2^{4}$ + 1, $2^{5}$ + 1.

Model d'algorisme:
n ← 1
mentre 3·n + 7 ≤ 100: n ← n + 1
mostra n i 3·n + 7
Mentre el terme no superi 100 (≤ 100), augmentem n; el bucle s'atura quan 3n + 7 > 100.
Resultat: 3n + 7 > 100 equival a n > 31, així que el bucle s'atura a n = 32 i mostra $a_{32}$ = 3·32 + 7 = 103.
Comprovació: $a_{31}$ = 3·31 + 7 = 100, que no supera 100.

Si n és parell es divideix entre 2; si és senar es multiplica per 3 i se suma 1.
7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.
Hi ha 16 fletxes, és a dir, 16 passos (17 valors comptant el 7 inicial i l'1 final).
Observació: els valors pugen fins a 52 abans de baixar. Es creu que, per a qualsevol nombre inicial, el procés acaba arribant a 1, però no s'ha demostrat: és un problema obert.

Es llisten els nombres del 2 al 60 i es tatxen, començant pel quadrat de cada primer, els múltiples dels primers que van apareixent: els de 2 (4, 6, 8, ...), els de 3 (9, 15, 21, ...), els de 5 (25, 35, 55) i els de 7 (49).
No cal anar més enllà perquè el primer següent, l'11, té $11^{2}$ = 121 > 60: tot nombre compost fins a 60 té un divisor primer ≤ $\sqrt{60}$ ≈ 7,7, de manera que ja ha quedat tatxat.
Primers que queden: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 i 59.
Són 17 primers.

Quan arriba la persona n + 1, saluda les n persones que ja hi eren: a_n+1 = a_n + n, amb a₂ = 1 (1, 1 + 2 = 3, 3 + 3 = 6, 6 + 4 = 10, ...).
Fórmula explícita: a_n = 1 + 2 + ... + (n - 1) = n·(n - 1)/2 (suma d'una progressió aritmètica). També és el nombre de parelles que es poden formar amb n persones: C_n,2.
Comprovació: n = 5 → 5·4/2 = 10.
Amb 30 persones: 30·29/2 = 435 encaixades.

Anota els dos punts de partida, que aquí en són dos i no un: a₁ = 1 i a₂ = 1.
Aplica la regla: a₃ = 1 + 1 = 2.
Continua: a₄ = 2 + 1 = 3, a₅ = 3 + 2 = 5, a₆ = 5 + 3 = 8 i a₇ = 8 + 5 = 13.
Escriu els set: 1, 1, 2, 3, 5, 8, 13.
Mira si la diferència és constant: de 1 a 2 hi va 1, de 2 a 3 en va 1, de 3 a 5 en van 2, de 5 a 8 en van 3. No ho és, o sigui que no és aritmètica.
Mira si el quocient és constant: 2/1 = 2 però 3/2 = 1,5. Tampoc, o sigui que no és geomètrica.
Conclou: com que no és de cap dels dos tipus que saps passar a explícita, aquí la recursiva és l'única manera de generar-la.

Fes el primer camí: 2·2·2·... amb deu factors, que són NOU multiplicacions.
Fes el segon: calcula $2^{2}$ = 4 (una multiplicació).
Eleva-ho al quadrat: $4^{2}$ = 16, que és $2^{4}$ (dues).
Torna a elevar-ho: $16^{2}$ = 256, que és $2^{8}$ (tres).
Falta arribar a l'exponent 10: multiplica per $2^{2}$ = 4 i dona 256 · 4 = 1024 (quatre).
Comprova que els dos camins donen el mateix: $2^{10}$ = 1024.
Compara: nou multiplicacions contra quatre, i el mateix resultat exacte. La millora no ve de calcular més de pressa, sinó d'haver vist que una part de la feina era innecessària.

Comprova primer que el segon no s'equivoca, que és la condició abans de mirar si és més ràpid.
Pensa què vol dir que un nombre no sigui primer: es pot escriure com un producte de dos factors, tots dos més grans que 1.
Si els dos factors fossin més grans que l'arrel quadrada, el producte seria més gran que el nombre. Això no pot ser.
Per tant, si hi ha divisors, ALMENYS UN és menor o igual que l'arrel quadrada: provar fins allà és suficient.
Compara el cost per a un nombre al voltant de 10.000: el primer fa unes 10.000 divisions i el segon, unes 100.
Fixa't d'on ve la millora: no de calcular més de pressa, sinó d'haver RAONAT que una part de la feina era innecessària.

Per moure n discos: primer es passen els n - 1 de dalt a la vareta auxiliar ($a_{n-1}$ moviments), després el disc gran a la vareta final (1 moviment) i finalment els n - 1 sobre el gran ($a_{n-1}$ moviments). Recurrència: $a_{n}$ = 2·$a_{n-1}$ + 1, amb $a_{1}$ = 1 (1, 3, 7, 15, 31, ...).
Fórmula explícita: si sumem 1 als valors obtenim 2, 4, 8, 16, 32, ..., potències de 2, així que $a_{n}$ = $2^{n}$ - 1. Comprovació: 2·($2^{n-1}$ - 1) + 1 = $2^{n}$ - 1.
Per a 20 discos: $a_{20}$ = $2^{20}$ - 1 = 1048575 moviments, és a dir, 1048575 s.
Com que un dia té 86400 s: $\tfrac{1048575}{86400}$ ≈ 12,1 dies seguits movent un disc cada segon.

Diferències primeres: 2 - 0 = 2, 5 - 2 = 3, 9 - 5 = 4. Diferències segones: 1 i 1 (constants), per tant la fórmula és quadràtica, d(n) = a·n² + b·n + c, amb 2a = 1, és a dir, a = 1/2.
Amb d(3) = 0 i d(4) = 2: 4,5 + 3b + c = 0 i 8 + 4b + c = 2. Restant: 3,5 + b = 2, d'on b = -1,5 i c = 0. Fórmula: d(n) = n²/2 - 3n/2 = n(n - 3)/2.
Justificació: cada vèrtex es pot unir amb n - 3 vèrtexs (no amb ell mateix ni amb els dos veïns) i cada diagonal es compta dues vegades.
Per a n = 12: 12·9/2 = 54 diagonals.
77 = n(n - 3)/2 → n² - 3n - 154 = 0 → n = (3 + √625)/2 = (3 + 25)/2 = 14 (la solució negativa no serveix). Comprovació: 14·11/2 = 77.

Primer cas: (252, 105): 252 = 2·105 + 42, així que passem a (105, 42); 105 = 2·42 + 21, passem a (42, 21); 42 = 2·21 + 0, passem a (21, 0). MCD(252, 105) = 21, en 3 iteracions.
Segon cas: (91, 35): 91 = 2·35 + 21 → (35, 21); 35 = 1·21 + 14 → (21, 14); 21 = 1·14 + 7 → (14, 7); 14 = 2·7 + 0 → (7, 0). MCD(91, 35) = 7, en 4 iteracions.
Per què funciona: si a = q·b + r, qualsevol divisor comú de a i b divideix també r = a - q·b, i qualsevol divisor comú de b i r divideix a = q·b + r. Així, els parells (a, b) i (b, r) tenen els mateixos divisors comuns i MCD(a, b) = MCD(b, r).
Els residus són cada cop més petits, de manera que el procés acaba en 0 després d'un nombre finit de passos.
Comprovació: 252 = 21·12 i 105 = 21·5, i 12 i 5 no tenen divisors comuns; 91 = 7·13 i 35 = 7·5.

Cada pas redueix la llista a la meitat: 1000 → 500 → 250 → 125 → 63 → 32 → 16 → 8 → 4 → 2 → 1. Són 10 passos ($2^{10}$ = 1024 ≥ 1000, mentre que $2^{9}$ = 512 < 1000).
Per a 1000000: $2^{19}$ = 524288 < 1000000 ≤ $2^{20}$ = 1048576, així que calen 20 passos.
La cerca un a un, en el pitjor cas, revisa tots els elements: 1000 i 1000000 comprovacions, respectivament.
Patró: cada cop que la llista es duplica, la cerca binària només necessita 1 pas més; si es multiplica per 1000, només uns 10 passos més. El nombre de passos creix com el logaritme en base 2 de n, molt més a poc a poc que n.

7¹ = 7, 7² = 49, 7³ = 343, 7⁴ = 2401, 7⁵ = 16807...: les unitats són 7, 9, 3, 1, 7, 9, 3, 1...; el patró es repeteix cada 4 potències (període 4).
Dividim l'exponent entre 4: 2026 = 4·506 + 2. El residu és 2, així que 7²⁰²⁶ acaba com 7², és a dir, en 9.
Per què es repeteix: la xifra de les unitats d'un producte només depèn de les xifres de les unitats dels factors. Com que 7⁴ acaba en 1, multiplicar per 7⁴ no canvia l'última xifra, i a partir d'aquí tot torna a començar.
Comprovació: 7⁶ = 117649 acaba en 9, com 7² (6 = 4 + 2).

Passada 1 (4 comparacions): 7 3 9 2 5 → 3 7 9 2 5 → 3 7 2 9 5 → 3 7 2 5 9. Llista: 3 7 2 5 9.
Passada 2 (3 comparacions): 3 7 2 5 → 3 2 7 5 → 3 2 5 7. Llista: 3 2 5 7 9.
Passada 3 (2 comparacions): 3 2 5 → 2 3 5. Llista: 2 3 5 7 9.
Passada 4 (1 comparació): 2 3 ja estan en ordre. Llista final: 2 3 5 7 9.
Total: 4 + 3 + 2 + 1 = 10 comparacions.
Per a n elements: (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 (suma d'una progressió aritmètica); per a n = 5, 5·$\tfrac{4}{2} = 10$.
Conseqüència: si la llista passa de 100 a 200 elements, les comparacions passen de 4950 a 19900, unes 4 vegades més; el cost creix com $n^{2}$.