Ejemplos

Insertar un valor o un vector en otro vector manteniendo intacto el original

Descripción del programa

El objetivo es implementar dos variantes de inserción: la que insertar un valor y la que inserta un vector. Para verificar su corrección nos ayudaremos de programas de prueba que:

  1. Definan e inicialicen vectores, por ejemplo, de tipo double

  2. Inserte el valor o el segundo vector en todas las posibles posiciones del primero. ¡La función debe mantener los vectores originales inalterados!

  3. Muestre en cada iteración el nuevo vector.

Diseño del programa

La función de inserción de un valor en una posición del vector puede tener el siguiente prototipo:

vector<double> inserta(const vector<double>& v, size_t pos, double valor);

Una posible implementación es la que sigue:

vector<double> inserta(const vector<double>& v, size_t pos, double valor)
{
   if (pos > v.size())
   {
      cout << "Fallo en la funcion inserta().\n"
           << "El índice " << pos << " de inserción está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }
   vector<double> w;
   w.reserve(v.size()+1);  // Opcional

   for (size_t i = 0; i < pos; ++i)
      w.push_back(v[i]);
   w.push_back(valor);
   for (size_t i = pos; i < v.size(); ++i)
      w.push_back(v[i]);
   return w;
}

Nótese cómo se copian los valores del vector original en el intervalo [0, pos-1], posteriormente se carga el valor en la posición pos para finalmente copiar el resto de valores del intervalo [pos, size()-1].

Dado que el valor pos puede estar fuera de los límites válidos de inserción, se gestiona con un mensaje de error, dando por finalizado el programa. Observe que no nos preocupamos de gestionar una posición negativa. Es imposible: la variable pos es de tipo size_t, ¡sin signo!

Una función main() para realizar un programa de prueba se muestra a continuación:

int main()
{
   vector<double> v{0, 1, 2, 3, 4, 5};

   for (size_t i = 0; i <= v.size(); ++i)
   {
      auto w = inserta(v, i, 1000);
      cout << "Inserción en posición " << i << endl;
      muestra_vector(w);
      cout << endl;
   }
   // auto w = inserta(v, -1, 1000);  // Descomenta esta línea y comenta la siguiente
   auto w = inserta(v, v.size() + 1, 1000);
}

Edita, compila y ejecuta el código

Esta función de prueba inserta un valor ficticio (dummy) igual a 1000 en todas y cada una de las posibles posiciones de inserción. Además, verifica que si la posición no es válida, genera un mensaje de error. Observe el valor que muestra el mensaje de error cuando enviamos -1 como posición.

La función que inserta el vector es muy similar. Su prototipo puede ser:

vector<double> inserta(const vector<double>& u, size_t pos, const vector<double>& v);

De forma similar a la versión para insertar un valor, una posible implementación es la que sigue:

vector<double> inserta(const vector<double>& u, size_t pos, const vector<double>& v)
{
   if (pos > u.size())
   {
      cout << "Fallo en la funcion inserta().\n"
           << "El índice " << pos << " de inserción está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }
   vector<double> w;
   w.reserve(u.size() + v.size());  // Opcional

   for (size_t i = 0; i < pos; ++i)
      w.push_back(u[i]);
   for (auto x : v)
      w.push_back(x);
   for (size_t i = pos; i < u.size(); ++i)
      w.push_back(u[i]);
   return w;
}

Finalmente, una función main() para testar la función de inserción de un vector podría ser la siguiente:

int main()
{
   vector<double> u{0, 1, 2, 3, 4, 5};
   vector<double> v{100, 101, 102};

   for (size_t i = 0; i <= u.size(); ++i)
   {
      auto w = inserta(u, i, v);
      cout << "Inserción en posición " << i << endl;
      muestra_vector(w);
      cout << endl;
   }
   // auto w = inserta(u, -1, v);  // Descomenta esta línea y comenta la siguiente
   auto w = inserta(u, u.size() + 1, v);
}

Edita, compila y ejecuta el código

Nota

El contenedor vector dispone de una función miembro insert() sobrecargada con características similares a las funciones que acabamos de estudiar, salvo por un importante detalle: la función actúa sobre el propio vector, modificándolo.

Borrar elementos de un vector manteniendo intacto el original

Descripción del programa

De nuevo, el objetivo es implementar dos variantes de borrado: la que elimina un elemento en una determinada posición y la que elimina los valores en un rango. Para verificar su corrección nos ayudaremos de programas de prueba que:

  1. Definan e inicialicen un vector, por ejemplo, de tipo double

  2. Borren un elemento en una posición o en un rango de posiciones ¡La función debe mantener el vector original inalterado!

  3. Muestren el nuevo vector

Diseño del programa

La función de borrado de un elemento en una determina posición puede tener el siguiente prototipo:

vector<double> borra(const vector<double>& v, size_t pos);

Una posible implementación es la que sigue:

vector<double> borra(const vector<double>& v, size_t pos)
{
   if (pos >= v.size())
   {
      cout << "Fallo en la funcion borra().\n"
            << "El índice " << pos << " de borrado está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }
   vector<double> w;
   w.reserve(v.size()-1);  // Opcional

   for (size_t i = 0; i < pos; ++i)
      w.push_back(v[i]);
   for (size_t i = pos+1; i < v.size(); ++i)
      w.push_back(v[i]);
   return w;
}

Esta función es muy similar a la vista en el caso de inserción de un valor. Se copian los valores del vector original en el intervalo [0, pos-1] y luego el resto de valores del intervalo [pos+1, size()-1].

De la misma forma, dado que el valor pos puede estar fuera de los límites válidos de borrado, se gestiona con un mensaje de error, dando por finalizado el programa. En este caso, los valores válidos para pos pertenecen al rango [0, size()-1].

Ae muestra a continuación una función main() para realizar un programa de prueba que borra un elemento en todas las posibles posiciones :

int main()
{
   vector<double> v{0, 1, 2, 3, 4, 5};
   for (size_t i = 0; i < v.size(); ++i)
   {
      auto w = borra(v, i);
      cout << "Borrado del elemento en posición " << i << endl;
      muestra_vector(w);
   }
   // auto w = borra(v, -1);  // Descomenta esta línea y comenta la siguiente
   auto w = borra(v, v.size());
}

Edita, compila y ejecuta el código

La función que borra un rango de posiciones es muy similar. Su prototipo puede ser:

vector<double> borra(const vector<double>& u, size_t ini, size_t fin);

Una posible implementación es la que sigue:

vector<double> borra(const vector<double>& v, size_t ini, size_t fin)
{
   if (ini >= v.size())
   {
      cout << "Fallo en la funcion borra().\n"
            << "La posición inicial " << ini << " está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }
   else if (fin >= v.size())
   {
      cout << "Fallo en la funcion borra().\n"
            << "La posición final " << fin << " está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }
   else if (ini > fin)
   {
      cout << "Fallo en la funcion borra().\n"
            << "La posición de borrado inicial es superior a la final.\n";
      exit(EXIT_FAILURE);
   }
   vector<double> w;
   w.reserve(v.size() - (fin - ini + 1));  // Opcional

   for (size_t i = 0; i < ini; ++i)
      w.push_back(v[i]);
   for (size_t i = fin+1; i < v.size(); ++i)
      w.push_back(v[i]);
   return w;
}

El código es muy similar a la versión para una única posición. La mayor diferencia está en la gestión de los posibles valores inválidos para el rango de posiciones. Así, no se permite el caso inf > sup.

La función main() para realizar un programa de prueba borra todos los posibles rangos de posiciones del vector, usando dos bucles for anidados. Se muestra a continuación:

int main()
{
   vector<double> v{0, 1, 2, 3, 4, 5};

   for (size_t i = 0; i < v.size(); ++i)
   {
      for (size_t j = i; j < v.size(); ++j)
      {
         auto w = borra(v, i, j);
         cout << "Borrado de los elementos en el rango [" << i << "," << j << "]\n";
         muestra_vector(w);
         cout << endl;
      }
   }
   // Descomenta una línea y comenta las otras
   auto w = borra(v, -1, 1);
   //auto w = borra(v, 1, v.size());
   //auto w = borra(v, 2, 1);
}

Edita, compila y ejecuta el código

Nota

El contenedor vector dispone de una función miembro erase() sobrecargada con características similares a las funciones que acabamos de estudiar, salvo por un importante detalle: la función actúa sobre el propio vector, modificándolo.

Insertar un valor o un vector en otro vector alterando el original

Descripción del programa

Las variantes de inserción vistas más arriba permiten alterar el vector original sin más que usar:

v = insertar(v,...);

Debido a la semántica de movimiento, esta operación de asignación apenas tiene coste computacional.

Imaginemos que deseamos insertar los datos de un nuevo cliente en un listado alfabético con gran número de clientes ya existente. Para contenedores de gran tamaño, donde el objetivo final es alterar el vector original, estas variantes de inserción analizadas pueden ser computacionalmente ineficientes.

Diseño del programa

Ahora basta con desplazar los elementos desde la posición de inserción, dejando los anteriores inalterados.

Esto es básicamente lo que hace la función miembro insert(). En nuestra emulación para insertar un valor, el prototipo será:

void inserta(vector<double>& v, size_t pos, double valor);

Una posible implementación es:

void inserta(vector<double>& v, size_t pos, double valor)
{
   if (pos > v.size())
   {
      cout << "Fallo en la funcion inserta().\n"
           << "El índice " << pos << " de inserción está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }

   v.resize(v.size() + 1);

   for (size_t i = v.size()-1; i > pos; --i)
      v[i] = v[i-1];
   v[pos] = valor;
}

Aparece en escena la función miembro resize(). Esta función, cuyo prototipo es:

void resize(size_t nuevo_tam);

redimensiona el vector:

  • si el tamaño aumenta, se rellena con elementos cuyo valor suele ser 0 para los tipos de datos habituales

  • si el tamaño disminuye, se borran los elementos sobrantes

Si queremos inicializar a un determinado valor los valores nuevos añadidos al redimensionar, podemos usar la variante:

void resize(size_t nuevo_tam, const tipo& valor);

Por tanto, en nuestra función, se ha usado resize() para aumentar en un elemento el tamaño del vector, para lograr generar el hueco para la inserción del nuevo valor.

Posteriormente, se desplazan una posición los elementos desde el índice del vector pos. Finalmente, se inserta el nuevo valor.

El código de prueba en main() es similar a las ya utilizadas, con la particularidad de que, en cada iteración, se hace una copia del vector original para poder ser reutilizado.

int main()
{
   vector<double> v{0, 1, 2, 3, 4, 5};

   for (size_t i = 0; i <= v.size(); ++i)
   {
      auto v_copia = v;
      inserta(v, i, 1000);
      cout << "Inserción en posición " << i << endl;
      muestra_vector(v);
      v = v_copia;
      cout << endl;
   }
   // inserta(v, -1, 1000);  // Descomenta esta línea y comenta la siguiente
   inserta(v, v.size() + 1, 1000);
}

Edita, compila y ejecuta el código

La función que inserta un vector tendrá una implementación similar. Su prototipo puede ser:

void inserta(vector<double>& u, size_t pos, const vector<double>& v);

Una posible implementación es la que sigue:

void inserta(vector<double>& v, size_t pos, const vector<double>& w)
{
   if (pos > v.size())
   {
      cout << "Fallo en la funcion inserta().\n"
            << "La posición " << pos << " de inserción está fuera de los límites del vector.\n";
      exit(EXIT_FAILURE);
   }

   auto tam_w = w.size();
   v.resize(v.size() + tam_w);

   for (size_t i = v.size() - 1; i >  pos + tam_w - 1; --i)
      v[i] = v[i-tam_w];

   for (size_t i = 0; i < tam_w; ++i)
      v[i+pos] = w[i];
}

Edita, compila y ejecuta el código

Dejamos al alumno que implemente las variantes de borrado que emulan las realizadas por la función miembro erase(), es decir, alterando el propio vector, con prototipos:

void borra(vector<double>& u, size_t pos);
void borra(vector<double>& u, size_t ini, size_t fin);

Sucesiones homogéneas recurrentes de orden \(t\)

Puede verse la descripción del problema en los ejemplos del tema de Control de flujo iterativo. En lugar de limitarnos como en ese tema a las sucesiones de orden 2, con vectores es fácil calcular la sucesión para cualquier orden \(t\). Usaremos además aquí tipos double.

Una sucesión recurrente homogénea de orden \(t\) es aquella cuyos términos \(x_i\) vienen dados por la expresión:

\[x_{n+t}=c_0x_{n}+c_1x_{n+1}+ ... + c_{t-1}x_{n+t-1} \quad n>=0\]

donde los coeficientes \(c_i\) de la sucesión son fijos.

Nótese que para poder generar la sucesión necesitamos los \(t\) primeros términos.

En este ejemplo, almacenaremos en un vector los \(N\) primeros términos y calcularemos su suma.

Diseño del programa

Datos de entrada

Necesitamos:

  • El orden de la sucesión

  • El vector con los \(t\) coeficientes de la sucesión

  • El vector con los \(t\) primeros términos de la sucesión

  • El número de términos que se desea calcular

El orden de la sucesión

Usaremos una función con prototipo:

int introduce_orden();

Dado que un orden inferior a 1 no tiene sentido, la función exigirá al usuario el cumplimiento de esta restricción.

Una posible implementación es:

int introduce_orden()
{
   int orden;
   do
   {
      cout << "Introduzca el orden de la sucesion: ";
      cin >> orden;
      if (orden < 1)
         cout << "El orden debe ser al menos 1\n";
   }while (orden < 1);
   return orden;
}

Los vectores de los \(t\) coeficientes y primeros términos

Para ello usaremos una función con prototipo:

vector<double> introduce_valores(int orden, const string& texto);

Una posible implementación es:

vector<double> introduce_valores(int orden, const string& texto)
{
   vector<double> v;
   v.reserve(orden);

   for (int i = 0; i < orden; ++i)
   {
      cout << texto << i << ": ";
      double valor;
      cin >> valor;
      v.push_back(valor);
   }
   return v;
}

En esta variante, pasamos el orden, es decir, el tamaño del vector y, además, un texto que permite informar al usuario del tipo de valor que se está solicitando.

Por ejemplo, una posible llamada a esta función sería:

auto coef = introduce_valores(orden, "Coeficiente ");

El número de términos a calcular

Esta función exigirá que al menos se introduzca un número de términos idéntico al orden de la sucesión.

Su prototipo puede ser:

int introduce_numero_terminos(int minimo);

Una posible implementación sería:

int introduce_numero_terminos(int minimo)
{
   int num_terminos;
   do
   {
      cout << "\nIntroduzca el número de términos: ";
      cin >> num_terminos;
      if (num_terminos < minimo)
         cout << "\n\nERROR: el número de términos es inferior a " << minimo << endl;
   }while (num_terminos < minimo);
   return num_terminos;
}

Datos de salida

Necesitamos:

  • La función que muestra los valores de un vector, en este caso, los términos calculados de la sucesión

  • Una función que calcula la suma de los elementos de la sucesión

Esta segunda función podría tener el siguiente prototipo:

double calcula_suma(const vector<double>& v);

y una posible implementación es:

double calcula_suma(const vector<double>& v)
{
   double suma = 0.0;
   for (auto x : v)
      suma += x;
   return suma;
}

Procesamiento de los datos

Entre las diversas opciones, el cálculo de los términos de la sucesión se puede hacer con una función con prototipo:

void calcula_sucesion(const vector<double>& c, vector<double>& t, int num_terminos);

La función lanzará un mensaje de error y dará por finalizado el programa si:

  • El número de términos es menor que orden

  • Los vectores no tienen el mismo tamaño

Debemos pensar que las funciones pueden ser usadas por terceros y que, por error, quizás las invoquen indebidamente. El hecho de que nuestro programa garantice que estos errores no se producen, no significa que, si se estima oportuno, la función avise si se produce algún error.

Recalcar para esta función y las anteriores:

  • Usamos const para indicar a terceros que el vector no se modificará y para protegernos frente a nosotros mismos al programar, evitando que modifiquemos el vector por descuido.

  • Usamos & para poder modificar el valor del vector. En caso de que no lo vayamos a modificar (usamos const) pasar por referencia nos evita crear una copia local a la función de todo el vector.

Una posible implementación es:

void calcula_sucesion(const vector<double>& c, vector<double>& t, int num_terminos)
{
   auto orden = c.size();
   if (orden != t.size())
   {
      cout << "\n\nERROR: el vector de coeficientes y términos iniciales ";
      cout << "tienen tamaños diferentes.\n\n";
      exit(EXIT_FAILURE);
   }
   if (num_terminos < orden)
   {
      cout << "\n\nERROR: el número de términos a calcular es inferior ";
      cout << "al orden de la sucesión.\n\n";
      exit(EXIT_FAILURE);
   }

   for(int i = orden; i < num_terminos; ++i)
   {
      double nuevo_termino = 0.;
      for (int j = 0; j < orden; ++j)
         nuevo_termino += c[j]*t[i+j-orden];
      t.push_back(nuevo_termino);
   }
}

Edita, compila y ejecuta el código

Para probar la función, además de con la célebre sucesión de Fibonacci, podemos utilizar el siguiente resultado:

La sucesión formada por los cuadrados naturales \({1, 4, 9, 16, ...}\) corresponde a la sucesión recurrente de orden 3:

\[x_{n+3}=x_{n}-3x_{n+1}+ 3x_{n+2} \quad n>=0\]

con \(x_0 = 1\), \(x_1 = 4\) y \(x_2 = 9\).