Hola chic@s, os dejo la solución del problema:
Por si os interesa, saludos.
Código [Seleccionar]
#include <algorithm>
#include <iostream>
using namespace std;
/*
PRECONDICION DE LA FUNCION:
---Escribe aqu� la precondici�n de la funci�n.
0<=n<=tam(v) && crec(v,n)
*/
unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k);
/*
POSTCONDICION DE LA FUNCION:
---Escribe aqu� la poscondici�n de la funci�n. Para refirte
---al valor devuelto por la funci�n, utiliza la pseudo-variable
---'res'
(1) Definiciones auxiliares (si procede):
crec(v,n) = PARATODO i: 0<=i<n-1: v[i] < v[i+1]
num_k_emp(v,n,k) = #i,j:0<=i<=j<n:|v[i]-v[j]|=k
(2) Postcondici�n
res = num_k_emp(v,n,k)
*/
/* DISE�O DEL ALGORITMO:
--- Detalla aqu� el proceso seguido para dise�ar el
--- algoritmo
PASO 1. Variables
v,n,res,i,j
PASO 2. Invariante
(1) res = num_k_emp_hasta(v,n,k,i)
donde
num_k_emp_hasta(v,n,k,t) = #u,w:0<=u<=w<n && u < t:|v[u]-v[w]|=k
(2) 0 <= i <= j <= n
(3) no_k_emp(v,k,i,j)
donde no_k_emp(v,k,i,j) = PARATODO u,w: i<=u<=w<j: |v[u]-v[w]|<k
PASO 3. Inicializaci�n:
i=0
j=0
res = num_k_emp_hasta(v,n,k,j) = num_k_emp_hasta(v,n,k,0) =
(#u,w:0<=u<=w<n && u < 0:|v[u]-v[w]|=k) =
(#u,w:false:|v[u]-v[w]|=k) = 0
PASO 4: Continuaci�n y finalizaci�n:
j != n
* Si j = n, entonces:
(1) El invariante asegura que res = num_k_emp_hasta(v,n,k,i)
(2) Tambi�n asegura que no_k_emp(v,k,i,j)
(3) Por tanto, res = num_k_emp_hasta(v,n,k,j)
(4) Pero,como j=n, entonces res = num_k_emp_hasta(v,n,k,n)
PASO 5: Cuerpo del bucle. Como 0 <= i <= j <= n y adem�s j != n
(por la condici�n del bucle), podemos asegurar que 0<=i<n y
0<=j < n. Por tanto, tanto v[i] como v[j] tienen sentido.
* Si |v[i]-v[j]|<k:
(1) Incrementamos j, para hacer la diferencia m�s grande.
Esto afecta a:
(1) 0 <= i <= j <= n. Pero, como 0 <= j <n antes
del incremento, despu�s de incrementar j
el t�rmino sigue siendo v�lido.
(2) no_k_emp(v,k,i,j). Pero, como |v[i]-v[j]|<k, y
como v es estrictamente creciente, entonces
el t�rmino se preserva.
* Si |v[i]-v[j]|>k: Incrementamos i. Esto afecta a:
(1) 0 <= i <= j <= n. Pero como, antes de incrementar i,
0 <= i <=j, y |v[i]-v[j]|>k asegura que i < j (por ser
v estrictamente creciente), el t�rmino se preserva tras
incrementar i.
(2) res = num_k_emp_hasta(v,n,k,i). Pero, como
se cumpl�a: (i) no_k_emp(v,k,i,j);
(ii) |v[i]-v[j]|>k; (iii) el vector es estrictamente
creciente, por lo que, al ser |v[i]-v[j]|>k,
no podemos encontrar un w > j, tal que
|v[i]-v[w]|=k, tras incrementar i podemos
asegurar que el t�rmino contin�a verific�ndose.
* Si |v[i]-v[j]|=k. En este caso:
(1) Incrementamos 'res', al haber encontrado una
nueva k-pareja.
(2) Pero esto afecta a res = num_k_emp_hasta(v,n,k,i).
Como el vector es estrictamente creciente,
y como |v[i]-v[j]|=k, no habr� w > j, tal que
|v[i]-v[w]|=k. Por tanto, para reestablecer el
t�rmino basta incrementar i. Pero esto afecta:
(2.1) A no_k_emp(v,k,i,j). Pero como, antes de
incrementar i, se cumple para v[i..j),
podemos asegurar que se cumpl�a tambi�n
para v(i..j). Por tanto, tras incrementar
i el t�rmino sigue siendo v�lido.
(2.2) A 0 <= i <= j <= n. Si, antes del incremento,
i=j, el t�rmino se viola. Para evitarlo, en
este caso debemos incrementar j. Pero entonces,
puede verse afectado:
(2.1.1) 0 <= i <= j <= n. Pero este
t�rmino sigue cumpli�ndose, ya
que, tras incrementar j, i=j
(al serlo antes de incrementar i y j),
y adem�s 0<=j<n.
(2.1.2) no_k_emp(v,k,i,j). Pero, como i=j,
esto es no_k_emp(v,k,i,i) =
PARATODO u,w: i<=u<=w<i: |v[u]-v[w]|<k
= true.
PASO 6: Terminaci�n
2n - (i+j) es una expresi�n de cota.
* Como en cada iteraci�n se incrementa i o j, la expresi�n
disminuye.
* Adem�s, podemos comprobar que 2n - (i+j) >= 0 es un invariante
del bucle:
- Al inicializar i=j=0, 2n - (i+j) = 2n >= 0.
- Supongamos que 2n - (i+j) >= 0 se cumple al entrar en
el cuerpo del bucle. Como i < n y j <n,
2n - (i+j) no va a ser m�s peque�a que
2n - ((n-1)+(n-1)) = 2n - 2n + 2 = 2.
Por tanto, en el caso m�s extremo en el que incrementamos
tanto i como j, a la salida del bucle 2n - (i+j) no
va a ser m�s peque�a que 0.
*/
unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k) {
int i=0;
int j=0;
int res=0;
while (j!=n) {
int d = v[j]-v[i];
if (d < k) {
j++;
}
else {
if (d == k) {
res++;
if (i == j) j++;
}
i++;
}
}
return res;
}
/*
Complejidad: Determina justificadamente el orden de complejidad
de este algoritmo:
* Con la expresi�n de cota hemos visto que el bucle no da
m�s de 2n vueltas. Como el cuerpo se ejecuta en tiempo
constante, la complejidad es lineal ( O(n) ).
*/
bool procesa_caso() {
int v[100];
int n, k;
cin >> n;
if (n != -1) {
cin >> k;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << num_k_emparejados(v, n, k) << endl;
return true;
}
else {
return false;
}
}
int main() {
while (procesa_caso());
}
Por si os interesa, saludos.