| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
psk
Registrado: 18 Nov 2005
Mensajes: 79
|  Publicado: 02/12/2005 12:17 pm | | | Título: Generar valores aleatorios sin repetir ninguno |
| A ver si alguno de vosotros puede aportarme un código para hacer eso que digo. Yo tengo el que adjunto, pero quiero ver si alguno saca uno más optimizado, que en estos momentos no se me ocurre ninguno.
| Código: | /* Crear un array de tamaño 30 con números generados aleatoriamente y con valores
comprendidos entre 100 y 200. No puede haber ninguno repetido */
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void main(void){
int array[30], i, colision = 1, e = 0;
randomize();
for(i=0;i<30;i++){
while(colision==1){
array[i] = random(101) + 100;
colision = 0;
while(colision==0 && e<i){
if(array[i]==array[e]){
colision++;
e++;
}
e++;
}
e = 0;
}
colision = 1;
printf("Elmento %d: %d\n", (i+1), array[i]);
}
getch();
} |
|
| | Volver arriba | |  | psk
Registrado: 18 Nov 2005
Mensajes: 79
| | Publicado: 02/12/2005 12:32 pm | | | Título: |
| Aquí pongo uno mejor. He eliminado un bucle y una variable. Ademas he definido una constante para generar la cantidad que desee cambiando solo su valor. Si meteis 10 como valor de la constanten podréis comprobar más rápidamente que no se repite ningun valor (al menos no se me ha repetido...). Con esto me doy por satisfecho por hoy, pero sigo esperando a ver si alguien me da una solución mejor.
| Código: | #include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define TAM 30
#define COMIENZO 100
#define FIN 200
void main(void){
int array[TAM], i, e = 0;
randomize();
for(i=0;i<TAM;i++){
array[i] = random(((FIN - COMIENZO) + 1)) + (COMIENZO);
while(e<i){
if(array[i] == array[e]){
array[i] = random(((FIN - COMIENZO) + 1)) + (COMIENZO);
e = 0;
}
else{
e++;
}
}
e = 0;
printf("Elemento %d: %d\n", (i+1), array[i]);
}
getch();
} |
EDITO: Por los cambios (para hacer la prueba con 10) ahora no se cumple el rango de numeros que tiene que abarcar la generacion aleatoria, pero de todos modos eso es secundario, sólo hay que ajustar la funcion random.
EDITO2: Bueno, no he podido apagar el ordenador sin antes arreglar eso. Ahora todo se controla modificando las constantes que he definido.  |
| | Volver arriba | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 02/12/2005 2:37 pm | | | Título: |
| Este programa que te paso a continuación es del eterno problema de espacio de memoria vs rapidez. Si lo revisas vas a ver que la función random sólo se llama el número de veces igual al de los números distintos que quieres sacar, pero por otro lado tuve que definir unos arreglos extras.
| Código: |
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#define SUBTOTAL 30
#define TOTAL 101
#define ORIGEN 100
main ()
{
int i, j, array[SUBTOTAL], numeros[TOTAL], indice[TOTAL], numaleat;
randomize ();
while (1) {
for (i = 0; i < TOTAL; i++) {
numeros[i] = ORIGEN + i;
indice[i] = i;
}
printf ("\n");
for (i = 0; i < SUBTOTAL; i++) {
array[i] = numeros[indice[numaleat = random (TOTAL - i)]];
if (indice[numaleat] != TOTAL - i - 1)
indice[numaleat] = indice[TOTAL - i - 1];
printf ("%d ", array[i]);
}
/* comprobaci¢n */
for (i = 0; i < SUBTOTAL; i++)
for (j = 0; j < i; j++)
if (array[j] == array[i]) {
printf ("\nEl n£mero %d se repite!!!\n", array[i]);
goto ETIQUETA;
}
printf ("\nNing£n n£mero se repite");
ETIQUETA:
printf ("\t\t\tpresione 'q' para salir...");
if (getch() == 'q')
break;
}
exit (EXIT_SUCCESS);
}
|
|
| | Volver arriba | | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 4672
Ubicación: Mexico
| | Publicado: 02/12/2005 3:14 pm | | | Título: |
| Otra posible solucion consiste en almacenar todos los numeros a utilizar en un array y lo que se generaria de forma aleatoria seria el orden, un ejemplo sencillo en C estandar es:
| Código: | #include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define NUM_ELEM 49 /* Numero de elementos a procesar */
int main(void)
{
int numero[NUM_ELEM];
int i, r;
/* Inicializar la semilla para numeros aleatorios */
srand((unsigned) time(NULL));
/* Asignar los valores 1 - 49 */
for (i = 0; i < NUM_ELEM; i++)
numero[i] = i + 1;
/* Presentar los numeros en un orden aleatorio */
for (i = NUM_ELEM; i > 0; i--){
r = rand() % i;
printf("%2d%s", numero[r], ((i - 1) % 7 == 0) ? "\n" : " ");
numero[r] = numero[i - 1];
}
return EXIT_SUCCESS;
} |
Un saludo
_________________
The capacity to learn is a gift;
The ability to learn is a skill;
The willingness to learn is a choice.
--
Rebec of Ginaz |
| | Volver arriba | | | psk
Registrado: 18 Nov 2005
Mensajes: 79
| | Publicado: 02/12/2005 5:42 pm | | | Título: |
| ¿No podría llegar eso a ocupar demasiada memoria? Imagina que quiero generar valores entre 1000 números distintos...
Gracias por contestar |
| | Volver arriba | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 02/12/2005 7:21 pm | | | Título: |
| Pues si, por eso te decía que es un compromiso entre el espacio en memoria y la rapidez. Lo que no acabo de entender es lo que dice rir3760, de que su programa es equivalente, pues el programa escoge
consecutivamente los números y después los "revuelve" pero de ninguna manera escoge números al azar, ¿cómo escogería los 30 números de los 101 que tu quieres? ¿acaso los escogería consecutivamente? ¿saltándoselos de dos en dos? Evidentemente haciéndolo así va a escoger números distintos, pero de ninguna manera serán al azar. El problema está precisamente en escoger al azar esos números y que no se repitan. |
| | Volver arriba | | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 4672
Ubicación: Mexico
| | Publicado: 03/12/2005 8:28 am | | | Título: |
| | pitukilloloco escribió: | | Lo que no acabo de entender es lo que dice rir3760, de que su programa es equivalente, pues el programa escoge consecutivamente los números y después los "revuelve" pero de ninguna manera escoge números al azar, ¿cómo escogería los 30 números de los 101 que tu quieres? |
De la misma forma que lo hace tu programa.
En otras palabras si eres tan amable de revisar tanto tu programa como el mio vas a encontrar algunas similitudes.
Un saludo
_________________
The capacity to learn is a gift;
The ability to learn is a skill;
The willingness to learn is a choice.
--
Rebec of Ginaz |
| | Volver arriba | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 03/12/2005 9:45 am | | | Título: |
| Bueno, vamos a ponernos de acuerdo en lo que hace cada programa. Yo digo que tu no escoges al azar los números ¿estás de acuedo en eso?, ahora, ¿dices que en el programa que yo puse tampoco escoge al azar los números?
Bueno, te voy a explicar porque creo que si se escogen al azar.
Te lo muestro con un ejemplo de 10 números. Supongamos que tengo este arreglo de 10 números:
| Cita: |
[56.05], [1000.0], [1.7], [89.2], [777.7], [26.65], [101.31], [67.9], [833.5], [531.4]
|
y tengo este arreglo de 10 enteros
| Cita: |
[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]
|
y este arreglo de 3 números no inicializados
Entonces voy a escoger 3 números de los 10 al azar, sin que se repitan, y usando sólo tres veces la función azar(n), que me devuelve un número aleatoreo entre 0 y n-1.
En la primera iteración efectúo azar(10). Supongamos que me da 3, entonces me fijo cual es el valor del contenido del arreglo de enteros cuyo índice es este valor sacado al azar, y es este: [3], o sea 3. entonces me fijo cual es el valor del arreglo de números y veo que es [89.2], entonces pongo este número en la primera localidad de números sin inicializar, lo que me quedaría así:
En el arreglo de enteros muevo el valor que tiene el último índice, el cual es [9] a esta localidad que ya usé, por lo que el arreglo de enteros quedaría así
| Cita: |
[0], [1], [2], [9], [4], [5], [6], [7], [8], [9]
|
En la segunda iteración vuelvo a escoger otro número al azar, pero esta vez entre 0 y 8. Vamos a suponer que me vuelva a sacar el número 3 ¿acaso se va a escoger el mismo número nuevamente? Esto ya no es posible, porque el valor del arreglo de enteros cuyo índice es 3 ahora es [9], y el valor del arreglo de números cuyo índice es 9 es [531.4]. Por lo que el arreglo sin inicializar me quedaría así
| Cita: |
[89.2], [531.4], [ ]
|
y vuelvo a mover el valor del último índice que puede alcanzar la función azar en esta iteración, el cual es 8, o sea que muevo [8] a la localidad que me dio la función azar en esta iteración, el cual repitió el número 3, o sea, que el arreglo de enteros me quedaría así
| Cita: |
[0], [1], [2], [8], [4], [5], [6], [7], [8], [9]
|
Bueno, la tercera iteración es exactamente igual, salvo que ahora la función azar me regresa un número entre 0 y 7, o sea, que va a escoger un número entre estos
| Cita: |
[0], [1], [2], [8], [4], [5], [6], [7]
|
¿si ves que es imposible que se vaya a escoger un número repetido dado que el [3] y el [9] ya no están aquí? ¿estás de acuerdo en que estoy escogiendo estos números al azar o no? |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 4672
Ubicación: Mexico
| | Publicado: 03/12/2005 1:11 pm | | | Título: |
| Antes que nada quiero aclarar que lo que mencione en mi mensaje anterior lo dije en en buen plan y sin ninguna mala intencion o doble sentido. ¿OK?
| pitukilloloco escribió: | | Bueno, vamos a ponernos de acuerdo en lo que hace cada programa. |
OK. Ambos programas utilizan en forma muy parecida el mismo algoritmo por lo que podemos deducir que su operacion y desempeño son similares.
| pitukilloloco escribió: | | Yo digo que tu no escoges al azar los números ¿estás de acuedo en eso?, |
No y es por eso que te pedi de forma amable que compararas ambos programas para que te dieras cuenta que el algoritmo es el mismo.
| pitukilloloco escribió: | | ahora, ¿dices que en el programa que yo puse tampoco escoge al azar los números? |
En ningun momento yo dije o sugeri que tu programa no funciona correctamente, lo unico que indique fue, con un poco de humor que por lo visto no captaste, que hay algunas similitudes.
Las diferencias entre los dos programas son:
* Tu programa es un poco mas extenso ya que utiliza un array de indices para preservar el estado del array de opciones.
* Mi programa es mas corto porque se enfoca en el caso particular que expone psk, esto es, en la generacion de numeros de tipo int que solo requieren el uso de un array y por lo mismo no es necesario preservar su contenido, las operaciones incluyendo la operacion 'mover al ultimo para que no se pierda' se realizan directamente en este.
Un saludo
_________________
The capacity to learn is a gift;
The ability to learn is a skill;
The willingness to learn is a choice.
--
Rebec of Ginaz |
| | Volver arriba | | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 03/12/2005 2:32 pm | | | Título: |
| Bueno, quiero aclarar que esta no es una pelea, simplemente estamos defendiendo nuestro punto de vista, lo cual me parece bien, y cada quien expondrá sus argumentos para apoyar sus ideas.
Yo estaré de acuerdo con las razones que me digas siempre que apoyes estas con argumentos válidos, por eso te preguntaba si considerabas que tu programa escogía los números al azar. Dices que tu programa si escoge los números al azar, o sea, que para ti, escoger varios números consecutivamente y después mezclarlos usando la función rand() a final de cuentas es escogerlos al azar ¿no? Yo estaría de acuerdo si se te pidiera escoger todos uno por uno al azar, pero en el caso del planteamiento inicial, vas a escoger un subconjunto de una población. Entonces, si tu me dices, que escoger consecutivamente una parte del total y después revolver estos usando una función aleatorea es escogerlos al azar entonces yo no estoy de acuerdo. Si en este punto no llegamos a ponernos de acuerdo entonces cada quien tiene una definición distinta de lo que es escoger al azar un objeto y no hay discusión posible.
Si no tenemos la misma definición de lo que es "escoger al azar" entonces no tiene caso que te diga en que se diferencía mi programa del tuyo (aparte de que es más grande como dices), y no, no estoy de acuerdo en que es el mismo algoritmo.
Si estás de acuerdo en que escoger una parte de la población consecutivamente (o usando otra función determinista que te regrese un número distinto, como sólo los números pares, los múltiplos de 5, etc.) y después aplicarle al subconjunto cualquier función aleatorea que los mescle, no es escogerlos al azar ¿me podrías decir cómo adaptarías tu algoritmo para escoger aleatoreamente un subconjunto de un total sin que se repitan y usando la función aleatorea exactamente el número de la población del subconjunto? |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 4672
Ubicación: Mexico
| | Publicado: 03/12/2005 5:22 pm | | | Título: |
| Pensaba compilar tu programa pero no puedo hacerlo ya que mis tres compiladores (Lcc-win32, Pelles C y GCC/Cygwin) no soportan random, randomize y la infamous conio de Borland.
Por lo mismo me tome la libertad de modificar tu programa para que compilara como C estandar y fuera lo mas compacto posible pero sin tocar el algoritmo:
| Código: | #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SUBTOTAL 30
#define TOTAL 101
#define ORIGEN 100
int main(void)
{
int i, array[SUBTOTAL], numeros[TOTAL], indice[TOTAL], numaleat;
srand((unsigned) time(NULL));
for (i = 0; i < TOTAL; i++){
numeros[i] = ORIGEN + i;
indice[i] = i;
}
for (i = 0; i < SUBTOTAL; i++){
array[i] = numeros[indice[numaleat = rand() % (TOTAL - i)]];
if (indice[numaleat] != TOTAL - i - 1)
indice[numaleat] = indice[TOTAL - i - 1];
printf (" %3d", array[i]);
}
puts("");
return EXIT_SUCCESS;
} |
Por supuesto antes de seguir con esto quisiera que me dieras tu visto bueno. ¿Este programa en C estandar sigue siendo en esencia tu programa?
Me refiero especificamente al algoritmo.
Un saludo
_________________
The capacity to learn is a gift;
The ability to learn is a skill;
The willingness to learn is a choice.
--
Rebec of Ginaz |
| | Volver arriba | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 03/12/2005 6:20 pm | | | Título: |
| Totalmente de acuerdo. Creo suponer lo que me vas a contestar. Que el programa que pusiste hace lo mismo pero tú recorres del final al comienzo el ciclo for y estás considerando todos los números y no una parte como yo lo hago aquí, desde 0 hasta SUBTOTAL. Pero precisamente esa hace la diferencia entre lo que yo considero escoger al azar una parte de la población. Pero hay otra diferencia, al introducir el arreglo numeros en el programa puedo escoger al azar no sólo números sino cualquier tipo que yo quiera que tenga el arreglo números y tal como tu lo tienes sólo escoges números enteros.
Pero no me contestaste la pregunta de que si tu considerabas que escoger una parte de los números y después mezclarlos aleatoreamente es escoger al azar un subconjunto de la población.
Si me respondes que si, entonces estamos en desacuerdo con la definición, pero si me respodes que no, entonces tu programa no resolvió el planteamiento inicial y me gustaría pusieras el código resolviendo esta situación, aunque sea para comparar cual código resulta más compacto.
Que conste que no es una pelea, sólo un intercambio de ideas. Saludos |
| | Volver arriba | | | | psk
Registrado: 18 Nov 2005
Mensajes: 79
| | Publicado: 03/12/2005 6:22 pm | | | Título: |
| | pitukilloloco escribió: | Pues si, por eso te decía que es un compromiso entre el espacio en memoria y la rapidez. Lo que no acabo de entender es lo que dice rir3760, de que su programa es equivalente, pues el programa escoge
consecutivamente los números y después los "revuelve" pero de ninguna manera escoge números al azar, ¿cómo escogería los 30 números de los 101 que tu quieres? ¿acaso los escogería consecutivamente? ¿saltándoselos de dos en dos? Evidentemente haciéndolo así va a escoger números distintos, pero de ninguna manera serán al azar. El problema está precisamente en escoger al azar esos números y que no se repitan. |
Ups! Acabo de ver tu código ahora, no si si es que la otra vez me lo salté o que no estaba, pero sólo vi el de rir3760.
Una cosilla, entiendo lo que dices (pitukilloloco) y creo que también lo de rir3760. Me parece que ambos tenéis razón. Es cierto que coger los números como tú dices no es generar números aleatorios, pero realmente lo que hace el algoritmo de rir2760 (según he entendido) es:
Crea una tabla en la que almacena TODOS los posibles números teniendo el cuenta el rango que indica en enunciado.
Genera aleatoriamente un valor que hará de índice a la hora de leer el valor. De esta forma coge sólo un determinado número de valores de todos los posibles. El problema es que en su código de ejemplo genera 49 valores y usa los 49, de modo que otra persona que lo lee puede interpretar que simplemente los rebuja. Pero hay que tener en cuenta que el ejercicio puede pedir que se generen valores dentro de un rango de N elementos pero sólo requerir x de esos N.
ej:
Si necesita crear valores aleatorios entre 20 y 33, incluye en el array los elementos 20, 21,22...33.
Si de entre esos valores tiene que sacar 10, con un for que se ejecutará 10 veces genera valores aleatorios entre 0 y (33-20)=13 que se usarán de índice para acceder a 10 de los valores posibles.
La diferencia con mi algoritmo es que yo compruebo que el número generado no coincida con ninguno de los generados anteriormente, y él tiene que comprobar que el índice generado no coincida con ninguno de los generados anteriormente.
Lo que no veo yo aquí es dónde se gana velocidad, porque igualmente tiene que comprobar que el índice generado no está repetido, y sí que veo donde se consume más (al generar todos los posibles valores y guardarlos en memoria).
Saludos |
| | Volver arriba | | | psk
Registrado: 18 Nov 2005
Mensajes: 79
| | Publicado: 03/12/2005 6:28 pm | | | Título: |
| | pitukilloloco escribió: | Este programa que te paso a continuación es del eterno problema de espacio de memoria vs rapidez. Si lo revisas vas a ver que la función random sólo se llama el número de veces igual al de los números distintos que quieres sacar, pero por otro lado tuve que definir unos arreglos extras.
| Código: |
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
#define SUBTOTAL 30
#define TOTAL 101
#define ORIGEN 100
main ()
{
int i, j, array[SUBTOTAL], numeros[TOTAL], indice[TOTAL], numaleat;
randomize ();
while (1) {
for (i = 0; i < TOTAL; i++) {
numeros[i] = ORIGEN + i;
indice[i] = i;
}
printf ("\n");
for (i = 0; i < SUBTOTAL; i++) {
array[i] = numeros[indice[numaleat = random (TOTAL - i)]];
if (indice[numaleat] != TOTAL - i - 1)
indice[numaleat] = indice[TOTAL - i - 1];
printf ("%d ", array[i]);
}
/* comprobaci¢n */
for (i = 0; i < SUBTOTAL; i++)
for (j = 0; j < i; j++)
if (array[j] == array[i]) {
printf ("\nEl n£mero %d se repite!!!\n", array[i]);
goto ETIQUETA;
}
printf ("\nNing£n n£mero se repite");
ETIQUETA:
printf ("\t\t\tpresione 'q' para salir...");
if (getch() == 'q')
break;
}
exit (EXIT_SUCCESS);
}
|
|
Aquí si "veo" que el consumo de memoria extra hace que se recorte el consumo de procesamiento, ya que se llama a la función random el número de veces necesarias para cada valor que genera, sin tener que llamarla nuevamente en caso de colisión, porque estas no se producen. Y pongo "veo" entre comillas porque es lo que interpreto de tus palabras, pero no termino de comprender el código (no por nada, sino porque aparte de que soy novato, acabo de llegar de la juerga y no estoy demasiado lúcido). Mañana lo leeré más detenidamente, pero dos cosas:
Qué significa while (1)?
Me han enseñado que los goto's son algo muy malo. ¿por qué? y ¿por qué tu lo usas? |
| | Volver arriba | | | pitukilloloco
Registrado: 11 May 2005
Mensajes: 442
| | Publicado: 04/12/2005 12:43 am | | | Título: |
| Trata de comprender el "post" de más arriba donde pongo un ejemplo de un arreglo de 10 números para que entiendas lo que hace el programa.
Las instrucciones
y
son ciclos infinitos que siempre evalúan la condición como verdadera. La única manera de salirse de ellas son con las instrucciones
break, return o goto.
En general se aconseja no usar la instrucción goto porque dificulta la revisión del código y algunos autores recomiendan que nunca las uses. Otros autores recomiendan que los uses en ocasiones especiales, como cuando tienes muchos ciclos anidados y te quieras salir de ellos.
Es lo que hago en este caso, y sólo lo hago cuando son pocas líneas y a simple vista puedo ver donde está el goto y la etiqueta hacia donde salta. En caso de que los ciclos anidados ocupen muchas líneas yo opto por definir algunas banderas y no usar el goto. La instrucción está ahí para que la uses. Es tu decisión el hacerlo o no. Si apenas estás comenzando mi consejo es que trates de evitar usarla y ya cuando tengas más experiencia programando entonces lo hagas en contados casos como este. |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes