Den store project euler tråden

[aspic]

Melder meg inn her eg. Har kun klart 15 stk eller noko, men har håp om å starte litt opp igjen, medan det framleis er ferie.

[Jann - Ove]

Ruby funker også flott til Project Euler. Forskjellene mellom forskjellige språk blir fort ganske liten når det er rene talloperasjoner som begrenser ytelsen.

 

Det er en stund siden jeg holdt på med Euler: "Last Solved: 26 May 2007 11:35 pm" - har løst 19 totalt, og det har vel kommet til godt over hundre oppgaver siden sist jeg holdt på.

 

Burde egentlig begynt igjen. Selv om det er matteoppgaver så er logikk og strategi ved valg av løsning viktigere enn mattekunnskaper.

[zotbar1234]

Altså så skal det bli:

 

ans = 0405071317

 

Ikke på oppgave 48.

[GeirGrusom]

Det starter med 9 ^^ Det ligger jo allerede tre fungerende løsninger i to språk her.

[Deneb]

Altså så skal det bli:

 

ans = 0405071317

 

 

Brukte du matlab på dette?

 

Lurer litt på Problem 25, dette må da kunne løses veldig lett uten bruk av brute force?

[snippsat]

Kan du forklare hva som skal bli output og hva som skal inn?

Altså så skal det bli:

 

ans = 0405071317

Nå har jeg forklart dette i post 5

Der er også output,kansje se litt nøyere på hva som er postet.

[zotbar1234]

Lurer litt på Problem 25, dette må da kunne løses veldig lett uten bruk av brute force?

 

Jepp. Det finnes en formel for det n-te Fibonacci-tallet. Men 25 er ganske enkel og kan løses ved rå regnekraft og.

[Deneb]

Ikke slik jeg gjør det med matlabben ihvertfall, den stopper på et par hundre siffer, deretter blir alt tresifret.. ???

 

Syns jeg så en tendens ved at det tok 6 ledd før det gikk til 2 siffer, deretter 5 for hvert nye siffer derifra? Men er det selve tallet eller leddnummeret de er ute etter?

[zotbar1234]

Men er det selve tallet eller leddnummeret de er ute etter?

 

Det er nummeret i rekkefølgen. Lime inn 1000 siffre er litt pes

[Senyor de la guerra]

Huff, skulle gjøre problem nr. 5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

 

Min kode (MATLAB)

clear
j = 1;
D = 1;

while D != 0

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

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

end

disp(j-1)

 

.... men, octave bruker en evighet på å regne det ut

Noe tips til forbedring av koden?

Endret 5. januar 2010 av runesole

[zotbar1234]

Noe tips til forbedring av koden?

 

Ja -- dette er en av de virkelig få oppgavene hvor man ikke trenger en datamaskin. Kan (og bør) gjøres med papir og blyant. Tenk litt på hvilket tall man etterspør og hvilke egenskaper (delelighet, opplagt) det tallet skal ha.

 

Tips til programmet -- hvis du vet at resten etter divisjon med 2 er forskjellig fra 0, er det noe poeng i å teste f.eks. 6, 8, 12, 16 ?

Endret 5. januar 2010 av zotbar1234

[aspic]

Tråden her gir meg inntrykk av at matlab ikkje er skikkeleg eigna til slike oppgåver, dvs. begrensingar og slikt? Kvifor ikkje prøve eit lettfatteleg programmeringsspråk som f.eks. Python istadenfor?

[snippsat]

Lurer litt på Problem 25, dette må da kunne løses veldig lett uten bruk av brute force?

Ja, men brute force går veldig fort med kun 1000 sifferer.

Kjøre en vanlig(ikke opptimalisert fibonacci sekvens) i en infinity loop og bryte ut ved 1000 siffere.

 

#Python
#Euler 25 
import time
start = time.clock()
def fib():
terms = 0
a, b = 0, 1	
while True:
	a, b = b, a + b	   
	terms += 1
	if len(str(a)) == 1000:
		break
end = time.clock()
print 'First fibonacci sequence that has 1000 digits is %sth terms time used %.3f seconds  ' % (terms,end - start)	
fib()
'''
My output-->
First fibonacci sequence that has 1000 digits is 4782th terms time used 0.695 seconds  
'''

[zotbar1234]

Tråden her gir meg inntrykk av at matlab ikkje er skikkeleg eigna til slike oppgåver, dvs. begrensingar og slikt?

 

Problemet ligger ikke i matlab

[Jann - Ove]

Nei. Men det er lettere å lære seg til god logikk og struktur i programmering for programløsning i et språk som oppfordrer til fin og lettlest kode.

 

Sitter programmeringsevnene godt er språket forholdsvis irrelevant, men hvis ikke kan man få hjelp av et mer pedagogisk programmeringsspråk.

[Senyor de la guerra]

Tråden her gir meg inntrykk av at matlab ikkje er skikkeleg eigna til slike oppgåver, dvs. begrensingar og slikt? Kvifor ikkje prøve eit lettfatteleg programmeringsspråk som f.eks. Python istadenfor?

Tja, har vel strengt tatt ikke tålmodighet til å lære meg et prog.språk på egenhånd.

Octave surrer og går forresten ennå, er det på tide å stoppe den?

 

Edit: Bruteforcer alle i intervallet: 1:20:tallet

Endret 5. januar 2010 av runesole

[Deneb]

Tråden her gir meg inntrykk av at matlab ikkje er skikkeleg eigna til slike oppgåver, dvs. begrensingar og slikt?

 

Problemet ligger ikke i matlab

 

Kan ikke du værsåsnill gi svaret på hvordan jeg displayer store tall i matlab da, siden du vet det?

 

Runesole - jeg også løste denne oppgaven ved å faktorisere, uten bruk av matlab altså.

[zotbar1234]

Octave surrer og går forresten ennå, er det på tide å stoppe den?

 

Mesteparten av alle oppgavene kan løses på under 1 sekund uansett språk. Så, ja, bruker du flere enn 10-15 sekunder på å regne, så gjør du noe feil

 

(Jeg skulle dog ønske at *løsningen* ble åpenbar på under 1 sekund).

[zotbar1234]

Problemet ligger ikke i matlab

 

Kan ikke du værsåsnill gi svaret på hvordan jeg displayer store tall i matlab da, siden du vet det?

 

Tja, nei, jeg vet ikke, kanskje bare søke?

 

Poenget mitt var at den soleklart vanskeligste biten er å finne ut hva man skal utnytte, ikke hvordan bignum-aritmetikk er implementert (eller ikke implementert). Jeg blir så å si alltid temmelig misunnelig, når jeg ser hvor mye skarpere andres løsninger er; men jeg kan ikke huske å ha blitt imponert av at en løsning er på 19 tegn i J, heller enn på 5 linjer i Python, eller å ha savnet en eller annen språkfeature i C/C++/Python (det er de jeg har brukt i mine løsninger). Mathematica har et par finurligheter, men de er *aldri* avgjørende.

 

Hverken 25 eller 48 krever bignum-aritmetikk, forresten.

Endret 5. januar 2010 av zotbar1234

[Deneb]

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, her er det ikke snakk om å vise store tall, men å regne med de.

 

I tillegg er det meget vanskelig å finne tverrsummen av tall, ja har søkt.

Endret 5. januar 2010 av slux