Den store project euler tråden

[Senyor de la guerra]

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

 

Knotete skrivemåte

 

Jeg tolker det slik:

- Jeg skal finne summen av alle de aktuelle leddene (som har en tallverdi under 4 000 000, og som samtidig er partall).

 

Men det kan vel også tolkes slik:

- Finn summen av alle de aktuelle leddene (som er partall), der summen blir under 4 000 000.

- Finn summen av alle de aktuelle leddene (som er partall), der det siste leddet er det 4 000 000 'te leddet i rekka.

- Finn summen av alle de aktulle leddene, der summen er ..... *tenke*

 

 

HVORDAN SKAL DET TOLKES?

[zotbar1234]

Jeg tolker det slik:

- Jeg skal finne summen av alle de aktuelle leddene (som har en tallverdi under 4 000 000, og som samtidig er partall).

 

Jepp.

 

Men det kan vel også tolkes slik:

- Finn summen av alle de aktuelle leddene (som er partall), der summen blir under 4 000 000.

 

Nei. For at da ville det ha stått "the sum of which does not exceed four million"

 

- Finn summen av alle de aktuelle leddene (som er partall), der det siste leddet er det 4 000 000 'te leddet i rekka.

 

Nei. "which" henviser jo til elementet i Fibonacci-sekvensen, ikke dets indeks. I oppgavene der det stilles krav til indeks står det typisk stavet ut eksplisitt.

 

HVORDAN SKAL DET TOLKES?

 

Finn summen av Fibonacci-tall F_i der

 

* F_i er et partall

* F_i <= 4'000'000.

Endret 16. januar 2010 av zotbar1234

[Senyor de la guerra]

Koden min kommer til gå en en flere timer lang loop for svaret

 

 

clear
verdi = 1;
summen = 0;
teller = 1;
verdi = 1;

while verdi < 4000000

if (round(verdi/2) == (verdi/2))
	summen = summen + verdi;
	verdi;
end

teller = teller + 1;
verdi = rfibonacci(teller);

end

summen

 

 

 

Hvordan forbedre denne?

Endret 16. januar 2010 av Senyor de la guerra

[Deneb]

Er det matlab?

[Senyor de la guerra]

Ja, rfibonacci er ikke en innebygd fn.

 

function rfib = rfibonacci(n)
 if (n < 2)
rfib = n;
 else
rfib = rfibonacci(n-1) + rfibonacci(n-2);
 end
end

Endret 16. januar 2010 av Senyor de la guerra

[Deneb]

Hvilket nummer er oppgava? Kan kopiere min kode på det.

[Senyor de la guerra]

2

[Deneb]

Hadde slettet problemet, her er et nytt jeg laget. Tok 0.00038 sekund.

 

function [ ret ] = fibonacci ()
%lager her litt startverdier for å få while løkken til å komme igang.
list=ones(1,3);
list(1)=1;
list(2)=2;
i=2;
l=1;  
summen=0   

while list(i-1)+list(i)<4000000 
 i=i+1;
 list(i)=(list(i-1))+(list(i-2)); %lager fibonaccirekka 
if list(i)./2==floor(list(i)./2) %summerer samtidig partall 
 summen=summen+list(i);
end
end

ret=summen+2 %tar ikke med første partallsleddet som er 2, så det må jeg plusse på selv

Endret 16. januar 2010 av slux

[Senyor de la guerra]

Slux: Genialt

Har fått for meg at bruteforce er løsningen på alt

[Senyor de la guerra]

Matlab surrer noe vilt når tall blir store

Kan jo ikke regne ut 100! ordentlig en gang.

 

Uansett (problem 25) :

 

 

clear

list = [1 2];
i = 2; 
summen = 2;
siffer = 0;

while siffer < 1000

i = i + 1;
list(i) = (list(i-1)) + (list(i-2));
	siffer = length(num2str(list(i)));

end

i + 1

 

 

 

Går i evig loop siden list(i) kommer ut som Inf

Endret 16. januar 2010 av Senyor de la guerra

[zotbar1234]

Ja, rfibonacci er ikke en innebygd fn.

 

function rfib = rfibonacci(n)
 if (n < 2)
rfib = n;
 else
rfib = rfibonacci(n-1) + rfibonacci(n-2);
 end
end

 

Holy fuck! Dobbelrekursiv Fibonacci-beregning? Veldig fint for matematikere, ubrukelig for ingeniører. Dette er Det Klassiske Eksempelet[tm] på eksponensiell rutine som kan gjøres om til å ha lineær (i n) antall addisjoner. Ikke gjør dette

[zotbar1234]

Matlab surrer noe vilt når tall blir store

Kan jo ikke regne ut 100! ordentlig en gang.

 

1) matlab er ikke problemet her

2) #25 kan løses uten å regne ut noen Fibonacci-tall eksplisitt (og uten eksplisitt iterasjon) (hint: hvordan regner man ut det n-te Fibonacci-tallet *uten* å regne alle de foregående?)

[Senyor de la guerra]

1) matlab er ikke problemet her

Jo, Matlab er problemet når den ikke en gang kan regne litt store fakultetsproblemer uten å surre det til:

 

fac = 1;

for i = 1:100
 fac = fac*i;
end

fac

 

Denne koden kan bare ikke mistolkes, men Matlab føkker det til likevel. Funker fint for små verdier, men med en gang intervallet blir for stort printer den kun ut svada...

 

2) #25 kan løses uten å regne ut noen Fibonacci-tall eksplisitt (og uten eksplisitt iterasjon) (hint: hvordan regner man ut det n-te Fibonacci-tallet *uten* å regne alle de foregående?)

Kan ikke regne ut noe n'te ledd hvis Matlab ikke har støtte for nok siffre.

Endret 16. januar 2010 av Senyor de la guerra

[kloffsk]

Slutt å grin over Matlab. Bruk C++/Java/Python/Haskell/osv og implementer oppgavene selv - SLIK DET ER MENT. Bruk av innebygde funksjoner i MATLAB, Mathematica og maple fjerner sjarmen.

Endret 16. januar 2010 av kloffsk

[kloffsk]

og btw:

http://www.thestudentroom.co.uk/showthread.php?t=626128

[zotbar1234]

1) matlab er ikke problemet her

Jo, Matlab er problemet når den ikke en gang kan regne litt store fakultetsproblemer uten å surre det til:

 

Matlab er ikke problemet her. Du trenger nemlig ikke å regne ut 100 fakultet for å løse #25. "Prøv-alle"-metoden krever bignum-aritmetikk, ja, men for det første kan man faktisk implementere bignum-addisjon selv, og for det andre er det lite poeng i det, når man har formelen for n-te Fibonacci-tallet (hint1: man kan bruke den for å finne ut nummeret på tallet i rekkefølgen; hint2: nei, man trenger overhodet ikke å regne ut selve Fibonacci-tallet, for å finne ut hvilket tall i rekkefølgen har 1000 siffer)

 

2) #25 kan løses uten å regne ut noen Fibonacci-tall eksplisitt (og uten eksplisitt iterasjon) (hint: hvordan regner man ut det n-te Fibonacci-tallet *uten* å regne alle de foregående?)

Kan ikke regne ut noe n'te ledd hvis Matlab ikke har støtte for nok siffre.

 

Matlab har støtte for nok siffre. Slutt å sutre og heller kom på en smartere løsning for #25. Det holder med vanlig IEEE double presisjon for å løse #25.

Endret 17. januar 2010 av zotbar1234

[Emancipate]

Er det noen som har løst 67? Jeg holder på nå, etter å ha løst 18 med brute-force.

[kloffsk]

Ja, bruk DP.

[Senyor de la guerra]

Aner ikke hva DP er.

 

Uansett:

[Emancipate]

Løste den enkelt i prinsippet, men jeg klarte ikke å debugge før jeg hadde fått lunsj. Uten mat og drikke kompilerer programmet ikke, osv...