For et stykke tid siden sad jeg og hørte et ret sjov foredrag af Randall Munroe, skaberen af xkcd.com en ret nørdet men sjov tegneserie. På et tidspunkt i foredraget taler han om Project Euler, om hvordan han brugte det til at lære python, det gjorde mig nysgerrig, så jeg oprettede en bruger derinde. Project Euler er en side med indtil videre 298 problemer, der bedst kan løses ved at programmere et program. Indtil videre har jeg løst 17 af dem, hvilke giver en sølle 6%. Hvis man har en bruger på siden, så kan man følge med i min fremskridt her: andreasjoensen. Jeg konkurrerer lidt med Dennis, men må desværre konstatere at han har løst 23, seks mere end mig.
I dag løste jeg problem 33 som havde titlen: “Discover all the fractions with an unorthodox cancelling method.”
Den går ud på at finde brøker hvor, hvis en af cifrene i både tælleren og nævneren er ens, så er det lig med den brøk hvor det ciffer er fjernet, fx: 49/98 = 4/8. Betingelsen er at både tælleren og nævneren er på to cifre og brøken er mindre end 1. Desuden tæller brøker hvor tælleren og nævneren kan deles med 10 ikke med, da de er lidt for oplagte, som i: 30/50 = 3/5. Alle disse tal skal så ganges sammen og den mindste fælles nævner for det tal findes.
Herunder er resultatet af min kode skrevet i Java:
double res = 1.0;
for (int num1 = 11; num1 < 100; num1++) {
for (int den1 = num1 + 1; den1 < 100; den1++) {
if (den1 % 10 == 0)
continue;
int num2 = 0, den2 = 0;
if (num1 / 10 == den1 / 10) {
num2 = num1 % 10;
den2 = den1 % 10;
} else if (num1 / 10 == den1 % 10) {
num2 = num1 % 10;
den2 = den1 / 10;
} else if (num1 % 10 == den1 / 10) {
num2 = num1 / 10;
den2 = den1 % 10;
} else if (num1 % 10 == den1 % 10) {
num2 = num1 / 10;
den2 = den1 / 10;
}
double fac1 = (double) num1 / den1;
double fac2 = (double) num2 / den2;
if (fac1 == fac2) {
res *= fac1;
System.out.println(num1 + "/" + den1 + " = " + num2 + "/" + den2);
}
}
}
System.out.println(res);
Udførselstiden er på 0,66ms.
Ideen er at jeg har to løkker der gennemløber fra 11 op til 99 på både tælleren og nævneren. Jeg søger dog for at løkken for tælleren starter ved en plus det for tælleren, pga betingelsen om at være under en.
Dernæst tjekker jeg om nævneren er deligt med 10, for at undgå de trivielle tilfælde, men også undgå at dele med nul.
Så tjekkes efter cifre fra tælleren og nævneren der er lig hinanden. Det gøres vha. fire if-sætninger, pga disse fire tilfælde: ax/bx, xa/bx, ax/xb og xa/xb. Hvis de er det, så laves en ny brøk bare uden det ciffer der er ens. Det viste sig så senere, ved at se på problem forumet på euler, at man kun kan opnår de tilfælde ved mønsteret: ax/xb. Udførselstiden bliver så til 0,27ms hvis man kun undersøger for det ene tilfælde.
Hvis de to brøker, det oprindelige og det uden det fælles ciffer, er lig med hinanden, så ganges det med de andre man har fundet. Det tal printes så til sidst og ud fra det, fandt jeg det mindste fælles nævner i hånden (hvilke er tilladt, problemerne er lavet sådan at de ikke kan løses udelukkende i hånden).
Resultatet blev:
16/64 = 1/4
19/95 = 1/5
26/65 = 2/5
49/98 = 4/8
Produktet af brøkerne: 0,01
Hvilke giver 100 som svar, da 1/100 = 0,01 og brøken kan ikke reduceres ydeligere.
).