Den store project euler tråden

[zotbar1234]

Matlab greier ikke omtrent de siste 500 talla i den rekka - så hvordan skal man løse den ellers?

 

I tillegg greier den ikke fibonacci opp til 1000 tall, bare opp til et par hundre.

 

Man trenger ingen av delene.

[Deneb]

Hint?

Endret 5. januar 2010 av slux

[zotbar1234]

Hint?

 

Til #25: n-te Fibonacci-tall kan regnes ut uten å måtte regne ut alle de foregående.

 

Til #48: Man trenger bare de 10 minst signifikante siffre i svaret, og kan utnytte det under beregningen.

[Deneb]

Skal jobbe litt med #25. #48 å finne de ti siste sifrene i "inf" er umulig, om det var det du tenkte på :/ takk for tips dog!

[zotbar1234]

#48 å finne de ti siste sifrene i "inf" er umulig, om det var det du tenkte på

 

Du skal ikke regne fram til matlab får inf, det er hele hintet. Du trenger ikke å regne ut hele 1000^1000, nemlig, bare deler av den.

[Deneb]

Hmm, tallene fra 1-100 går ihvertfall mot bare nuller i de siste sifrene, tipper dette gjelder for resten av rekken også, desverre er dette feil.. hmm. Er jeg på villspor?

[Senyor de la guerra]

Ingen bør bruteforce problem nr. 5 Har stått på i hele natt uten resultater.

[steingrim]

Ingen bør bruteforce problem nr. 5 Har stått på i hele natt uten resultater.

Høh. Jeg sjekket min bruteforce løsning på nr 5, den tok 33 sekunder i Python. Sikker på du ikke har en feil et sted?

 

Edit: Jada zotbar1234, det er altfor lenge, jeg vet det

Endret 6. januar 2010 av steingrim

[Senyor de la guerra]

Kode:

 

 

clear
j = 20;
D = 1;

while D != 0

	for i = 1:20
			A(i) = mod(j, i);
	end

	D = sum(A);
	j = j + 20;

end

disp(j-20)

 

 

 

Ganske sikker på den stemmer, da jeg får rett svar for tall opptil 10.

Endret 6. januar 2010 av runesole

[GeirGrusom]

Ingen bør bruteforce problem nr. 5 Har stått på i hele natt uten resultater.

Evig loop?

Brute force er alltid greit, fordi da slipper en å tenke/google så mye.

[steingrim]

Vel, det finnes brute force, også finnes det raskere brute force zotbar1234 ga et tips litt lenger opp, og et annet tips er: hvis tallet ikke er delelig på 3, trenger du da sjekke 4-20?

[GeirGrusom]

Vel, det finnes brute force, også finnes det raskere brute force zotbar1234 ga et tips litt lenger opp, og et annet tips er: hvis tallet ikke er delelig på 3, trenger du da sjekke 4-20?

Optimalisering av brute-force algoritmer er for pyser ^^

[Senyor de la guerra]

Enig

[steingrim]

Nei altså, det er samma for meg. Jeg har løst oppgaven jeg

[zotbar1234]

Hmm, tallene fra 1-100 går ihvertfall mot bare nuller i de siste sifrene, tipper dette gjelder for resten av rekken også, desverre er dette feil.. hmm. Er jeg på villspor?

 

La meg gjenta hintet.

 

 

 

Du er interessert kun i de siste 10 siffrene i alle ledd i beregningen. Dvs. alle utregninger i #48 kan gjøres modulo 10^10. Og det er ikke slik at du faktisk må opphøye 983 i 983-e potens for så å ta modulo 10^10.

 

 

[zotbar1234]

Ingen bør bruteforce problem nr. 5 Har stått på i hele natt uten resultater.

 

La meg gjenta et meget viktig poeng med projecteuler-oppgaver:

 

1) Bruce-force er så å si *aldri* løsningen. Hvis beregningsfasen tar mer enn 10-15 sekunder, gjør man noe veldig veldig galt.

2) En rekke av problemene kan ikke løses ved rå regnekraft (vi snakker om mange år med beregninger). Den eneste måten å angripe oppgaven er å finne på en Smart Framgangsmåte[tm], ikke teste alle mulige kandidatløsninger.

3) #5 løses med penn og papir. Man trenger *ikke* en datamaskin til det. Stikkordet her er å finne ut hva man kan si om et tall som er delelig med f.eks. 2, 6 og 8 (det er ikke 2*6*8, slik oppgaven er stilt).

Endret 6. januar 2010 av zotbar1234

[Senyor de la guerra]

Nei, huff da må jeg tenke mer enn jeg allerede gjør.

Har mekket en kode for problem 14 nå, der jeg sliter med det samme skvipet:

 

 

 

makslengde = 0;
nmax = 0;

for n = 1:1000000

teller = n;
A = [];
A(1) = n;
k = 2;

while n > 1

	if mod(n, 2) == 1
		n = 3*n + 1;
		A(k) = n;
		k = k + 1;
	end

	if mod(n, 2) == 0
		n = n/2;
		A(k) = n;
		k = k + 1;
	end

end

lengde = length(A);

if makslengde < lengde
	makslengde = lengde;
	nmax = teller;
end

n = teller;

end

makslengde
nmax

 

 

 

Estimert tid er omtrent 300 minutter med min kode (kjørt i octave). Har ikke tålmodighet til slikt skvip, må jo en syk IQ til for å løse disse problemene da

Endret 6. januar 2010 av runesole

[Jann - Ove]

Lær deg et nytt og bedre språk.

 

Du kan allerede programflyt og struktur - da er det kun bagateller som må inn for å kunne bruke et annet språk. Python er f.eks kjapt på slik bruteforcing.

 

Den kodesnippen der kan forøvrig optimiserers med en elseif. Mod() er typisk en krevende funksjon, og du kjører den unødvendig to ganger på samtlige tall som går gjennom løkken. Det fins vel også mer effektive måter å sjekke om et tall er odde eller partall.

[Senyor de la guerra]

@Jann_Ove: Takk, det korter tiden ned til ca 1,5 timer. Vet ikke hvordan jeg skal gå frem for å lære meg python.

 

 

Føkk Matlab

Endret 6. januar 2010 av runesole

[zotbar1234]

@Jann_Ove: Takk, det korter tiden ned til ca 1,5 timer. Vet ikke hvordan jeg skal gå frem for å lære meg python.

 

pythonchallenge er muligens litt drøyt for å lære seg python, men man har "dive into python" og masse gratis ressurser om/rundt språket. Du kan uansett bruke det språket du er mest komfortabel med. Skjønt at Java er litt køddent å lese inn matriser med (kontra f.eks. Python eller Perl), men det er aldri en avgrensende faktor.

 

 

 

Hva #14 angår, så har jeg dessverre ikke funnet ut en smart løsning. Men en tur innom mathworld og google for å lese litt om Collatz problem er jo et must. Bruce-force løsningen er innlysende: regn ut lengden av sykelen for et tall x, dersom lengden er større enn beste resultat hittil, så har vi en ny verdi. Men det er lett å se at for et partall n, sykellengden(n) = sykellengden(n/2) + 1. Kan dette utnyttes på en eller annen måte? Spørsmålet er ikke retorisk -- jeg fikk en ca. 60x forbedring i tiden brukt på #14 etter å ha utnyttet akkurat den biten. Du gjør noe av det samme med å fylle ut A, men du utnytter det ikke. (Jeg må dessverre innrømme at #14 er en av de oppgavene hvor Python-løsningen min ikke kom under 1 sekund (2.4s ser ut til være tiden på en c2d E8400))

 

Jeg tror også at måten du regner sykellengdene på er fryktelig kostbar -- du lager en dynamisk array og ikke bruker resultatene du har regnet til noe. Vil ikke det være mye raskere å la være å fylle A? Bruce-force C-løsning uten en slik array bruker ca 5 sekunder (jeg har ikke testet ideen min med caching, men det er klart verdt å prøve i C i tillegg til Python).

 

 

 

 

Føkk Matlab

 

Matlab er ikke problemet

Endret 6. januar 2010 av zotbar1234