[C++] Divisibilidad por primos de un número por partes

Iniciado por El_Lentejas, 11 Junio 2020, 18:34 PM

0 Miembros y 1 Visitante están viendo este tema.

Imprimir
Ir Abajo Páginas1
Acciones del Usuario

El_Lentejas

11 Junio 2020, 18:34 PM Ultima modificación: 15 Junio 2020, 21:44 PM por YreX-DwX
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 (cpp) [Seleccionar]
#include<iostream>
#include<math.h>
using namespace std;

int main(){

 long long int x, d1, d2, d3, d4, d5, d6, d7, d8, d9, d10, d56, d78, d89;

for(x=4130912867;x<=4130992867;x++){

d1=x/1000000000;
d2=x/100000000%10;
d3=x/10000000%10;
d4=x/1000000%10;
d5=x/100000%10;
d6=x/10000%10;
d7=x/1000%10;
d8=x/100%10;
d9=x/10%10;
d10=x%10;
d56=x/10000%100;
d78=x/100%100;
d89=x/10%100;

if(d4==2 || d4==4 || d4==6 || d4==8 || d4==0) //Divisible por 2*

//cout<<d1<<d2;

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

//cout<<d3;

if(d6==5 || d6==0) //Divisible por 5

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) ||
(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))
          //Divisible por 7
if(d6+d8-d7==0 || d6+d8-d7==11) //Divisible por 11

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) ||
(d78-(d9*9)==-13) || (d78-(d9*9)==-26) || (d78-(d9*9)==-39) || (d78-(d9*9)==-52) || (d78-(d9*9)==-65)) //Divisible por 13

if((d89-(d10*5)==0) || (d89-(d10*5)==17) || (d89-(d10*5)==51) || (d89-(d10*5)==68) || (d89-(d10*5)==85) ||
 (d89-(d10*5)==-17) || (d89-(d10*5)==-51) || (d89-(d10*5)==-68) || (d89-(d10*5)==-85)) //Divisible por 17
 
 

cout<<"El numero es: "<<d1<<d2<<d3<<d4<<d5<<d6<<d7<<d8<<d9<<d10<<endl;


}
 


return 0;
}

K-YreX

#1
11 Junio 2020, 19:28 PM Ultima modificación: 11 Junio 2020, 19:51 PM por YreX-DwX
Ese código que tienes es una locura para lo que quieres controlar.

Mi recomendación es que hagas una función:
Código (cpp) [Seleccionar]
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 (cpp) [Seleccionar]

if(numero % 2 == 0)
 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 (cpp) [Seleccionar]

const int NUM_DIGITOS = 10;

int main(){
  int numero = 4130912867;
  int digitos[NUM_DIGITOS];

  for(int i = NUM_DIGITOS-1; i >= 0; --i){
    digitos[i] = numero % 10;
    numero /= 10;
  }
}
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.
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

El_Lentejas

#2
11 Junio 2020, 22:29 PM
CitarCon 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.

K-YreX

#3
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 [Seleccionar]

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 [Seleccionar]

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.
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

dijsktra

#4
15 Junio 2020, 13:19 PM Ultima modificación: 17 Junio 2020, 21:54 PM por dijsktra
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 [Seleccionar]

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 [Seleccionar]
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 (c) [Seleccionar]
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX 10
const int N = MAX ;   // i.e O(1)
static  int d[MAX];
static const  int primes[MAX-3]={2,3,5,7,11,13,17}; // N primes is very hard to compute.



void print_solution(const int d[])
{
  for(int n=0;n<10;n++) printf("%d",d[n]);
  printf("\n");
  for(int n=1;n<8;n++)
    {
      char s[4];
      sprintf(s,"%d%d%d",d[n],d[n+1],d[n+2]);
      int num=atoi(s);
      printf("d%dd%dd%d = %03d --> %03d / %d = %d\n",n,n+1,n+2,num,num,primes[n-1],num/primes[n-1]);
    }
  printf("----------\n");
  return;
}

/* O(1) Specialzer.*/
void primeG(const int k, const int part,const int N)
{
  static int free[MAX]={1,1,1,1,1,1,1,1,1,1};

  //  printf("%d\n",k);
  if (k==N)
    {
      print_solution(d);
      return;
    }
  else
    for(int c=0; c<10; c++)
    {
      if (!free[d[k]=c]) continue;
#define DDD (10*part + c)
      if ((k>2) && (DDD%primes[k-3])) continue;
      free[c]=0;
      primeG(k+1,DDD%100,MAX);
      free[c]=1;
    }
  return;
}





int main(int argc, char *args)
{
  // Call Specializer.
  primeG(0,0,MAX);
  return 0;
}



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

#5
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 [Seleccionar]

$ 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)
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

dijsktra

#6
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,.
Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Imprimir
Ir Arriba Páginas1
Acciones del Usuario