El bucle exterior recorre i de 1 a 200, i per a cada i el bucle interior fa i passos. Quantes operacions es fan en total?
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
No són n2: el bucle interior no sempre fa el mateix nombre de passos.
Pista 2.
Has de sumar 1+2+⋯+200.
Com es fa
El compte correcte. El bucle interior fa 1 pas la primera vegada, 2 la segona, i així fins a 200:
∑i=1200i=2200⋅201=20100
Per què no és 40000. «Dos bucles niats» no és una unitat d'anàlisi: el que compta és quantes iteracions fa cadascun realment. Aquí el total és aproximadament la meitat del quadrat.
Asimptòticament sí que és Θ(n2), perquè la constant 1/2 no canvia l'ordre. Però la constant importa a la pràctica: un factor 2 és un factor 2 de temps real.
Compte amb això.
Multiplicar els dos límits com si el bucle interior fos sempre de longitud n.
Exercici 2
Quantes parelles diferents d'elements es poden formar amb una llista de 30 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 30 agafats de dos en dos.
Com es fa
El recompte.
(230)=230⋅29=435
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 30⋅29=870, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 30 a 60 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 3
Quantes parelles diferents d'elements es poden formar amb una llista de 35 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 35 agafats de dos en dos.
Com es fa
El recompte.
(235)=235⋅34=595
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 35⋅34=1190, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 35 a 70 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 4
Quantes parelles diferents d'elements es poden formar amb una llista de 40 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 40 agafats de dos en dos.
Com es fa
El recompte.
(240)=240⋅39=780
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 40⋅39=1560, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 40 a 80 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 5
Quantes parelles diferents d'elements es poden formar amb una llista de 45 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 45 agafats de dos en dos.
Com es fa
El recompte.
(245)=245⋅44=990
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 45⋅44=1980, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 45 a 90 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 6
Quantes parelles diferents d'elements es poden formar amb una llista de 50 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 50 agafats de dos en dos.
Com es fa
El recompte.
(250)=250⋅49=1225
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 50⋅49=2450, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 50 a 100 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 7
Quantes parelles diferents d'elements es poden formar amb una llista de 60 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 60 agafats de dos en dos.
Com es fa
El recompte.
(260)=260⋅59=1770
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 60⋅59=3540, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 60 a 120 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 8
Quantes parelles diferents d'elements es poden formar amb una llista de 70 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 70 agafats de dos en dos.
Com es fa
El recompte.
(270)=270⋅69=2415
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 70⋅69=4830, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 70 a 140 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 9
Quantes parelles diferents d'elements es poden formar amb una llista de 80 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 80 agafats de dos en dos.
Com es fa
El recompte.
(280)=280⋅79=3160
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 80⋅79=6320, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 80 a 160 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Exercici 10
Quantes parelles diferents d'elements es poden formar amb una llista de 100 elements? (És el nombre de comparacions que fa un algorisme que compara tothom amb tothom.)
Escriu només el número. Si no és enter, posa tres o quatre decimals.
Pots escriure fraccions (3/4), decimals amb punt o coma, e, π i arrels (sqrt(2)).
Pista 1.
Cada element es compara amb tots els altres, però cada parella es compta dues vegades.
Pista 2.
És el coeficient binomial de 100 agafats de dos en dos.
Com es fa
El recompte.
(2100)=2100⋅99=4950
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 100⋅99=9900, però cada parella hi surt dues vegades (un cop en cada ordre). Dividint per dos queda el nombre real de parelles.
El que en diu l'asimptòtica. Aquest recompte és Θ(n2), i per això els algorismes que comparen tothom amb tothom es fan impracticables de pressa: passar de 100 a 200 elements multiplica la feina aproximadament per quatre, no per dos.
Compte amb això.
Donar el producte sense dividir per dos, comptant cada parella dues vegades.
Com escriure les respostes. A les integrals pots posar-hi la constant (+ C) o deixar-la: es dona per bona igual. Fes servir ^ per als exponents (x^2), * o res per multiplicar (3x i 3*x valen igual), / per dividir i sqrt( ) per a les arrels. Les funcions s'escriuensin(x), cos(x), ln(x), e^x. No cal que simplifiquis: qualsevol forma equivalent es dona per bona.
Has fallat algun exercici.Repassa'ls abans de continuar: el que has de repetir és justament el que no et surt.
Galetes
Fem servir galetes tècniques (necessàries perquè el lloc funcioni) i, si ens hi dones permís, galetes d'analítica i de publicitat que ens ajuden a mantenir els apunts gratuïts. Pots acceptar-les, rebutjar-les o triar-les una per una. Detall a la política de galetes.