| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 90
|  Publicado: 02/10/2007 12:55 pm | | | Título: |
| | cheroky escribió: |
En lo que si estaras conmigo es que este número
| Código: | 126000=6*21000
126000=21*6000
126000=60*2100 |
generado por tu programa no es vampiro ni pseudovampiro.
|
¿Por qué no? 126000 se puede descomponer de 3 maneras en factores que contienen las mismas cifras que 126000.
| digies escribió: | | Número vampiro: todo número natural para el cual exista una factorización formada por lo dígitos del propio número. Por ejemplo, el número 126 es un número vampiro ya que lo podemos factorizar así: 126=21·6. |
Ahora me he quedado descolocado, no se que quieres decir exactamente, cheroky.
editado: ¿no te estarás refieriendo a que piensas que "exista una factorización" quiera decir "exista una factorización y sólo una" en vez de "existe almenos una factorización"?
Saludos! |
| | Volver arriba | |  | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 90
| | Publicado: 02/10/2007 10:47 pm | | | Título: |
| | cheroky escribió: | | Pantalàimon_ escribió: | | Bueno, pues acepto esta definición por convenio si quieres, no pasa nada, aunque no es la única. He visto en varios lugares definir los pseudovampiros como vampiros. No es un problema de invención, descubrimiento o opinión, es un problema de definición, es decir, de lenguaje. Así que yo no me atreviría a decir ni que tienes razón tú ni que tengo razón yo, todo depende de en que idioma haya hablado bosterito. |
Entonces, sin querer liar más el asunto, creo que no deberías haber dicho en tu anterior post lo contrario. |
A ver, que quede claro, yo en ningún momento dije que tuviera la razón, simplemente dije que no estaba de acuerdo. |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 04/10/2007 2:16 am | | | Título: |
| Otra propuesta, es bastante más rápida que la anterior, y genera números muy grandes relativamente rápido, aun así se pondría optimizar un poco más, pero ahora ando bastante cansado para revisarlo o mejorarlo, no descarto que tenga algún fallo.
| Código: | #include <stdio.h>
#define ITOC(vec,n,i) {int j = i; do { (vec[j--]) = (n) % 10; } while ( (n)/=10 );}
#define MAX_BUF 8
int xsort(char *v, size_t t)
{
int i,j;
char c,b;
for(i = 0,b =0; i < t; i++)
{
for(j = 0; j < t-1; j++)
if(v[j] < v[j+1]){
c = v[j+1]; v[j+1]=v[j];
v[j] = c;
b=1;
}
if(!b)return 0;
}
return 0;
}
int parser(int y, int z, int n, int seek)
{
char buf_yz[MAX_BUF]={0};
char buf_nu[MAX_BUF]={0};
char *p_yz, *p_aux;
int ky = y, kz = z;
ITOC(buf_yz,y, MAX_BUF-1);
p_yz = p_aux = buf_yz;
while(!*p_aux) p_aux++;
ITOC(buf_yz,z, p_aux-p_yz -1);
ITOC(buf_nu,n,MAX_BUF-1);
xsort(buf_yz, MAX_BUF);
xsort(buf_nu, MAX_BUF);
for(p_yz=buf_yz, p_aux=buf_nu;
*p_yz == *p_aux && *p_yz;
p_yz++, p_aux++);
if(!(*p_yz - *p_aux))
{
if(seek)
{ if(ky * kz == seek)
printf("Encontrado %d = %d * %d\n", ky * kz, ky, kz );
return 0;
}else
printf("%d = %d * %d\n", ky * kz, ky, kz );
}
return 0;
}
void proc(int i, int f, int L,int seek)
{
int y,z;
for(y = i; y <= L; y++)
for(z = f; z <= L; z++)
if(z > y)
parser(y, z, y*z, seek);
}
#define TOP 999 /* 999^2 */
int main(void)
{
proc(1,1,TOP,0); /* 0 Generar rango. n Numero concreto */
return 0;
} |
La generación la realiza de forma cuadratica y puede hacerlo con pseudos y originales.
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | Volver arriba | | | | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 90
| | Publicado: 04/10/2007 3:29 am | | | Título: |
| Oh, genial si se puede hacer en tiempo polinomial! 
edit: a ver si cuando tengas un momento me puedes explicar como funcionan tus dos códigos. Que no lo acabo de comprender.
Saludos! |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 04/10/2007 9:31 am | | | Título: |
| Cuando tengo un rato te explico, aún ando asombrado con ese algoritmo, es rapidisimo 0_0
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | Volver arriba | | | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 90
| | Publicado: 04/10/2007 3:34 pm | | | Título: |
| Record!
Acabo de hacer uno más rápido que también genera número vampiros. Pero con una pequeña trampa, no los genera ordenados pero los genera todos. 
Aquí van 33 líneas de código:
| Código: | #include<stdio.h>
char criba(int vamp,int prod1,int prod2,char dgts,int nprod)
{
int i,j,k;
char *vec;
if(vamp<10*nprod*nprod) return 0;
vec= (char*) malloc(2*dgts);
for(i=0;i<2*dgts;i++) vec[i]=1;
prod1+=10*nprod*prod2;
for(i=vamp; i ;i/=10)
for(j=prod1,k=0;j;j/=10,k++ )
if((i%10)==(j%10)&&vec[k])
{
vec[k]=0;
break;
}
for(i=0;i<2*dgts;i++)
if(vec[i]) return 0;
return 1;
}
int main(void)
{
int exp,num;
int prod1,prod2;
for(exp=1,num=1;exp<4;exp++,num*=10)
for(prod1=num+1;prod1<10*num;prod1++)
for(prod2=prod1;prod2<10*num;prod2++)
if(criba(prod1*prod2,prod1,prod2,exp,num))
printf("%d=%d*%d\n",prod1*prod2,prod1,prod2);
return 0;
} |
Creo que es hora de ir comentado nuestras artimañas usadas a ver si podemos crear un turbovampiro.
edit: veo que el tuyo también los genera desordenados, esto es por generarlos a partir de los productos. Esta cosa es clave.
Saludos! |
| | Volver arriba | | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 06/10/2007 11:34 pm | | | Título: |
| | Pantalàimon_ escribió: | Record!
Acabo de hacer uno más rápido que también genera número vampiros. Pero con una pequeña trampa, no los genera ordenados pero los genera todos. :P
Aquí van 33 líneas de código:
|
¡Record batido!
Este es casi instantaneo en el primer 1000k, es mas rapido que la consola :-D Verle trabajar con vampiros de 10 digitos es sorprendente, al menos comparando con las otras implementaciones.
Se compila para el estandar C99.
| Código: | #include <stdio.h>
#include <stdint.h>
#define ITOC(vec,n) for(int8_t *p = (vec); (n); (n/=10)) (*p++) = (n%10)
#define NEG ~0x0LL
int ncmp(int8_t *buf, int y)
{
int tmp,bmp = 0, i=0;
for (; y ;y/=10) {
tmp = y % 10;
for(i = 0; i < 8; i++) {
if(buf[i] == tmp && buf[i] != -1){
buf[i] = -1;
break;
}
}
bmp++;
}
return bmp;
}
int ncmp2(int n, int y, int z)
{
int nn=0, r=0, par=0;
for(;n ;n/=10){ nn+= n%10; par++; }
if( par & 1) return -1;
for(;y ;y/=10) r+= y%10;
for(;z ;z/=10) r+= z%10;
return nn - r;
}
#define TOP 10000
int main()
{
int8_t buf[8];
int y = 1 ,z = 1 , MAX = 100, n , prn;
*((uint64_t*) buf) = NEG;
for(;MAX < TOP; MAX*=10 )
for(y = MAX/10; y < MAX; y++)
for(z = y ; z < MAX; z++) {
prn = n = y * z;
if(n / 10 != z) {
if(!ncmp2(n, y, z)) {
ITOC(buf, n);
ncmp(buf, y);
ncmp(buf, z);
if( *((uint64_t*) buf) == NEG )
printf("%d=%d*%d\n", prn, y, z);
}
}
}
return 0;
} |
Si lo haces más eficiente, me obligarías hacerlo en ensamblador :-D
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso.
Ultima edición por cheroky el 07/10/2007 9:28 am; editado 4 veces |
| | Volver arriba | | | Pantalàimon_
Registrado: 17 Jul 2007
Mensajes: 90
| | Publicado: 07/10/2007 4:38 am | | | Título: |
| Mierda, iba todo ansioso a ver que tal tu programa pero no me compila...
In function `main':
43 [Warning] integer constant is too large for "long" type
51 'for' loop initial declaration used outside C99 mode
54 [Warning] integer constant is too large for "long" type
57 [Warning] integer constant is too large for "long" type |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 07/10/2007 6:57 am | | | Título: |
| | Pantalàimon_ escribió: | Mierda, iba todo ansioso a ver que tal tu programa pero no me compila...
In function `main':
43 [Warning] integer constant is too large for "long" type
51 'for' loop initial declaration used outside C99 mode
54 [Warning] integer constant is too large for "long" type
57 [Warning] integer constant is too large for "long" type |
Ya comente en el post que se compila para C99, en gcc el flag apropiado es -std=c99, de todos modos es fácil modificarlo para c90.
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | Volver arriba | | | | guimel
Registrado: 17 Oct 2007
Mensajes: 11
| | Publicado: 21/10/2007 1:08 pm | | | Título: |
| Hola!
Al ver este post, no he podido evitar enviar una propuesta de solución. A ver qué os parece
| Código: | #include <string> #include <algorithm> #include <iostream> #include <sstream> #include <math.h> using namespace std; // Devuelve cierto si a es una permutacion de los digitos de b bool compara( int a, int b ) { stringstream ss; string stra; string strb; ss << a; ss >> stra; ss.clear(); ss << b; ss >> strb; sort(stra.begin(),stra.end()); sort(strb.begin(),strb.end()); return( stra == strb ); } // Genera una lista de vampiros de hasta digits digitos void vampiros(int digits) { int factor1=10; int factor2=10; int factor2ant=1; int res; for (int lim =1; lim < digits / 2; ++lim ) { for (int i=1; i <= lim; ++i) { for (int j=1; j<= digits - lim ; ++j) { for (int ii=factor2ant; ii< factor2; ++ii) { for (int jj=1; jj< factor1; ++jj) { res=ii*jj; if (compara( res, ii * factor1 + jj )) { cout << res << "es el producto de "<< ii << " por "<< jj << endl; } } } factor2ant = factor2; factor2 = factor2 * 10; } factor1 = factor1 * 10; } } } // Genera una lista de vampiros de hasta digits digitos void vampirosVerdaderos(int digits) { int res; int limsup = pow(10.0, int(digits/2)); int liminf = pow(10.0, int(digits/2)-1); for (int ii = liminf; ii < limsup; ++ii) { for (int jj = liminf; jj < ii; ++jj) { res=ii*jj; if (compara( res, ii * limsup + jj )) { cout << res << "es el producto de "<< ii << " por "<< jj << endl; } } } } int main( int argc, char *argv[]) { cout<<"Buscando vampiros..."<<endl; vampiros(4); cout<<"buscando vampiros verdaderos..."<<endl; vampirosVerdaderos(4); char z; cout<<"Fin del programa"<<endl; cin>>z; } |
He cambiado un poco el enfoque. Lo que hace el programa es iterar sobre los posibles factores y evaluar si el producto es un vampiro. He creado dos funciones: una devuelve todos los vampiros de hasta n dígitos, y la otra calcula los vampiros verdaderos de exáctamente n cifras.
_________________
Las ciencias de la computación están tan poco relacionadas con las computadoras como la astronomía con los telescopios
Edsger Dijkstra |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 21/10/2007 3:19 pm | | | Título: |
| Se agradece un aporte en puro C++.
Creo que deberías revisar el código, no lo he mirado bien por falta de tiempo pero parece que arroja resultados erróneos.
Otra cuestión es en la función vampirosverdaderos donde se producen sendos warnings al truncar un tipo double sobre int, se hace necesario un cast.
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | Volver arriba | | | guimel
Registrado: 17 Oct 2007
Mensajes: 11
| | Publicado: 22/10/2007 10:18 am | | | Título: |
| Hola!
Bueno, he comparado los resultados, y al menos los de la función de vampiros verdaderos no parecen incorrectos. El problema es que los devuelve desordenados, y cuesta verificarlos. Además, repite el mismo vampiro si tiene varios pares de colmillos distintos.
Es cierto, se me ha pasado el cast  . A ver si pulo un poco el programita y publico una versión mejorada.
_________________
Las ciencias de la computación están tan poco relacionadas con las computadoras como la astronomía con los telescopios
Edsger Dijkstra |
| | Volver arriba | | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 22/10/2007 12:01 pm | | | Título: |
| Entonces debo entender que la impresión de "buscando vampiros" ¿se refiere a números en los que debe buscar?.
| Código: |
buscando vampiros verdaderos...
3968es el producto de 64 por 62
1752es el producto de 73 por 24
1804es el producto de 82 por 22
1092es el producto de 91 por 12
2093es el producto de 91 por 23
3094es el producto de 91 por 34
4095es el producto de 91 por 45
5096es el producto de 91 por 56
6097es el producto de 91 por 67
7098es el producto de 91 por 78
8099es el producto de 91 por 89
3948es el producto de 94 por 42
7938es el producto de 98 por 81
Fin del programa
|
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | Volver arriba | | | guimel
Registrado: 17 Oct 2007
Mensajes: 11
| | Publicado: 24/10/2007 9:32 am | | | Título: |
| Me he quedado pasmado. No lo comprendo!! Mi salida es esta:
buscando vampiros verdaderos...
1435es el producto de 41 por 35
1530es el producto de 51 por 30
1260es el producto de 60 por 21
2187es el producto de 81 por 27
6880es el producto de 86 por 80
1827es el producto de 87 por 21
1395es el producto de 93 por 15
Fin del programa
He comprobado si el programa que había posteado era el que yo estaba probando, e incluso he compilado el que había posteado en el foro, pero la salida del programa es la que copio arriba.
_________________
Las ciencias de la computación están tan poco relacionadas con las computadoras como la astronomía con los telescopios
Edsger Dijkstra |
| | Volver arriba | | | cheroky
Registrado: 22 Sep 2005
Mensajes: 1372
Ubicación: En ecx esperando un call
| | Publicado: 24/10/2007 12:40 pm | | | Título: |
| Es curioso, te sugiero que lo investigues, compilado con VC++ e Intel Compiler la salida es correcta, sin embargo con g++ (Mingw) y/o Digital Mars la salida es la que te he posteado :-S
S2.
_________________
- Explícito es mejor que implícito.
- Simple es mejor que complejo.
- Complejo es mejor que complicado.
- Plano es mejor que anidado.
- Ralo es mejor que denso. |
| | 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