C++ , duda con vectores

Iniciado por yadiira, 26 Octubre 2019, 22:59 PM

0 Miembros y 1 Visitante están viendo este tema.

yadiira

Hola amigos soy nueva programando en C++ , tengo una duda o mas bien quiero saber como podria realizar la siguiente tarea. El ususario me dara una serie de datos que yo ya guarde en un vector y para fines del programa ocupo ordenarlo de menor a mayor eso ya lo hice ,pero al hacer eso obviamente cambio las pociciones del vector para ordenarlo , lo que NECESITO es etiquetar a cada elemento desde el principio para poder identificarlos posteriormente para fines del programa.

osea aunque se cambien de poscicion saber cual  es cual , como ponerles nombre

gracias espero me puedan ayudar :)

K-YreX

Si estás empezando creo que te puede resultar un poco lioso pero te dejo un par de opciones:
Usar un array auxiliar.
Normalmente esto se hace creando un array auxiliar de punteros. Haciendo que cada puntero i del array auxiliar apunte al elemento i del array original y después ordenas uno de los dos arrays. De esta manera podrás usar el otro para saber cuál era cada elemento.

arrayOriginal  := {3,6,2,9,5}
arrayPunteros := {p0,p1,p2,p3,p4} // pi significa que apunta al elemento i

Entonces ordenas uno de ellos (el de punteros por ejemplo) para dejar el original intacto y quedaría algo así:

arrayOriginal := {3,6,2,9,5}
arrayPunteros := {p2,p0,p4,p1,p3}

Cuando quieras ver qué elemento era, recorres el arrayOriginal. Cuando quieras trabajar con los elementos ordenados, recorres el de punteros.


Para esto tienes que saber un poco sobre trabajar con punteros. Saber usar el operador para desreferenciarlos (*) y esas cosas.
Otra opción más sencilla es usar dos arrays de enteros. Uno que sea el original y el otro que guarde en la posición i, la nueva posición del elemento i original. Con un ejemplo se ve mejor:

arrayOriginal := {3,6,2,9,5}
arrayOrdenOriginal := {0,1,2,3,4}

arrayOrdenado := {2,3,5,6,9}
arrayOrden := {1,4,0,2,3}

Utilizas el array ordenado y cuando quieras saber cuál era el elemento que habías guardado el primero (posición 0: valor 3), lo recuperas porque su nueva posición la indica el arrayOrden (posición 0: valor 1 -> nuevaPosición: arrayOrdenado[1] = 3).
Lo malo de este método es que es más susceptible a errores humanos y que tienes que intercambiar las posiciones en ambos arrays mientras que en el de punteros sólo en uno. Lo bueno es que en este no tienes que trabajar con punteros.

Si no te sirven estas opciones o no entiendes algo. Deja tu código entre etiquetas de Código GeSHi para que podamos ayudarte mejor. :-X
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

Serapis

En un array no hay necesidad de identificar nada... el identificador es precisamente 'el array', su nombre. ...que, como colección homogénea mantiene índices para cada elemento... Otra cosa es que con posterioridad puedas hacer búsquedas sobre el array, a lo cual se recurre a acceder individualmente a través del índice para cada elemento del array.

Posiblemente tengas conceptos equivocados sobre lo que es y puede hacese con un array...

ThunderCls

Cita de: yadiira en 26 Octubre 2019, 22:59 PM
osea aunque se cambien de poscicion saber cual  es cual , como ponerles nombre

Usa un unordered_map

https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/

Saludos
-[ "...I can only show you the door. You're the one that has to walk through it." – Morpheus (The Matrix) ]-
http://reversec0de.wordpress.com
https://github.com/ThunderCls/

yadiira

Muchas gracias a todos , la verdad estoy intento programa un algoritmo no se como atacarlo exactamente. El problema que  resuelve dicho algoritmo es un problema de localizacion, es el siguiente:

--Tengo un conjunto J de puntos donde se recolecta basura para reciclar.
--Tengo un conjunto centros I de puntos donde se puede mandar esa basura y un costo asociado(Cji)
-- Cada i en I tiene una capacidad de basura que puede recibir.
--Para cada punto fijo  *j en J, solo puede ir a un i en I, pero un centro I puede recibier de diferentes puntos de recolección de basura.
--....... mas o menos para poner en contexto
El objetivo es no es minimizar costos ,si no que MAXIMIZAR la cantidad de basura recolectada.
--------------------------------------------------------------------------------------------
Mi algoritmo es:
1.Tomar el punto donde se genera la mayor cantidad de basura.
2.De los centros a donde se puede enviar localizar el que tenga mayor capacidad de recolección.
3.Dividir el presupuesto/costo de mandar de j a i , y me dará las toneladas máximas que pueda mandar hacia algún centro de recolección.
4.Si lo máximo que puedo mandar  es mayor a las toneladas que hay en el punto j* en J , pues mandar todo , de otra forma mandar para lo que me alcanza
5. Si aun queda espacio en el centro *j en J , de los puntos de recoleccion hacia lo que esta conectado que me mande el que tenga menos caantida de basura.


Bueno espero no atormentarlos con tanto choro no espero que me ayuden con el porblema , solo como puedo plantearlo mas facilmente en C++, jaja por que no tengo mucha practica hasta ahora llevo esto, pero siento que ocupo definir mas cosas


#include <iostream>
#include<vector>
#include<conio.h>
#include<stdlib.h>
using namespace std;
vector<int> J;
vector<int> I;
int main (){
   int n,m;
   cout<<"Numero de puntos de residuos: ";
   cin>>n;
   J.resize(n);
   for(int i=0;i<n;i++){
      cout<<"Toneladas del punto d"<<i+1<<": ";
      cin>>J;
   }
   
   cout<<"Numero de posibles centros a instalar: ";
   cin>>m;
   I.resize(m);
   for(int i=0;i<m;i++){
      cout<<"Capacidad en toneladas del punto b"<<i+1<<": ";
      cin>>I;
   }
   //llenar una matriz con ceros y unos
   int M_relacion [n][m];
   for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
      
   }
   
   
   
   return 0;
}


gracias igual si no le entienden al problema, no pasa nada yo apenas lo ando cachando :)






Serapis

La descripción del planteamiento está bien... aunque falta algún detalle.

- Cuántos colectores I hay y cuántos focos de emisión J hay.
- La suma total de los focos de emisión J, se sabe si caben en la suma total de los colectores I, o quedará algún emisor sin poder enviar su carga?. Lo ideal es que aún quedara algún colector sin llenarse del todo y los emisores haber podido enviar todo.

...y para 'descomplicar' el asunto, yo en vez de llamarlos I y J, los llamaría colector y emisor, para evitar equívocos en algún momento...

yadiira

hola gracias por responder, la cantidad de emisores segun el plantemiento no se van a acabar osea hay muchos puntos de recoleccion, lo que te va a detener es el presupuesto. Y pues como es un problema de localizacion hay que decidir que emisores vas a instalar. Igual solo tengo problema en como programar aunque sea la primer parte.

Serapis

#7
Este tipo de problemática está resuelto satisfactoriamente desde hace 60 años o más, si bien adaptarlo a cada situación es lo que puede tener su miga.

La solución está en los árboles de Huffman, pero además no en uno simple si no en uno adaptativo.
Como supongo, sabrás, los árboles de Huffman se utilizan para la compresión de datos con el algoritmo que lleva su nombre... (inical y principalmente), donde el byte (valor más repetido) se le otorga pesos en función de su frecuencia.
...cuando es adapatativo señala que la frecuencia se actualiza con cada aparición (lectura de cada byte) lo que fuerza a actualizar el árbol: Si un nodo (le siendo sumado) supera en frecuencia al previo, desde ese instante, ese valor (el byte aparecido), se codifica con el valor que tiene asignado la posición del nodo...

Nota, que no es necesario reproducir en todo el algoritmo solo la parte que construye el árbol y la parte que lo hace adaptativo.
Un árbol de Huffman, típicamente se construye al inicio y luego se usa... pero en tu caso conviene que sea adaptativo, pués una vez que envías un emisor a un colector, el total de colector aumenta, luego tiene menos capacidad libre y por tanto bajaría en el nodo si ahora tiene menos disponibilidad libre que otro colector.
Algunas diferencias hay... en tu caso cuando un colector se llena, se supone (intuyo porque eso lo indicará la especificación completa del problema), deja de ser utilizado, lo que de algún modo implicaría retirar dicho nodo del árbol (y si existe un factor tiempo (u otro) que luego lo rehabilita, pués hale tocará añadirlo en su posición cuando se habilite superando a todos los nodos por 'espacio libre en toneladas'... Lo mismo si se añade un colector de repente al árbol... es decir necesitarás alguna función añadir colector(peso)... que examine que posición le corresponde en base a su 'espacio libre' en toneladas... es mejor abstraerse de toneladas, basura y tal y atenerse meramente al asunto matemático...

Un árbol de Huffman, netamente es un árbol binario que funciona conducido por el peso de los nodos, es decir el valor se establece al inicio... (en tu caso al inicio supone establecer el total que puede almacenar cada colector o si ya está usado, lo que le queda libre) y como he dicho precisa ser adaptativo... en Huffman adaptativo es costoso en tiempo ya que está continuamente actualizándose con cada byte... otro modo es 'semiadaptativo', es decir se propone (por ejemplo 4kb., 64kb. de bytes), se van sumando mientras y cuando se completa esa cantidad se reordena el árbol, conforma los nuevos valores... La compresión lograda con un algoritmo adaptativo es superior a los otros semiadaptativo o no adaptativo, pero el coste en tiempo es mayor.
Debes establecer en función de la cantidad de colectores y frecuencia en emisiones si en tu caso conviene que sea adaptativo o semiadaptativo, y si es semiadaptativo, debe encontrarse el punto aceptable para actualizar el árbol... (por ejemplo, cada 10 emisiones).

Todavía operar con árboles resulta lento, más siendo adaptativo... la opción más efectiva es operar sobre un array. Un array puede representar a un árbol binario, básicamente cada nodo de un árbol binario viene representado en un índice específico del array... un pequeño cálculo permite pasar de un nodo a otro. Así en vez de usar referencias a 'siguiente' anterior', 'derecha' o 'izquierda', tu tendrás sendas funciones que devuelvan el índice correspondiente dado aqule en el que estás y el acceso al que tratas de llegar...

Nota finalmente como un árbol, retiene la info que pedías al comienzo, pero sin necesitar un indicador otro que la que representa su posición y que obedece a su valor, al valor que alamcena que en tu caso debe ser el espacio libre o más complejo en función del espacio libre y el costo asociado...
...y finalmente ese array utilizado como un árbol binario, ofrece la velocidad que pueda ser preciso, aunque en el caso que te trae, considero que tiene menos sobrecarga que la simpre compresión de un fichero de 1Mb. (por ejemplo). Así que si finalmente construído el árol te funciona y satisface la velocidad y sobrecarga, podrías no necesitar el array... ya valorarás el caso.

Así que una vez te empapes sobre construir el árgol de Huffman y lograr que sea adaptativo, y luego (que funciones bien) remplazarlo por el array, finalmente te queda solventar la cuestión del costo (pesos de cada nodo). Ahí ya es cosa que tendrás que lidiar con la especificación que te hayan dado. Si el ejemplo es real (no un ejercicio), probablemente el costo será dado en kilometraje o en tiempo, etc... pero como digo, antes de meterte en el fregado de dar los pesos al árbol, primero constrúyelo con valores ficitios, no calculados, para verificar que el algortimo funciona bien que se actualiza convenientemente, y solo al final toca sustituir esa parte por la que en efecto calcula el peso real de cada nodo... en el árbol de Huffman esa parte es la más sencilla, pués se lleva la cuenta de la presencia de cada byte. Para grandes cantidades de datos, cuando el valor en la raíz supera cierto umbral para evitar desbordamiento del tipo de datos, suele recurrirse a dividirse todos (el valor de cada nodo) por la mitad...  es decir ciertos detalles no son tu caso, otros son ligeramente variados y otros se aplican al 100%...

Bueno, ya tienes pan para ir comiendo... Si tienes alguna duda, pregunta... pero ven ya con algo más sólido...