Examen Laboratori 2016 X30839
arrows
Sigui v un vector d’enters. Una 1-rotació del vector v
és un vector en què els elements del vector v estan desplaçats una posició
a l’esquerra.
Per exemple, si tenim el vector:
[main node] (1) 2; [main node] (2) [right of=1] 3; [main node] (3) [right of=2] 1; [main node] (4) [right of=3] 5; [main node] (5) [right of=4] 4;
Si hi apliquem una 1-rotació en aquest vector, tots els elements van a la posició de l’esquerra, llevat del primer, que va a parar a la darrera posició del vector:
[main node] (1) 2; [main node] (2) [right of=1] 3; [main node] (3) [right of=2] 1; [main node] (4) [right of=3] 5; [main node] (5) [right of=4] 4;
[->] (2) – (1); [->] (3) – (2); [->] (4) – (3); [->] (5) – (4); [->] (1) to [out=150,in=30] (5);
i, finalment, queda aquest vector:
[main node] (1) 3; [main node] (2) [right of=1] 1; [main node] (3) [right of=2] 5; [main node] (4) [right of=3] 4; [main node] (5) [right of=4] 2;
En general, una n-rotació és un vector que ha estat rotat
n vegades a l’esquerra. Per exemple, pel vector:
[main node] (1) 2; [main node] (2) [right of=1] 3; [main node] (3) [right of=2] 1; [main node] (4) [right of=3] 5; [main node] (5) [right of=4] 4;
una 3-rotació és l’aplicació d’una 1-rotació tres vegades:
(0) 1a;
[main node] (1) [right of=0] 3; [main node] (2) [right of=1] 1; [main node] (3) [right of=2] 5; [main node] (4) [right of=3] 4; [main node] (5) [right of=4] 2;
(0) 2a;
[main node] (1) [right of=0] 1; [main node] (2) [right of=1] 5; [main node] (3) [right of=2] 4; [main node] (4) [right of=3] 2; [main node] (5) [right of=4] 3;
(0) 3a;
[main node] (1) [right of=0] 5; [main node] (2) [right of=1] 4; [main node] (3) [right of=2] 2; [main node] (4) [right of=3] 3; [main node] (5) [right of=4] 1;
Si N = length(v), tenim que una N-rotació de v
té, com a resultat, el mateix vector v.
De fet, podem considerar que una N-rotació és equivalent a una
0-rotació (en què no fem cap rotació).
Cal que feu una funció que, donats dos vectors v1 i v2,
torni TRUE si i només si v2 és una i-rotació de v1,
per a alguna 1 ≤ i ≤ length(v1).
És a dir, si v2 és igual a una i-rotació de v1.
Ja teniu la capçalera d’aquesta funció al fitxer enunciat.R:
es_rotacio <- function (v1, v2)
Per exemple, si tenim:
(0) v1:;
[main node] (1) [right of=0] 2; [main node] (2) [right of=1] 3; [main node] (3) [right of=2] 1; [main node] (4) [right of=3] 5; [main node] (5) [right of=4] 4;
(0) v2:;
[main node] (1) [right of=0] 1; [main node] (2) [right of=1] 5; [main node] (3) [right of=2] 4; [main node] (4) [right of=3] 2; [main node] (5) [right of=4] 3;
la funció tornarà TRUE, ja que v2 és una 2-rotació de v1.
En canvi, si tenim:
(0) v1:;
[main node] (1) [right of=0] 2; [main node] (2) [right of=1] 3; [main node] (3) [right of=2] 1; [main node] (4) [right of=3] 5; [main node] (5) [right of=4] 4;
(0) v2:;
[main node] (1) [right of=0] 1; [main node] (2) [right of=1] 4; [main node] (3) [right of=2] 5; [main node] (4) [right of=3] 2; [main node] (5) [right of=4] 3;
la funció tornarà FALSE ja que v2 no és una 1-rotació,
ni una 2-rotació, 3-rotació 4-rotació ni una 5-rotació.
En cas que v1 i v2 vectors siguin iguals, la funció tornarà TRUE,
ja que v2 és una 5-rotació de v1.
Per a resoldre aquest exercici, podeu fer dues funcions auxiliars:
- una funció auxiliar que, donat un vector, en calcula la 1-rotació.
- una funció auxiliar que, donats dos vectors, torna
TRUEsi i només si tots dos vectors són iguals.
Observació
Al fitxer public.tar hi ha el fitxer enunciat.R
que conté l’esquelet del programa. Fes-lo servir, però no modifiquis
la part indicada. Aquest fitxer el pots fer servir també en l’entorn R.
Entrada
2 vectors v1 i v2 d’enters.
Sortida
TRUE si i només si v2 és una i-rotació de v1.
Input
5 2 3 1 5 4 1 5 4 2 3
Output
TRUE
Input
5 2 3 1 5 4 1 4 5 2 3
Output
FALSE
Input
10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
TRUE
- Author
- Jaume Baixeries
- Language
- Catalan
- Official solutions
- R
- User solutions
- R