Problema en c++ - Números k-emparejados

[MariCarmeniii]

Algoritmo iterativo.

El problema:
Dos números se llaman k-emparejadoscuando cuando el  valor  absoluto  de  su  diferencia  es  exactamente k(es decir, u y v están k-emparejados cuando |u–v| = k ). Por ejemplo, 7 y 14 están 7-emparejados. Observa que todo número está 0-emparejado consigo mismo. Diseña  un algoritmo eficiente que, dado un vector estrictamente  creciente de  enteros int a[n] (n>=0) y un número k>=0, determine el número de parejas de números en a que están k-emparejados.

La  entrada  termina  con  una  línea que  empieza por -1. Cada  vez que  lee  un caso de  prueba, el  programa invoca  a  una  función num_k_emparejados que  determina  el  número  de  parejas  de  números k-emparejados, y escribe dicho número por la salida estándar.  A  continuación,  se  muestra  un  ejemplo  de  entrada  procesable  por  este  programa,  y  de salida  producida (suponiendo una implementación adecuada de num_k_emparejados):

Entrada                Salida
5 3                          2
1 4 5 6 8                  1
4 2                          3
1 4 5 6                    
3 0                            
1 2 3
-1

Esqueleto de lo que llevo:

Código [Seleccionar] Expandir


#include <algorithm>
#include <iostream>

using namespace std;


/*

PRECONDICION DE LA FUNCION:

 
*/
unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k);
/*
POSTCONDICION DE LA FUNCION:

 
*/



unsigned int num_k_emparejados(int v[], unsigned int n, unsigned int k) {
   /* CUERPO DE LA FUNCION */

}

/*
Complejidad: orden de complejidad del algoritmo:

*/



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());
}



Si me podéis ayudar con la función unsigned int num_k_emparejados lo agradecería.

[K-YreX]

Te dejo este tema que es de hace muy poco tiempo y creo que se trató este mismo tema. Quizás pueda servirte.
https://foro.elhacker.net/programacion_cc/problema_kpaired_kemparejados_en_on-t499246.0.html

[MariCarmeniii]

Sii muchas gracias, lo he estado ojeando antes de subir el tema pero no me sirve porque no es en modo iterativo pero muchas gracias por responder =)

[K-YreX]

El modo de resolución a mí sí me parece que es iterativo. Si no es lo que buscas añade un poco más de código para ver qué es lo que quieres implementar.

[MariCarmeniii]

Hola chic@s, os dejo la solución del problema:

Código [Seleccionar] Expandir


#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.