Funcions:
ITERATIVE sum of odd values until an odd value - X71538
Primer exercici que em va sortir al segon examen. Podeu veure'n l'enunciat aquí. En essència, ens demana que de manera iterativa, fem la suma de tots els senars des de 0 a n. Per tant, ha de ser un for o un while, no serveix ni una versió recursiva, ni utilitzar la fórmula que va descobrir Gauss per sumar sèries de números... Aleshores, una opció seria:
int suma (int n) {
int r=0;
for (int i=1;i<=n;i+=2) {
r+=i;
}
return r;
}
És a dir, ens recorrem tots els números de 1 a n, saltant de 2 en 2, i els anem sumant a r. Finalment els retornem. Podríem fer-ho també amb un while, però seria similar. Jo quan vaig aprendre a programar era fan dels while, però cada cop m'agraden més els for
RECURSIVE sum of odd values until an odd value - X97800
Sorpresa! T'havies quedat amb ganes de fer-ho recursiu? Perquè el segon problema de l'examen demanava fer el mateix recursivament. Aquí podeu veure el problema, però realment és el mateix que abans. L'únic diferent és que aquest valia 2,5 punts, mentre que l'anterior en valia 2 (això era perquè així t'obligaven a fer el 3r o el 4t exercici si volies aprovar).
int suma(int n) {
if (n==1) return 1;
return n+suma(n-2);
}
No em digueu que no és màgica la recursivitat? Fem el mateix que al problema anterior, amb dues línies de codi. Si n és 1, sabem que la suma dels senars des de 1 fins a 1 és 1. Si no és 1, serà n més la suma dels que hi ha fins a n-2
Odd-even increasing sequences - X55755
Aquí podeu veure l'enllaç, perquè resumir-ho és difícil. En essència, havies de mirar que els elements en posició parell fossin creixents, i els elements en posició senar també (és a dir, la seqüència 1 3 2 4 ho compleix, ja que 2>1, i 4>3). Com ho faríem?
bool is_odd_even_increasing() {
int senar, parell;
bool es_senar=true;
cin >>senar>>parell;
int n;
while (cin >>n) {
if (es_senar) {
if (senar>n) return false;
senar=n;
}
else {
if (parell>n) return false;
parell=n;
}
es_senar=not es_senar;
}
return true;
}
int main() {
if(is_odd_even_increasing()) cout <<"yes"<<endl;
else cout <<"no"<<endl;
}
Emmagatzemem els dos primers números llegits. A partir d'aquí, anem llegint, i si la posició és senar, comparem amb l'anterior en posició senar. Si no, ídem amb parell. Aquest va ser el tercer del meu examen
Happiness index - X18514
Aquest va ser l'últim problema del meu examen. El teniu aquí
int suma_quadrats_elements(int n) {
if(n<10) return n*n;
int modul=n%10;
return modul*modul+suma_quadrats_elements(n/10);
}
int happiness_index(int n) {
if (n==1) return 1;
if (n==4) return -1;
int res=happiness_index(suma_quadrats_elements(n));
if (res==-1) return -1;
return res+1;
}
int main() {
int n;
int happy=0, sad=0;
while (cin >>n) {
int r=happiness_index(n);
cout <<n<<" has happiness index "<<r<<endl;
if (r==-1) ++sad;
else ++happy;
}
cout <<endl;
cout <<"happy numbers: "<<happy<<endl;
cout <<"sad numbers: "<<sad<<endl;
}
No em mateu, però realment jo veig molt la solució recursiva. Bàsicament, definim una funció que sumi els quadrats dels seus dígits. Si n==1, retornem 1 (per definició). Si n==4, retornem -1 (també per definició). Si no és cap dels dos, cridem recursivament la funció amb la suma dels quadrats. Si això ens retorna -1, retornem -1, perquè vol dir que és trist. I, si no, retornem el que ens doni més 1.
No obstant, jo recordo que, quan vaig fer aquest examen, la meva solució va ser iterativa. Per tant, també en puc posar una
int happiness_index(int n) {
int index=1;
while (n!=1 and n!=4) {
++index;
n=suma_quadrats_elements(n);
}
if (n==1) return index;
return -1;
}
Vectors
Segona subseqüència seguida de primera subseqüència - X62402
Com sempre, l'enllaç a l'enunciat.
void llegir_vector(vector<int>& v) {
int n=v.size();
for (int i=0;i<n;++i) {
cin >>v[i];
}
}
int main() {
int n, k;
cin >>n>>k;
vector<int> v(n);
llegir_vector(v);
int punt_tall=n-k;
for (int i=punt_tall;i<n;++i) {
if (i!=punt_tall) cout<<' ';
cout <<v[i];
}
for (int i=0;i<punt_tall;++i) {
cout <<' '<<v[i];
}
cout <<endl;
}
És a dir, calculem el punt de tall (que és n-k, perquè primer volem mostrar els n últims). Després, fem un for des d'aquest fins al final, mostrant. Finalment, un altre for, des del principi fins a aquest, per mostrar els primers
Codi Morse - X61261
Aquí teniu l'enllaç, per variar. En aquest problema, quan es va fer l'examen, hi va haver problemes amb el codi del PDF. Per tant, millor utilitzar la plantilla que penjo a la carpeta, ja que utilitzant el PDF el més probable és que no us vagi.
void encode_text_in_Morse(const vector<string>& MC) {
char c;
bool primer=true;
while (cin >>c) {
if ((c>='a' and c<='z') or (c>='A' and c<='Z')) {
if (not primer) cout <<' ';
if (c>='a' and c<='z') cout <<MC[c-'a'];
else cout <<MC[c-'A'];
primer=false;
}
}
cout <<endl;
}
És a dir, anar llegint. Si no és una lletra, ni cas, no té traducció al Morse. Si és una lletra, mostrem l'element del vector.
Index de Jaccard - X49511
L'enllaç. Recordo que quan vaig fer aquest, vaig fer molts càlculs inútils i, finalment, sempre em retornava 0, ja que estava dividint enters. Tot el càlcul ben plantejat, però sense tenir en compte que dividir dos enters dóna un enter.
void llegir(vector<int>& v) {
int n=v.size();
for (int i=0;i<n;++i) cin >>v[i];
}
int interseccio(const vector<int>& c1, const vector<int>& c2) {
int iguals=0;
int i=0,j=0;
while (i<int(c1.size()) and j<int(c2.size())) {
if (c1[i]==c2[j]) {
++iguals;
++i;
++j;
}
else if (c1[i]>c2[j]) ++j;
else ++i;
}
return iguals;
}
double jaccard (const vector<int>& c1, const vector<int>& c2) {
int intersec=interseccio(c1,c2);
return double(intersec)/(int(c1.size()+c2.size())-intersec);
}
int main() {
cout.setf(ios::fixed);
cout.precision(3);
int n;
while (cin >>n) {
vector<int> c1(n);
llegir(c1);
int m;
cin >>m;
vector<int> c2(m);
llegir(c2);
cout <<jaccard(c1,c2)<<endl;
}
}
La funció complexa és jaccard. El que fem és calcular la mida de la intersecció dels dos conjunts. Aquesta l'aprofito per calcular la de l'unió, ja que aquesta és la mida dels dos conjunts menys els elements comuns (que, a la suma, els estem comptant doble). Amb això, faig la divisió (tenint en compte que un dels dos elements ha de ser double, i que la funció size() retorna unsigned int
Matrius
Després de l'error de l'exercici del Codi Morse, els professors van culpar a la traducció del problema, i es va determinar que l'últim examen seria només en un idioma (com el segon, de fet). I, com que ja sabem que la FIB està a Cambridge, podem deduir quin idioma es va utilitzar
Is identity? - X35986
Aquí podeu consultar l'enunciat
bool is_identity(const Matrix& A) {
int n=A.size();
int m=A[0].size();
if (n!=m) return false;
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j) {
if (i==j and A[i][j]!=1) return false;
if (i!=j and A[i][j]!=0) return false;
}
}
return true;
}
És a dir, si no és quadrada, retornem false perquè no pot ser la identitat. Si és quadrada, la recorrem. Hem de comprovar que quan i=j hi hagi un 1, i quan i!=j un 0. Si en algun moment veiem que no es compleix, return false i fora. Si acabem el bucle, no hem trobat cap problema, i retornem true
Transpose - X37157
Per transposar una matriu, el que hem de fer és que les files passin a ser les columnes, i a la inversa. Com que en aquest cas volem crear una nova matriu, que sigui la transposada, ens haurem de recórrer tota la matriu.
void print_matrix(const Matrix& M) {
int n=M.size();
int m=M[0].size();
cout <<n<<' '<<m<<endl;
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j) {
if (j!=0) cout <<' ';
cout <<M[i][j];
}
cout <<endl;
}
cout <<endl;
}
// returns the transpose of the given non-empty matrix
Matrix transpose(const Matrix& M) {
int n=M.size();
int m=M[0].size();
Matrix mat(m,Row(n));
for (int i=0;i<n;++i) {
for (int j=0;j<m;++j) {
mat[j][i]=M[i][j];
}
}
return mat;
}
Matrix commands - X40782
Hey! Sembla que els dos primers exercicis de l'examen han sigut prou viables, no? Què ens demanen aquí? Doncs determinar si podem sumar dues matrius, i determinar si les podem multiplicar.
- Quan podrem sumar-les? Quan tinguin les mateixes dimensions
- Quan podrem multiplicar-les? Quan la quantitat de columnes de la primera matriu sigui igual a la de files de la segona
int main() {
char s;
while (cin >> s) {
int n, m;
cin >>n>>m;
Matrix M1=read_matrix(n,m);
int o, p;
cin >>o>>p;
Matrix M2=read_matrix(o,p);
if (s == '+') {
if (n!=o or m!=p) cout <<"The two matrices cannot be added."<<endl;
else print_matrix(matrix_sum(M1,M2));
cout <<endl;
} else if (s == '*') {
if (m!=o) cout <<"The two matrices cannot be multiplied."<<endl;
else print_matrix(matrix_product(M1,M2));
cout <<endl;
}
}
}
char s;
while (cin >> s) {
int n, m;
cin >>n>>m;
Matrix M1=read_matrix(n,m);
int o, p;
cin >>o>>p;
Matrix M2=read_matrix(o,p);
if (s == '+') {
if (n!=o or m!=p) cout <<"The two matrices cannot be added."<<endl;
else print_matrix(matrix_sum(M1,M2));
cout <<endl;
} else if (s == '*') {
if (m!=o) cout <<"The two matrices cannot be multiplied."<<endl;
else print_matrix(matrix_product(M1,M2));
cout <<endl;
}
}
}
La funció print_matrix pot ser la mateixa que a l'exercici anterior.
Orthonormal matrices - X43660
Si després d'haver llegit aquest títol, segueixes tenint ganes de fer-lo, aquí pots trobar-lo. En defensa de l'exercici, diré que el títol espanta, però aquest examen, comparat amb els anteriors, era fàcil.
bool orthonormal_matrix (const Matrix& Q) {
Matrix Qt=transpose(Q);
return is_identity(matrix_product(Q,Qt)) and is_identity(matrix_product(Qt,Q));
}
int main() {
int n, m;
bool primer=true;
while (cin >>n>>m) {
if (not primer) cout <<' ';
Matrix Q=read_matrix(n,m);
if (orthonormal_matrix(Q)) cout <<"yes";
else cout <<"no";
}
cout <<endl;
}
Ens diuen que una matriu és ortonormal si la transposada és igual a l'inversa. Ens donen l'aclaració de que multiplicant-la per la transposada, donaria la identitat. Per tant, és bastant obvi que hem de fer això. Per tant, calculem la transposada, i mirem si es compleix això
Nota: Si tens ganes, sempre pots utilitzar el mètode de Gauss per invertir la matriu, i comparar-les. Realment és molta més feina per tenir un cost equivalent, però si et fa il·lusió, endavant.
