Programa que genera un conjunto usando array C++ no funciona correctamente

[seryioo]

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 (cpp) [Seleccionar] Expandir


#include <iostream>
using namespace std;

typedef long int Tarray [100];

void generarConjunto(Tarray ar);

bool esta(Tarray ar, int long n, unsigned pos);

void ordenar(Tarray ar);

void mostrar(Tarray ar);

//---------------------------

int main(){
   Tarray ar;
   generarConjunto(ar);
   cout<<"-----------------------------------"<<endl;
   ordenar(ar);
   mostrar(ar);


   return 0;
}

//---------------------------

void generarConjunto(Tarray ar){ //EL FALLO CREO QUE LO DA ESTA FUNCION,  QUE ES LA QUE GENERA LOS VALORES DEL CONJUNTO
   unsigned valor=0;
   ar[valor]=1;
   long int x=ar[valor];
   for(unsigned pos=1; pos<100; pos++){
       if(!esta(ar, 2*x+1, pos)){
           ar[pos]=2*x+1;
           cout<<ar[pos]<<endl;
       } //end if
       ++pos;
       if(!esta(ar, 3*x+1, pos)){
           ar[pos]=3*x+1;
           cout<<ar[pos]<<endl;
       }//end if
       ++valor;
       x=ar[valor];
   }//end for
}

bool esta(Tarray ar, int long n, unsigned pos){
   unsigned i=0;
   bool e =false;
   while(!e and i<pos){
       if(ar[i]==n) e=true;
       ++i;
   }//end while
   return e;
}

void ordenar(Tarray ar){
   int long aux=0;
   unsigned comp=0;
   do{
       for(unsigned pos=0; pos<99; pos++){
           if(ar[pos]>ar[pos+1]){
               aux=ar[pos];
               ar[pos]=ar[pos+1];
               ar[pos+1]=aux;
           }//end if
       }//end for
   ++comp;
   }while(comp<=1000); //podria sustituir esto por una funcion auxiliar que dijera si el array esta ordenado o no.
}

void mostrar(Tarray ar){
   for(unsigned pos=0; pos<100; ++pos){
       cout<<"->"<<ar[pos]<<endl;
   }//end for
}



[do-while]

¡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!

[seryioo]

Muchas gracias. Explicación de 10!