elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Entrar al Canal Oficial Telegram de elhacker.net


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [Duda] Inserción en una tabla ordenada
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [Duda] Inserción en una tabla ordenada  (Leído 3,768 veces)
Denok

Desconectado Desconectado

Mensajes: 17


Ver Perfil
[Duda] Inserción en una tabla ordenada
« en: 3 Enero 2012, 14:11 pm »

Hola, mirar estoy intentando hacer el ejercicio siguiente:

Hacer un procedimiento
    void insereix(vector <double>& v);

que, suponiendo que todas las posiciones de v, excepto quizas la ultima,estan ordenadas de pequeño a grande, deje v totalmente ordenado de pequeño a grande.
Un ejemplo seria, si v fuera (2,4,7,7,8,9,5), deberia quedar(2,4,5,7,7,8,9).

El codigo que yo he hecho es el siguiente:
Código
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. void insereix(vector <double>& v){
  7.    int n = v.size();
  8.    int k = v[n-1];
  9.    vector <double> vi(n);
  10.    bool inserit = false;
  11.    int j;
  12.  
  13.    for(int i = 0; i < n and not(inserit); ++i){
  14.        if(v[i] <= k){
  15.            vi[i] = v[i];
  16.        } else {
  17.            vi[i] = k;
  18.            inserit = true;
  19.            j = i + 1;
  20.        }
  21.    }
  22.  
  23.    for(int i = j; i < n;++i){
  24.        vi[i] = v[i];
  25.    }
  26. }
  27.  
  28. int main(){
  29.    int n;
  30.    cin >> n;
  31.    vector <double> v1(n);
  32.    for(int i = 0; i < n; ++i)
  33.        cin >> v1[i];
  34.  
  35.    insereix(v1);
  36.  
  37.    for(int i = 0; i < n; ++i)
  38.        cout << v1[i];
  39.  
  40. }
  41.  

Pero cuando imprimo me sale el vector exactamente igual que lo he introducido.
Para explicar un poco el código de la función, lo que hago es crear un nuevo vector donde guardare el antiguo vector ordenado.
Declaro una variable(k) donde guardo el valor de la ultima posición, y con un for voy comprobando si cada posición es menor o igual a la ultima. Si no es así, introduzco en esa posición el valor de k, y con una variable booleana puesta en false, hago que no se ejecute el código.

Luego solo hago otro for para rellenar el vector desde la siguiente posición de k.

No entiendo porque no funciona.

Muchas gracias y adiós!.


En línea

El_Java

Desconectado Desconectado

Mensajes: 144



Ver Perfil WWW
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #1 en: 3 Enero 2012, 15:46 pm »

Hombre, puestos a usar métodos predefinidos puedes usar la función sort (sí, es standar):
Código
  1. #include <algorithm>
  2. #include <vector>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. int main(){
  7.    vector<double> v(7);
  8.    v[0] = 2; v[1] = 4; v[2] = 7; v[3] = 7; v[4] = 8; v[5] = 9; v[6] = 5;
  9.    // v == {2,4,7,7,8,9,5}
  10.    for(int y=0; y<(int)v.size(); y++) cout << v[y];
  11.    cout << endl;
  12.    sort(v.begin(), v.end());
  13.    // v == {2,4,5,7,7,8,9}
  14.    for(int x=0; x<(int)v.size(); x++) cout << v[x];
  15.    cout << endl;
  16.  
  17.    return 0;
  18. }

Si no quieres usar la funcion sort, hazlo con las funciones que te da la clase vector, esta es tu función pero echa por mi:
Código
  1. void insereix(vector <double>& v){
  2.    int x;
  3.    for(x=0; x<(int)v.size(); x++) if(v[x] >= v[v.size()-1]) break; //para cuando encuentra un valor mas grande que v[v.size()-1]
  4.    v.insert(v.begin()+x, v[v.size()-1]); //lo inserta en x
  5.    v.erase(v.end()-1); //borra el ultimo valor
  6. }

PD: En tu función v nunca cambia porque usas un vector auxiliar y la funcion es de tipo void, añade swap(v, vi); al final de tu función y #include <algorithm> al principio del archivo y verás que de todas formas no haces bien el ordenamiento.


En línea

Denok

Desconectado Desconectado

Mensajes: 17


Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #2 en: 3 Enero 2012, 22:47 pm »

Gracias por responder!!.

Lo que pasa es que no puedo usar ninguna de las dos opciones que me explicas(no me dejan). Cual seria la manera para que me quedara bien ordenado, no entiendo porque no se ordena bien.
Que tendría que modificar de mi código para que quedase bien?
Tampoco entiendo tu pd, que tiene que ver que sea una función void ? Si me lo explicaras me harías un favor.

Muchas gracias!!

Adiós.
« Última modificación: 3 Enero 2012, 22:55 pm por Denok » En línea

El_Java

Desconectado Desconectado

Mensajes: 144



Ver Perfil WWW
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #3 en: 3 Enero 2012, 23:33 pm »

Claro que te lo explico, no hay problema:
en tu función lo que haces es ir añadiendo elementos del vector v al vector NUEVO vi, pero sin embargo, al terminar la función no retornas nada, por lo que el vector v va a seguir igual porque no lo has modificado, y el modificado vi no lo usas para nada, por lo que al terminar la función 'desaparece'.

tu función "arreglada":
Código
  1. #include <algorithm> //mete esto en los includes
  2. void insereix(vector <double>& v){
  3.    int n = v.size();
  4.    int k = v[n-1];
  5.    vector <double> vi(n);
  6.    bool inserit = false;
  7.    int j;
  8.  
  9.    for(int i = 0; i < n && !inserit; ++i){ //he cambiado and not por && !
  10.        if(v[i] <= k){
  11.            vi[i] = v[i];
  12.        } else {
  13.            vi[i] = k;
  14.            inserit = true;
  15.            j = i + 1;
  16.        }
  17.    }
  18.  
  19.    for(int i = j; i < n;++i){
  20.        vi[i] = v[i-1]; //tambien te he metido el -1 en el v
  21.    }
  22.  
  23.    swap(vi, v); //intercambia vi y v
  24. }

saludos.
En línea

Denok

Desconectado Desconectado

Mensajes: 17


Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #4 en: 4 Enero 2012, 00:57 am »

La web que evalúa el programa me dice que no funciona, pero el código funciona muy bien en mi ordenador.

Muchas gracias !

Pero una cosa, las funciones de tipo void, son procedimientos por lo que no pueden retornar nada no? Siempre tengo que usar swap si uso un vector auxiliar ?

Gracias por todo.
Adios!
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #5 en: 4 Enero 2012, 01:11 am »

Por lo que veo estás haciendo un problema del Jutge en la versión catalana por el nombre de la función, así que asumiré que estás haciendo o un Grado en Matemáticas en la FME o un Grado en Informática en la FIB, que son las dos carreras que lo utilizan. Esto lo digo porque al ser la primera asignatura de programación, suelen ser estrictos con el estilo al programar, así que voy a intentar hacer todo según el estilo que marcan en ambas asignaturas.

Vayamos por partes. El último código que se ha puesto cuando lo envíes si lo envías verás que no funciona, puesto que hay un fallo que tenías que sigue ahí y es que haces casting a int con la variable k y el vector es de double, de manera que las comparaciones van a hacerse raras y el número si tenía decimales quedará modificado. Aparte de eso, en tu código utilizas un vector auxiliar que no se necesita para nada, de forma que gastas memoria tontamente haciendo el código además bastante más largo, cosa que en un examen te valorarían (o almenos deberían, con el grado no se cómo puntúan sobretodo en la FIB) bastante mal en la corrección manual, por mucho que el Jutge de un verde.

La idea de la solución es simple y es comenzar por el final e ir intercambiando los elementos mientras sea necesario.

Un pequeño código que he hecho y que debería funcionar es el siguiente:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. void insereix(vector<double>& v){
  6.    int n = v.size();
  7.    for (int i = n - 1; i > 0 and v[i] < v[i - 1]; --i) swap(v[i], v[i - 1]);
  8. }

Como ves, sin usar vectores auxiliares queda todo mucho más simple, natural y corto. La función swap no recuerdo si la podéis usar, si no podéis es muy sencilla de implementar (de hecho es uno de los problemas de la lista si no recuerdo mal).
En línea

Denok

Desconectado Desconectado

Mensajes: 17


Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #6 en: 4 Enero 2012, 02:10 am »

La clavas en todo, estoy haciendo primero en la FIB, programando los algoritmos fundamentales.

Tu código funciona muy bien, y tu manera es mucho mas sencilla, lastima que no se me ocurriera xD

Creo que no nos dejan usar la función swap, la tenemos que programar pero eso es sencillo.

Muchas gracias por todo.
Algún consejo que me puedas dar a la hora de programar, para que puntúen bien en los exámenes? Es que se acerca el final y así voy mejor preparado.

Muchísimas gracias por todo.
Adiós.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #7 en: 4 Enero 2012, 03:03 am »

No hay mucho misterio, si quieres programar bien y saber hacer ejercicios de programación, se aprende a base de programar. No es simple cuestión de conocer el lenguaje, sino de saber resolver problemas de tipo a veces más algorítmico que de implementación. Para todo esto, la única opción es practicar y para eso está el Jutge. A programar se aprende programando y si alguna cosa no te sale, pregunta.

Aparte de eso, intenta adaptarte al estilo que marcan en la asignatura para que no te bajen puntos por estilo (en la FIB con el grado no sé si lo siguen haciendo, pero me imagino que sí).
En línea

Denok

Desconectado Desconectado

Mensajes: 17


Ver Perfil
Re: [Duda] Inserción en una tabla ordenada
« Respuesta #8 en: 5 Enero 2012, 00:46 am »

Si, siguen haciendo lo de las notas de estilo.

Muchas gracias !
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Duda con Tabla.
PHP
NaSaRiD15 2 1,598 Último mensaje 1 Septiembre 2008, 05:55 am
por NaSaRiD15
[Duda] Tabla de Karnaugh « 1 2 3 »
Electrónica
WaRc3L 20 15,922 Último mensaje 25 Marzo 2011, 19:39 pm
por *****
Duda sobre insersion a tabla html desde tabla sql
Bases de Datos
mokoMonster 2 3,928 Último mensaje 20 Febrero 2010, 01:20 am
por Shell Root
Lista Doble Dinamica con insercion ordenada?
Programación C/C++
gibranini 6 4,543 Último mensaje 21 Mayo 2014, 17:29 pm
por gibranini
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines