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

 

 


Tema destacado: Sigue las noticias más importantes de seguridad informática en el ttwitter! de elhacker.NET


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Programa que genera un conjunto usando array C++ no funciona correctamente
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Programa que genera un conjunto usando array C++ no funciona correctamente  (Leído 1,476 veces)
seryioo

Desconectado Desconectado

Mensajes: 83



Ver Perfil
Programa que genera un conjunto usando array C++ no funciona correctamente
« en: 10 Agosto 2015, 13:31 pm »

Buenas a todos otra vez, sigo atascado con este problema.

12) Diseñar un programa que genere y muestre en la pantalla ordenados los 100 primeros
números de un conjunto M definido de la siguiente forma:
i. 1 pertenece a M.
ii. Si x pertenece a M, entonces 2*x+1 y 3*x+1 también pertenecen a M.
iii. Ningún otro número pertenece a M.
El programa deberá producir una salida por pantalla de la forma:
M = {1, 3, 4, 7, 9, 10, … }*/


La cosa es que empieza a generarme el conjunto bien (al menos los primeros números, los demás no he tenido manera de comprobarlos), pero derrepente salen valores desorbitados, como si en alguna parte del proceso hubiera datos basura que estuvieran estropeando el proceso, y no lo veo.

Os dejo el código:

Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. typedef long int Tarray [100];
  5.  
  6. void generarConjunto(Tarray ar);
  7.  
  8. bool esta(Tarray ar, int long n, unsigned pos);
  9.  
  10. void ordenar(Tarray ar);
  11.  
  12. void mostrar(Tarray ar);
  13.  
  14. //---------------------------
  15.  
  16. int main(){
  17.    Tarray ar;
  18.    generarConjunto(ar);
  19.    cout<<"-----------------------------------"<<endl;
  20.    ordenar(ar);
  21.    mostrar(ar);
  22.  
  23.  
  24.    return 0;
  25. }
  26.  
  27. //---------------------------
  28.  
  29. void generarConjunto(Tarray ar){ //EL FALLO CREO QUE LO DA ESTA FUNCION,  QUE ES LA QUE GENERA LOS VALORES DEL CONJUNTO
  30.    unsigned valor=0;
  31.    ar[valor]=1;
  32.    long int x=ar[valor];
  33.    for(unsigned pos=1; pos<100; pos++){
  34.        if(!esta(ar, 2*x+1, pos)){
  35.            ar[pos]=2*x+1;
  36.            cout<<ar[pos]<<endl;
  37.        } //end if
  38.        ++pos;
  39.        if(!esta(ar, 3*x+1, pos)){
  40.            ar[pos]=3*x+1;
  41.            cout<<ar[pos]<<endl;
  42.        }//end if
  43.        ++valor;
  44.        x=ar[valor];
  45.    }//end for
  46. }
  47.  
  48. bool esta(Tarray ar, int long n, unsigned pos){
  49.    unsigned i=0;
  50.    bool e =false;
  51.    while(!e and i<pos){
  52.        if(ar[i]==n) e=true;
  53.        ++i;
  54.    }//end while
  55.    return e;
  56. }
  57.  
  58. void ordenar(Tarray ar){
  59.    int long aux=0;
  60.    unsigned comp=0;
  61.    do{
  62.        for(unsigned pos=0; pos<99; pos++){
  63.            if(ar[pos]>ar[pos+1]){
  64.                aux=ar[pos];
  65.                ar[pos]=ar[pos+1];
  66.                ar[pos+1]=aux;
  67.            }//end if
  68.        }//end for
  69.    ++comp;
  70.    }while(comp<=1000); //podria sustituir esto por una funcion auxiliar que dijera si el array esta ordenado o no.
  71. }
  72.  
  73. void mostrar(Tarray ar){
  74.    for(unsigned pos=0; pos<100; ++pos){
  75.        cout<<"->"<<ar[pos]<<endl;
  76.    }//end for
  77. }
  78.  
  79.  


« Última modificación: 10 Agosto 2015, 13:33 pm por seryioo » En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Programa que genera un conjunto usando array C++ no funciona correctamente
« Respuesta #1 en: 11 Agosto 2015, 01:35 am »

¡Buenas!

En la función que estás utilizando para generar los valores del conjunto estás haciendo cosas muy raras, incrementas índices sin tener en cuenta si has introducido o no un elemento en el vector y no tienes en cuenta que para todos los elementos x que ya has calculado 2x+1 y 3x+1 tienen que estar.

Tienes que darte cuenta de que no hay una fórmula que te de los elementos del conjunto de forma directa (o si la hay no resulta evidente) y de que el conjunto está definido de forma recursiva:
- 1 es un elemento del conjunto
- si x e un elemento 2x+1 y 3x+1 son elementos del conjunto.

Con estos datos lo más fácil de hacer es determinar cuándo un número pertenece o no al conjunto:
- si n == 1 -> n está en el conjunto.
- si n - 1 es par, n estára en el conjunto si y solo si (n - 1)/2 lo está: n = 2x+1, así que habrá que ver si x está en el conjunto.
- si n - 1 es multiplo de 3, n estará en el conjunto si y solo si (n - 1) 3 lo está: n = 3x+1, así que habrá que ver si x está en el conjunto.

Ahora que tienes definida la función recursiva que decide si un número pertenece o no al conjunto, lo único que tienes que hacer es recorrer los números a partir del 1 y comprobar si pertenecen o no al conjunto, así hasta que tengas 100 números que pertenezcan.

Si quieres hacerlo como lo estabas haciendo tendrás que dar muchas más vueltas:
- Tienes que insertar el 1.
- Tienes que calcular 2 * 1 + 1 y 3 * 1 + 1,
- Para cada uno de los valores x anteriores tendrás que calcular 2 * x + 1 y 3 * x + 1 y si no están repetidos insertarlos en el vector.
- Repetir el paso anterior hasta que tengas 100 elementos.

Resumiendo lo anterior, en cada iteración tendrás que saber:
- Donde ha empezado la iteración anterior: ini_anterior
- Cuantos elementos has introducido en la iteración anterior: n_insertados

Y lo que tendrás que hacer será:
- Desde i = ini_anterior hasta ini_anterior + n_insertados, insertar 2v(i)+1, 3v(i)+1 (si no están repetidos)
- Llevar la cuenta de los que has insertado.
- Actualizar ini_anterior al inicio del nuevo bloque de inserciones y actualizar n_insertados con la nueva cantidad de elementos insertados
- Actualizar el número total de elementos insertados para saber si has llegado a los 100 o no.

Como ves, la forma más cómoda de tratar con el problema es utilizar la función recursiva que hemos definido al principio e ir comprobando uno a uno si un número pertenece o no al conjunto.

¡Saludos!


En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
seryioo

Desconectado Desconectado

Mensajes: 83



Ver Perfil
Re: Programa que genera un conjunto usando array C++ no funciona correctamente
« Respuesta #2 en: 12 Agosto 2015, 13:31 pm »

Muchas gracias. Explicación de 10!
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines