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

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C++] Divisibilidad por primos de un número por partes		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [C++] Divisibilidad por primos de un número por partes  (Leído 5,209 veces)
El_Lentejas

Desconectado Desconectado

Mensajes: 3


Ver Perfil
[C++] Divisibilidad por primos de un número por partes
« en: 11 Junio 2020, 18:34 pm »
Muy buenas a todos, me colocaron a realizar el siguiente problema: "El numero, 1406357289, contiene todos los dígitos del 0 al 9.

si d1 es el primer dígito, d2 es el segundo dígito, y así sucesivamente. Encuentre todos los números entre 4130912867 y 4130992867 que cumplen las siguientes condiciones :

d2d3d4=406 es divisible por 2
d3d4d5=063 es divisible por 3
d4d5d6=635 es divisible por 5
d5d6d7=357 es divisible por 7
d6d7d8=572 es divisible por 11
d7d8d9=728 es divisible por 13
d8d9d10=289 es divisible por 17 "

Ya intenté realizarlo, coloque todas las condiciones que me piden, pero al final el programa no me imprime en pantalla lo que quiero que se vea. De esta manera, agradecería si me ayudan a corregir el error, o los errores que tengo, que tengo bien, que no tengo bien, les agradecería muchísimo. Esto es lo que hice:

[
Código
  1. #include<iostream>
  2. #include<math.h>
  3. using namespace std;
  4.  
  5. int main(){
  6.  
  7.   long long int x, d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d56, d78, d89;
  8.  
  9.  for(x=4130912867;x<=4130992867;x++){
  10.  
  11.  d1=x/1000000000;
  12.  d2=x/100000000%10;
  13.  d3=x/10000000%10;
  14.  d4=x/1000000%10;
  15.  d5=x/100000%10;
  16.  d6=x/10000%10;
  17.  d7=x/1000%10;
  18.  d8=x/100%10;
  19.  d9=x/10%10;
  20.  d10=x%10;
  21.  d56=x/10000%100;
  22.  d78=x/100%100;
  23.  d89=x/10%100;
  24.  
  25.  if(d4==2 || d4==4 || d4==6 || d4==8 || d4==0) //Divisible por 2*
  26.  
  27.  //cout<<d1<<d2;
  28.  
  29.  	if(d3+d4+d5==3 || d3+d4+d5==6 || d3+d4+d5==9 || d3+d4+d5==12 || d3+d4+d5==12 || d3+d4+d5==15 || d3+d4+d5==18)//Divisible por 3
  30.  
  31.  //cout<<d3;	 
  32.  
  33. 	 	if(d6==5 || d6==0) //Divisible por 5
  34.  
  35. 	 		if((d56-(d7*2)==7) || (d56-(d7*2)==14) || (d56-(d7*2)==21) || (d56-(d7*2)==28) || (d56-(d7*2)==35) || (d56-(d7*2)==42) || (d56-(d7*2)==49) || (d56-(d7*2)==56) || (d56-(d7*2)==63) || (d56-(d7*2)==70) || 
  36. 			 (d56-(d7*2)==-7) || (d56-(d7*2)==-14) || (d56-(d7*2)==-21) || (d56-(d7*2)==-28) || (d56-(d7*2)==-35) || (d56-(d7*2)==-42) || (d56-(d7*2)==-49) || (d56-(d7*2)==-56) || (d56-(d7*2)==-63) || (d56-(d7*2)==-70))
  37. 			 	           //Divisible por 7
  38. 			 	if(d6+d8-d7==0 || d6+d8-d7==11)	//Divisible por 11
  39.  
  40. 			 		if((d78-(d9*9)==0) || (d78-(d9*9)==13) || (d78-(d9*9)==26) || (d78-(d9*9)==39) || (d78-(d9*9)==52) || (d78-(d9*9)==65) || 
  41. 					 (d78-(d9*9)==-13) || (d78-(d9*9)==-26) || (d78-(d9*9)==-39) || (d78-(d9*9)==-52) || (d78-(d9*9)==-65)) //Divisible por 13
  42.  
  43. 					 	if((d89-(d10*5)==0) || (d89-(d10*5)==17) || (d89-(d10*5)==51) || (d89-(d10*5)==68) || (d89-(d10*5)==85) ||
  44. 						  (d89-(d10*5)==-17) || (d89-(d10*5)==-51) || (d89-(d10*5)==-68) || (d89-(d10*5)==-85)) //Divisible por 17
  45.  
  46.  
  47.  
  48. 		cout<<"El numero es: "<<d1<<d2<<d3<<d4<<d5<<d6<<d7<<d8<<d9<<d10<<endl;	 
  49.  
  50.  
  51. 	 }
  52.  
  53.  
  54.  
  55. 	return 0;
  56. }
« Última modificación: 15 Junio 2020, 21:44 pm por YreX-DwX » En línea
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 1.008



Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #1 en: 11 Junio 2020, 19:28 pm »
Ese código que tienes es una locura para lo que quieres controlar.

Mi recomendación es que hagas una función:
Código
  1. int subNumero(int numero, int inicio, int longitud);
Que le pasas el número completo y te devuelve un número que empieza en el dígito <inicio> y con una longitud de <longitud>.

Y para comprobar si un número n es divisible por x, se usa el operador módulo (%):
Código
  1. if(numero % 2 == 0)
  2.   cout << "El numero " << numero << " es divisible por 2" << endl;

Con esos dos consejos deberías poder mejorar bastante ese programa.
Inténtalo y cuando te surja algún problema coméntalo para seguir ayudándote.


PD: Otra opción es guardar cada dígito en una posición del array. Pero utiliza las estructuras del lenguaje para no tener que hacer el estropicio ese de las líneas 11-23:
Código
  1. const int NUM_DIGITOS = 10;
  2.  
  3. int main(){
  4.   int numero = 4130912867;
  5.   int digitos[NUM_DIGITOS];
  6.  
  7.   for(int i = NUM_DIGITOS-1; i >= 0; --i){
  8.     digitos[i] = numero % 10;
  9.     numero /= 10;
  10.   }
  11. }
Esto modifica tu variable número original. Si no quieres que se vea modifica, crea una función a la que le pases el número como parámetro por valor.
« Última modificación: 11 Junio 2020, 19:51 pm por YreX-DwX » En línea
Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
El_Lentejas

Desconectado Desconectado

Mensajes: 3


Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #2 en: 11 Junio 2020, 22:29 pm »
Citar
Con esos dos consejos deberías poder mejorar bastante ese programa.
Inténtalo y cuando te surja algún problema coméntalo para seguir ayudándote.

Muchísimas gracias amigo, soy novato en esto y te agradezco totalmente de corazón, pude hacer el programa en menos de nada. El profesor había dicho que sólo había un número que cumplía con esas condiciones dentro de ese rango, pero siguiendo tus consejos, me salieron dos números que cumplen con las condiciones dadas dentro de ese rango. Muchas gracias por la ayuda.
En línea
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 1.008



Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #3 en: 12 Junio 2020, 02:42 am »
Me parecía sospechoso que hubiese dos números que cumpliesen las condiciones cuando tu profesor había dicho que solo habría uno. (Puede ser que se equivocase, pero no lo creo).

Si te fijas, al principio del enunciado hay otro comentario:
Cita de: El_Lentejas en 11 Junio 2020, 18:34 pm
Muy buenas a todos, me colocaron a realizar el siguiente problema: El numero, 1406357289, contiene todos los dígitos del 0 al 9.

si d1 es el primer dígito, d2 es el segundo dígito, y así sucesivamente. Encuentre todos los números entre 4130912867 y 4130992867 que cumplen las siguientes condiciones :
Código:
d2d3d4=406 es divisible por 2
d3d4d5=063 es divisible por 3
d4d5d6=635 es divisible por 5
d5d6d7=357 es divisible por 7
d6d7d8=572 es divisible por 11
d7d8d9=728 es divisible por 13
d8d9d10=289 es divisible por 17
Es cierto que hay dos números que cumplen con las condiciones recuadradas y estos son:
Código:
Numero valido: 4130952867
Numero valido: 4130959493
Pero si te fijas bien, solo uno de ellos cumple con la primera frase del enunciado (remarcada en negrita): que tenga todos los dígitos. Y este es el primero de los dos. Por lo tanto me parece que también tiene que darse esa condición y por tanto solo hay un número válido que cumpla todas las condiciones.
En línea
Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #4 en: 15 Junio 2020, 13:19 pm »
Lo primero, El_lentejas, cambia el titulo por algo m'as sugerente en vez de AYUDA PROBLEMA C++...

Esto no ayuda a los buscadores a indexar la respuesta...

Pon , "digitos y divisibilidad por primos, por ejemplo@...


Cita de: YreX-DwX en 12 Junio 2020, 02:42 am
...
Si te fijas, al principio del enunciado hay otro comentario:Es cierto que hay dos números que cumplen con las condiciones recuadradas y estos son:
Código:
Numero valido: 4130952867
Numero valido: 4130959493
...

EDIT

He decidido cambiar la respuesta, para editar un caso con mejor codigo y salida formateada.
He generalizado el problema a sacar todos los numeros especiales desde 0(10 veces)0 hasta 999(10 veces)9.
Sigue siendo de complejidad O(1), porque solo tratamos la base 10... para tratar en base N, con N arbitrariamente grande, tendriamos que hacernos con N-3 primos, cosa que, como se sabe, es muy costosa...Fundamento de  algoritmos de criptografia.

Código:
1406357289
d1d2d3 = 406 --> 406 / 2 = 203
d2d3d4 = 063 --> 063 / 3 = 21
d3d4d5 = 635 --> 635 / 5 = 127
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
1430952867
d1d2d3 = 430 --> 430 / 2 = 215
d2d3d4 = 309 --> 309 / 3 = 103
d3d4d5 = 095 --> 095 / 5 = 19
d4d5d6 = 952 --> 952 / 7 = 136
d5d6d7 = 528 --> 528 / 11 = 48
d6d7d8 = 286 --> 286 / 13 = 22
d7d8d9 = 867 --> 867 / 17 = 51
----------
1460357289
d1d2d3 = 460 --> 460 / 2 = 230
d2d3d4 = 603 --> 603 / 3 = 201
d3d4d5 = 035 --> 035 / 5 = 7
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
4106357289
d1d2d3 = 106 --> 106 / 2 = 53
d2d3d4 = 063 --> 063 / 3 = 21
d3d4d5 = 635 --> 635 / 5 = 127
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
4130952867
d1d2d3 = 130 --> 130 / 2 = 65
d2d3d4 = 309 --> 309 / 3 = 103
d3d4d5 = 095 --> 095 / 5 = 19
d4d5d6 = 952 --> 952 / 7 = 136
d5d6d7 = 528 --> 528 / 11 = 48
d6d7d8 = 286 --> 286 / 13 = 22
d7d8d9 = 867 --> 867 / 17 = 51
----------
4160357289
d1d2d3 = 160 --> 160 / 2 = 80
d2d3d4 = 603 --> 603 / 3 = 201
d3d4d5 = 035 --> 035 / 5 = 7
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
A falta de un criterio de divisbilidad para cualquier numero primo, no tenemos mas remedio que practicar la division y ver el resultado, lo que se traduce en una ténica de "fuerza bruta" o "backtraking".

El backtraking consiste en explorar todas las posibildades de un arbol de decision... Ensayamos en primer lugar el 0, depues cualquier numero menos el 0, que puedeser el {1,2,3,4,5,6,7,8,9}... Si cogemos el 1, entonces para la tercera cifra dispondremos de {2,3,4,5,6,7,8,9}. Pero si cogemos el 2 entonces tendermso {1,3,4,5,6,7,8,9}... Como se puede intuir, algo por lo menos exponencial. 10^10.
un 10 seguido de 10 ceros...

Se puede recortar computos marcando los digitos que ya se han usado, para asi no volverlos a usar... (podar el espacio de soluciones...) Si procedemos con una busqueda por profundidad, la recursion nos proporciona gratis la estructura de pila necesaria para hacer el recorrido...

Bueno,... miraros los esquemas de programacion "vuelta atras" y sabreis a lo que me refiero.

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  4.  
  5. #define MAX 10
  6. const int N = MAX ;   // i.e O(1)
  7. static  int d[MAX];
  8. static const  int primes[MAX-3]={2,3,5,7,11,13,17}; // N primes is very hard to compute.
  9.  
  10.  
  11.  
  12. void print_solution(const int d[])
  13. {
  14.   for(int n=0;n<10;n++) printf("%d",d[n]);
  15.   printf("\n");
  16.   for(int n=1;n<8;n++)
  17.     {
  18.       char s[4];
  19.       sprintf(s,"%d%d%d",d[n],d[n+1],d[n+2]);
  20.       int num=atoi(s);
  21.       printf("d%dd%dd%d = %03d --> %03d / %d = %d\n",n,n+1,n+2,num,num,primes[n-1],num/primes[n-1]);
  22.     }
  23.   printf("----------\n");
  24.   return;
  25. }
  26.  
  27. /* O(1) Specialzer.*/
  28. void primeG(const int k, const int part,const int N)
  29. {
  30.   static int free[MAX]={1,1,1,1,1,1,1,1,1,1};
  31.  
  32.   //  printf("%d\n",k);
  33.   if (k==N)
  34.     {
  35.       print_solution(d);
  36.       return;
  37.     }
  38.   else
  39.     for(int c=0; c<10; c++)
  40.     {
  41.       if (!free[d[k]=c]) continue;
  42. #define DDD (10*part + c)
  43.       if ((k>2) && (DDD%primes[k-3])) continue; 
  44.       free[c]=0;
  45.       primeG(k+1,DDD%100,MAX);
  46.       free[c]=1;
  47.     }
  48.   return;
  49. }
  50.  
  51.  
  52.  
  53.  
  54.  
  55. int main(int argc, char *args)
  56. {
  57.   // Call Specializer.
  58.   primeG(0,0,MAX);
  59.   return 0;
  60. }
  61.  
« Última modificación: 17 Junio 2020, 21:54 pm por dijsktra » En línea
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
K-YreX
Moderador
***
Desconectado Desconectado

Mensajes: 1.008



Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #5 en: 15 Junio 2020, 21:42 pm »
Cita de: dijsktra en 15 Junio 2020, 13:19 pm
Lo primero, El_lentejas, cambia el titulo por algo m'as sugerente en vez de AYUDA PROBLEMA C++...

Esto no ayuda a los buscadores a indexar la respuesta...

Pon , "digitos y divisibilidad por primos, por ejemplo@...
Sí que es cierto que estaría bien poder identificar los temas del foro por su título en vez de tener que ir entrando a cada uno de ellos hasta encontrar el que estabas buscando pero está visto que los tópicos de "ayuda", "urgente",... no van a desaparecer. Hace poco creo que leí un tema en otro subforo sobre esto mismo.

Cita de: dijsktra en 15 Junio 2020, 13:19 pm
Como tu dices, sólo hay uno.
Código:
$ gcc primes.c -o main && ./main
4130952867
----------

Lo que no sé es como has llegado a la conclusion de que hay más de uno con las "condiciones cuadradas". Aquí va mi idea.

La situación para que aparezca más de una solución es que como dije no se estaba tomando la condición de que el número tenía que contener cada dígito una vez, desde un principio. Entonces si nos fijamos únicamente en las condiciones que recuadré con la etiqueta code, siendo estas las condiciones de divisibilidad, hay dos números que las cumplen.

Claro que teniendo desde el principio en cuenta la otra condición de unicidad de los dígitos se puede exprimir mucho más el problema y llegar a una solución como la que muestras (que cuando tenga más tiempo le daré unas vueltecillas porque a mí no se me habría ocurrido hacerlo así  :xD)
En línea
Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 110


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: AYUDA PROBLEMA C++
« Respuesta #6 en: 17 Junio 2020, 21:56 pm »
Cita de: YreX-DwX en 15 Junio 2020, 21:42 pm
...
Claro que teniendo desde el principio en cuenta la otra condición de unicidad de los dígitos se puede exprimir mucho más el problema y llegar a una solución como la que muestras (que cuando tenga más tiempo le daré unas vueltecillas porque a mí no se me habría ocurrido hacerlo así  :xD)

He arreglado la respuesta que compuse en https://foro.elhacker.net/programacion_cc/c_divisibilidad_por_primos_de_un_numero_por_partes-t505293.0.html;msg2223708#msg2223708

Echale un vistazo, esta mas clara,.
En línea
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
[Ayuda] Problema VB 6
Programación Visual Basic 		.kiM 4 2,110 Último mensaje 22 Julio 2010, 05:14 am
por raul338
Ayuda en un problema de c++
Programación C/C++ 		Pwma 1 2,094 Último mensaje 25 Noviembre 2010, 23:38 pm
por darkvidhack
AYUDA .... problema con
Bases de Datos 		jamarchi 3 2,386 Último mensaje 13 Enero 2011, 19:09 pm
por Skeletron
Ayuda con un problema en C.
Programación C/C++ 		miguel1912 3 2,453 Último mensaje 18 Julio 2017, 05:10 am
por engel lex
Ayuda con un problema
Programación C/C++ 		gonwhter 1 3,038 Último mensaje 1 Diciembre 2020, 18:02 pm
por @XSStringManolo
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines