Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: mendez1415 en 21 Diciembre 2016, 18:17 pm



Título: multiplo de 11,100 digitos
Publicado por: mendez1415 en 21 Diciembre 2016, 18:17 pm
Su trabajo es, dado un número positivo N, determinar si es un múltiplo de once.
Especificación de entrada
La entrada es un archivo tal que cada línea contiene un número positivo. Una línea que contiene el número 0 es el final de la entrada. Los números dados pueden contener hasta 1000 dígitos.
Especificación de salida
La salida del programa indicará, para cada número de entrada, si es un múltiplo de once o no.

He buscado y buscado información, pero no encuentro como leer un numero de hasta mil digitos, espero que alguien pueda ayudarme, gracias.


Título: Re: multiplo de 11,100 digitos
Publicado por: engel lex en 21 Diciembre 2016, 18:50 pm
tienes 2 caminos, usar matemática de precisión arbitraria o usar matemáticas... si es un trabajo de la uni, dudo que te permitan usar la primera opción...

para la primera un post que hice alguna vez, te puede ayudar, con esta librería pude calcular pi a 11mil digitos, pero puede servir para cualquier cosa

https://foro.elhacker.net/programacion_cc/calculo_de_pi_en_alta_precision_aporte-t412338.0.html (https://foro.elhacker.net/programacion_cc/calculo_de_pi_en_alta_precision_aporte-t412338.0.html)

usando matemáticas, es hacer una algoritmo tal que puedas procesar el numero sin cargarlo...

es decir, por ejemplo...

tienes 9922121546975235412361002225 que en C/C++ no lo vas a poder cargar porque tiene más de 64 bits... para saber si un numero es multiplo, lo que haces es divirdirlo... te explico un poco como se hace la división para que veas que lo puedes hacer sin cargar el numero completo, esto debes ya haberlo estudidado antes en la primaria, pero como no se si lo conoces, igual lo desgloso paso a paso...

como el resultado final (cociente) no nos importa, sino solo el resto, no lo arrastraremos


9922121546975235412361002225 / 11

Código:
set: 
dividendo = 0
resto = 0
divisor = 11
resultado = 0
---
paso 0: tomas el primer numero, si es menor que el divisor tomas uno más y repites hasta tener mayor que el divisor
---
paso 1: divides como enteros,  sacas el resto y lo guardas
---
paso 2: multiplicas el resultado actual por el divisor y se lo restas al dividendo, luego tomas el siguiente digito del numero a dividir, multiplicas el dividendo resultante por 10 y le sumas el valor extraido, si el numero obtenido es menor que el divisor, multiplicas el resultado por 10, multiplicas el dividendo por 10 y repites este paso
---
paso 3:
repetir desde el paso 1 y hasta agotar los digitos, si el resto es diferente de 0, entonces no es divisible

y como sería

Código:
set: 
char* procesar = 9922121546975235412361002225
entero dividendo = 0
entero resto = 0
entero divisor = 11
entero resultado = 0


paso 0:
dividendo = 9
procesar = 922121546975235412361002225
dividendo < dividor? si
dividendo = 99
procesar = 22121546975235412361002225

paso 1:
resto = dividendo % divisor ->0
resultado = dividendo / divisor ->9

paso 2:
dividendo = dividendo - resultado * divisor ->0
dividendo = dividendo * 10 + 2 -> 2
procesar = 2121546975235412361002225
dividendo < divisor? si
dividendo = dividendo * 10 + 2 -> 22
procesar = 121546975235412361002225

paso 3
procesar contiene numeros? si
ir al paso 1

....... varias operaciones despues

paso 3
procesar contiene numeros? no
resto = 1
resto == 0? no
imprimir "no es multiplo"



Título: Re: multiplo de 11,100 digitos
Publicado por: do-while en 23 Diciembre 2016, 17:13 pm
A ver, matemáticas básicas de primaria. Un número es múltiplo de 11 si, empezando a contar por la cifra menos significativa, la diferencia entre la suma de las cifras que ocupan una posición impar y la suma de los que ocupan posiciones pares es un múltiplo de 11 (algebraicamente se demuestra con congruencias, pero no hace falta tanto detalle).

Por ejemplo:
  1903
   Cifras en posiciones impares: 3 y 9 que suman 12
   Cifras en posiciones pares: 0 y 1 que suman 1
   Diferencia de las sumas: 11 que es múltiplo de 11 y por lo tanto 1903 es múltiplo de 11.

En la práctica te da lo mismo empezar por las posiciones pares o impares, ya que si x es múltiplo de 11, -x también lo es, así que lo único que tendrás que hacer es ir sumando y restando las cifras según las vayas leyendo y comprobar si el resultado final es múltiplo de 11.

Por si hay alguna duda, cero es múltiplo de cualquier número 0 = 0 · x, así que si la diferencia es cero también será múltiplo de 11 (por ejemplo 132).


Título: Re: multiplo de 11,100 digitos
Publicado por: engel lex en 23 Diciembre 2016, 17:43 pm
desconocía esta teoría, pero si parece solida y probando me da bien...


Título: Re: multiplo de 11,100 digitos
Publicado por: Naimaderis en 23 Diciembre 2016, 22:20 pm
Si ese numero modulo 11 da 0, es multiplo de 11, por ejemplo 110%11 = 0, entonces 110 es multiplo de 11.


Título: Re: multiplo de 11,100 digitos
Publicado por: engel lex en 23 Diciembre 2016, 22:22 pm
Si ese numero modulo 11 da 0, es multiplo de 11, por ejemplo 110%11 = 0, entonces 110 es multiplo de 11.

es una explicación (diciendo lo mismo que do-while) o una pregunta?


Título: Re: multiplo de 11,100 digitos
Publicado por: Naimaderis en 23 Diciembre 2016, 22:55 pm
es una explicación (diciendo lo mismo que do-while) o una pregunta?
Pido disculpas por eso, no vi que habia respuestas. Generalmente, veo el tema principal, y si puedo ayudar a resolverlo, respondo directamente. De ahora en adelante lo tendré en cuenta, para evitar redundancias. Ademas, su respuesta fue mejor que la mia.


Título: Re: multiplo de 11,100 digitos
Publicado por: engel lex en 23 Diciembre 2016, 23:00 pm
por un lado tu respuesta de ninguna manera resolvería el problema, ya que primero necesitaría carga una variable de tipo numerico de 1000 digitos de largo antes de hacer modulo

por otro lado, es de mala educación para los que respondieron y es un comportamiento totalmente inapropiado para un foro que entes y des una respuesta sin leer los comentarios... esto ultimo que quede en claro! ya que hace perder tiempo a los demás y popula el foro de contenido redundante y sobrante sin necesidad