Nombre de rotacions (2) P55375


Statement
 

pdf   zip   main.cc   main.py

thehtml

Donat un vector (no buit) circularment ordenat d’enters, es vol trobar el nombre de cops que s’ha rotat. Assumiu que no hi ha duplicats al vector i que la rotació és en sentit antihorari.

Per exemple, [8, 9, 10, 2, 5, 6] s’ha rotat tres cops, [9, 10, 2, 5, 6, 8] s’ha rotat dos cops, [4, 0, 1, 2, 3] s’ha rotat un cop, i [2, 5, 8, 9, 12] s’ha rotat zero cops.

Resoleu aquest problema recursivament en temps logarítmic, usant aquesta capçalera per a C++:

int number_of_rotations (const vector<int>& v);

o aquesta per a Python:

number_of_rotations(v: list[int]) -> int

Doneu l’especificació de la funció recursiva que necessitareu escriure en un comentari a l’inici de tal funció.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Information
Author
Jordi Petit
Language
Catalan
Other languages
English
Official solutions
C++ Python
User solutions
C++ Python