Problemi di consegne

[Ranze1]

Ciao!
Vi pongo il mio problema di informatica
Tra non molto dovrò dare informatica 2 e...non riesco a fare gli esercizi perché non capisco le consegne...
Mi spiego meglio. Se mi dite:fai un programma che faccia questo io lo so fare, gira e fa quel che deve, ma il prof vuole che lo facciamo seguendo un certo schema che ci dà e non "a modo nostro"... tipo rispettando certe clausule sulla complessità o usando certe strutture in particolare...
C'è qualcuno che può aiutarmi vedendo i testi insieme a me?
Grazie 1000
Ranze

[TomSawyer1]

Posta le consegne, poi si vedrà se qualcuno sarà in grado di aiutarti.

[Ranze1]

Esercizio 1

Sia dato un vettore di interi v[0..n-1] ed una coppia di indici p < r tali che p..r sia un sottointervallo di 0..n-1. Si vuole permutare sul posto gli elementi di v[p..r] in modo che, posto x = v

, esista j in p..r t.c. il vettore risultante v’[p..r] sia ripartito in una parte v’[p..j-1] di valori < x con v’[j-1] = x, ed una parte v’[j..r] di valori > x, detta partizione di v[p..r] intorno al perno x. La funzione ritorna la posizione del perno, ossia j-1.

Per realizzare la funzione C++

int Perno (int v[], int p, int r)
// pre: p <= r < dimensione di v[], x = v

// post: se y in v[p..j-1] allora y <= x, v[j-1] == x,
// se z in v[j..r] allora z > x;
// ritorna j-1

si parta dall’invariante rappresentato dal seguente disegno

- --------------------------- ------------------ ----------
p el.<=x=v

j el.>x i r

Che significa l'invariante che devo usare?

[Ranze1]

Per favore aiutatemi ;-(