Quantes parelles diferents d'elements es poden formar amb una llista de 120 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 120 agafats de dos en dos.
Com es fa
El recompte.
(2120)=2120⋅119=7140
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 120⋅119=14280, 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 120 a 240 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 2
Quantes parelles diferents d'elements es poden formar amb una llista de 200 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 200 agafats de dos en dos.
Com es fa
El recompte.
(2200)=2200⋅199=19900
El perquè de la divisió. Si comptes «cada element contra tots els altres» obtens 200⋅199=39800, 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 200 a 400 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.