Dependències Funcionals W37218

Statement

Sigui una matriu $n \times m$ d’enters. Aquesta matriu representa una taula de dades de $n$ files i $m$ columnes ( $n \geq 2$ i $m \geq 2$ ).

Diem que la dependencia funcional x -> y entre dues columnes x i y, és vàlida a la matriu M si i només si per a tot parell de files i i j (on $i < j$ ) passa això:

quan les dues files i i j tenen el mateix valor a la columna x, aleshores també tenen el mateix valor a la columna y.

Per exemple, sigui la taula (matriu) M de 5 files i 4 columnes:

1	2	2	5
3	5	4	1
1	2	2	5
2	1	3	2
2	1	3	1

Considerem la dependència funcional 0 -> 1. Veiem que els valors de la columna 0 coincideixen en les files 0 i 2:

1	2	2	5
1	2	2	5

i també en les files 3 i 4:

2	1	3	2
2	1	3	1

I veiem que en tots dos casos els valors de la columna 1 també són iguals. I això passa per a tot parell de files. Per tant, la dependència funcional 0 -> 1 és vàlida.

En canvi, la dependència funcional 0 -> 3 no és vàlida perquè tot i que, per exemple, els valors de les columnes 0 i de 3 coincideixen a les files 0 i 2:

1	2	2	5
1	2	2	5

no passa igual en les files 3 i 4, en què coincideixen els valors de la columna 0, però no els valors de la columna 3:

2	1	3	2
2	1	3	1

En aquest cas, podem dir que les files 3 i 4 invaliden 0 -> 3.

Tingueu en compte que, donada una dependència funcional x -> y (on x i y són identificadors de columnes), si els valors de x no coincideixen en dues files, llavors aquestes dues files no poden invalidar la dependència funcional, independentment de si els valors de la columna y són o no iguals. Per exemple, les files 0 i 1 no tenen el mateix valor a la columna 0:

1	2	2	5
3	5	4	1

Per tant, no poden invalidar la dependència 0 -> 1 tot i que el valor de la columna 1 tampoc no coincideixi.

Fes una funció dependencia_funcional amb la següent declaració i especificació:

/*
 * PRE:  M.size() > 0 and M[0].size() > 0 and 0 <= x,y < M[0].size().
 *
 * POST: Retorna true si i només si la dependència funcional x -> y
 * 		 és vàlida a la matriu M.        
 */
bool dependencia_funcional(const Matriu& M, int x, int y);

Observació

Només cal enviar la funció que us demanem (i les funcions que hagueu pogut declarat vosaltres).

A més, al fitxer que envieu cal que també hi hagi això:

#include <iostream>
#include <vector>
using namespace std;

typedef vector <int>   Vector;
typedef vector<Vector> Matriu;

No es pot fer servir l’ordenació del C++: std::sort. Tampoc no es pot fer servir el mètode push_back() de la classe vector.

Si voleu, podeu fer servir les funcions min, max o swap.

Cal tenir en compte que la relació entre dues files i i j respecte a la dependència x -> y és simètrica. És a dir, si el parell de files i i j no invaliden la dependència x -> y, el parell j i i tampoc. Per això a la definició de la dependència especifiquem $i < j$ .

Entrada

L’entrada és una matriu i una seqüència de dependències funcionals. De la lectura ja se n’encarrega el programa principal.

Sortida

La sortida són els resultats per a cada dependència funcional. De l’escriptura també se n’encarrega el programa principal.

Public test cases

Input

Output

0->1 SI
0->2 SI
0->3 NO
1->0 SI
1->2 SI
1->3 NO
2->0 SI
2->1 SI
2->3 NO
3->0 NO
3->1 NO
3->2 NO

Input

2 5
1  2  2  5  2
2  1  3  2  4

0 -> 1
0 -> 2
0 -> 3
0 -> 4
1 -> 0
1 -> 2
1 -> 3
1 -> 4
2 -> 0
2 -> 1
2 -> 3
2 -> 4
3 -> 0
3 -> 1
3 -> 2
3 -> 4
4 -> 0
4 -> 1
4 -> 2
4 -> 3

Output

0->1 SI
0->2 SI
0->3 SI
0->4 SI
1->0 SI
1->2 SI
1->3 SI
1->4 SI
2->0 SI
2->1 SI
2->3 SI
2->4 SI
3->0 SI
3->1 SI
3->2 SI
3->4 SI
4->0 SI
4->1 SI
4->2 SI
4->3 SI

Input

Output

0->1 SI
0->2 SI
1->0 NO
1->2 NO
2->0 SI
2->1 SI

Information

Author: PRO1
Language: Catalan
Other languages: Spanish
Official solutions: C++
User solutions: C++