Divide y vencerás

Este quizá sea un dicho bélico, aplicandose cuando el volumen del enemigo es muy considerable, tanto que para poder someterlo o extinguirlo sea necesario reducirlo apequeñas fracciones.

 Una filosofía que no sé hasta que punto sea atinada, sin embargo, su esencia puede ser llevada al mundo de la informática, entre otras muchas disciplinas.

Hace mucho tiempo, cuando me dedicaba a intentar resolver problemas matemáticos de un sitio especialmente dispuesto a ello me encontré una dificultad que me volvió loco. En primer instancia, por mi falta de habilidad/práctica para desarrollar...pero en especial, me rehusé a utilizar un lenguaje de programación que permitiera resolver el problema sin astucia alguna. Ya estamos empezando a hablar de un problema, eso significa que vamos casi a la mitad de este post y me llena de felicidad comentar que por fin he hallado la solución. No la he inventando yo, pero al final la he entendido y aprehendido para lo que venga.

El problema, como quien dice, lo mero bueno.


The series, 11 + 22 + 33 + ... + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + ... + 100010

Dicho problema pertence al sitio de projecteuler.net, del cual estoy seguro que alguna vez tuve que haber mencionado y no ahondaré al respecto. En específico es el problema número 48, así que quien guste puede intentarlo. Mi ojbeto es plasmar únicamente lo que pude asimilar, no es dar una metodología de resolución de problemas así, aunque podría fungir en algun momento como tal.

La primer idea surgió de python, y es como conseguí acceso al foro, para posteriormente podero hallar, con un poco de suerte, de la forma que yo lo había empezado.

El código que motivó lo posterior es>


sum=0;
mod = pow (10, 10)

for x in range(1,1001):
  sum+=pow(x,x);

print sum % mod


Como ven, el tipo de dato está resuelto, y no está demás mencionar la velocidad con la que hace el cálculo de la suma de potencias. Está resuelto debido a que puede almacenar una cantidad estúpida de caracteres. Algo así como 3000 dígitos.

Encontré muchas soluciones con Java, algo que siempre me rehusé por la mala imagen que tiene ante mis ojos. Un código muy frecuente es:

package projecteuler;

import java.math.BigInteger;

public class Problem48 {

    public static void main(String[] args) {
        BigInteger sum = BigInteger.ZERO;
        for (Integer i = 1; i <= 1000; i++) {
            sum = sum.add(new BigInteger(i.toString()).pow(i));
        }
        System.out.println(sum.toString().substring(sum.toString().length()

- 10, sum.toString().length()));
    }
}
¿muy bonito no? Pero sigue sin ser lo que buscamos, queremos algo más ingenioso con tipos de datos estrictos y que pronga a prueba nuestra mente. Bueno, ya llegamos a la última parte, sí esa, dónde yo les digo el motivo bien exacto de este post. En C puro, alguien hizo el favor de subir su algoritmo, y gracias a ello entendi el concepto de "divide y vencerás"

#include

long long pow(int a)
{
        int i;
    long long ans=1;
        for(i=1;i<=a;i++)
        {
                ans*=a;
                ans=ans%1000000000000;
        }
        return ans;
}


void main()
{
    long long pow(int a);
        int i;
        long long sum=0;
         for(i=1;i<=1000;i++)
         {
                sum=(sum+pow(i))%

1000000000000;
         }
         sum=sum%1000000000000;
         printf("%lld",sum);
}

Como vemos no es un código de lo más complejo, pero la idea es la que se me hace buena. La función pow, tiene como tipo de dato long long, es decir, puede albergar muchas cifras, pero no las que necesitamos. Hasta aquí nada de nuevo, al menos para mi, pero sí en las líneas sum=(sum+pow(i))%
1000000000000 y ans=ans%1000000000000, ya que con ella se reduce la cantidad de datos a almacenar, en el sentido de que se queda con los residuos, siendo una cifra no mayor a los diez dígitos (condición del problema), así quitamos toda la basura restante que imposibilita el alacenar el dato completo. Para hacer el experimento hice el siguiente mini código.

#include

int main() {

int sum = 0;
int a = 798078764;
int b = 1000;

sum = a % b;
printf ("suma: %i", sum);

return 0;
 }

Si observan las salidas pueden entender como va eso de que el mod funge como discriminante de dígitos.

Espero les haya quedado sumamente claro el problema y la solución que esta persona dio. El tiempo también es bastante bueno.


Apéndice.

Cifra completa:

10003681991446951770953750112276467955677936806229346545837609
88100234910747716194381428659099527845945869942643191290894720
34297990640767964725986043423846803832604080969103761537037623
77136485100631157329514617742467055842668657596018158436664428
32284556880313114548151539190975398485496645576513465858582712
33640116622195618817344953167410268890832176466302030669977040
86253407660915950227913793680983693063756028138566463587737515
58775213460225796579846583334007349358624342339332981334571237
88880928310334876026136017595081560917946402687100524365210998
08635521420142429034340685609365732310793421940318644139181012
38151056509267393515760392842472501391594073463001521843811073
76702171102630750469573346789782186690664846982834660741296739
58017977916836098347224322419528453525646818682403695695661928
25555323558078061997527689983848863374786789331581565252059172
61433942460098614325923316758337107036262555453185205416611714
88582295085815896143375944632775543805183809213012188363271022
31407332201109740102580216469298331766920619646083790732807627
36061442808517156500628972850868896422679964719258292405858953
07506745783853655618785595896857562256923489147469228109139156
19834754117648358035814128670294158565669942087736286390942241
54722601500447133063011307204270428890504214262819377191859457
43022021472011884863459131908337523074769660105474239288710631
18783026036381319039052008252072057933666712918946233312793697
09407422418787204597097644430924278218773832025749008082433007
49916986982395611258111276078639003552217378466905677073440744
94145266662103839812840216303448476913957072355732716627098372
24522304679291974725911315742582406485833141540094327821304295
46350535740452099845122212642419035501784168245514125486375900
07779082539288247751653566899882749594405895102587985539527709
49351004954644542726561747839910718823868177121590423411939224
74897510790859480559450988056179637229284695542637822176251604
28008228845552540344494860195267115187092227766195753907211126
64615014061474423397476527347561996431185285861416781966834012
47304877101620067935299857588206536772743795633134954545266327
18723482339494825759821076401694316043456512117937935456463521
46302119772669498355892913235757618859497751663073421286386945
61642055255367673112981371825114946494636630737592192130568235
61667776093739425742883930712609962163464088038826569132032160
69263720618308594298797368458427649178484311547207790040169259
56941192735535110259912654460393662889217435813332000837171052
41171504606883543418862024047552177055263424469501298905901938
15824593863369410502481516667981368915666834119771347509438990
48871267944689018938504750500112052257424555556257505602132303
87910337983950333245020653238989115507013882956277763880795687
21085719649389314265671310596627542214460598805893960060360422
69214014020965192942504886702979833963532794604531423755422678
81989197481789780678955093763193658603690898474826976906544473
97801745572036792998179602304178585262679727128346578949838364
2350667978127819110846700.


Comentarios

Entradas populares de este blog

Análisis de conexiones TIME_WAIT

Agregar un usuario a un grupo secundario

Pluging de HAProxy para Collectd.