Gå til innhold

Den store project euler tråden

Deneb

Av Deneb
i Programmering og webutvikling

Anbefalte innlegg

Videoannonse

Videoannonse
Annonse
Deneb

Deneb

Skrevet
  • Forfatter
Skrevet

 

>> type euler14
euler14 is the user-defined function defined from: C:\***\euler14.m

makslengde = 0;
nmax = 0;

for n = 1:1000000

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

	while n > 1

			if round(n/2) != n/2
					n = 3*n + 1;
			else
					n = n/2;
			end

			A(k) = n;
			k = k + 1;

	end

	lengde = length(A);

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

	n = teller;

end

makslengde
nmax
>>

 

 

 

Min kode (som sikkert heller ikke er optimalisert):

 

function answer=Problem14

b=1000000;

p=0;

tic

for j=0:999999

m=1000000-j;

i=0;

n=m;

while n>1

if n/2==floor(n/2)

n=n/2;

i=i+1;

else

n=3*n+1;

i=i+1;

end

end

if i>p

p=i;

b=m;

 

end

 

end

answer=b;

toc

end

 

 

Veldig brute force...

Lenke til kommentar
zotbar1234

zotbar1234

Skrevet
Skrevet (endret)
Veldig brute force...

 

Ah, the power of brute force (enhanced by memoization)

 

 

 

def collatz(n, cache):
"""Calculate termination time for n."""

results = []
start = 1
while n != 1:
	if n < len(cache) and cache[n] != -1:
		start = cache[n]
		break

	results.append(n)
	if n % 2 == 0:
		n = n/2
	else:
		n = 3*n + 1

# update the cache from results
for x in results[::-1]:
	start += 1
	if x < len(cache):
		cache[x] = start

return start
# end collatz

def solve(limit):
# cache for previously calculated collatz seq values.
cache = [-1]*limit
max_so_far = 0
max_number = None
for i in xrange(1, limit):
	current = collatz(i, cache)
	if current > max_so_far:
		max_so_far = current
		max_number = i
return max_number
# end solve

 

Det er nokså meningsløst å regne ut sykellengden av for de samme tallene om og om igjen. Selv men en cache som ikke dekker alle tidligere beregninger, så vil denne enkle teknikken gi ca. 60x hastighetsforbedring.

 

 

Endret av zotbar1234
Lenke til kommentar
Senyor de la guerra

Senyor de la guerra

Skrevet
Skrevet

Mmmmmm....... pen kode :thumbs:

Endelig noe MATLAB kan brukes til.

 

28:

 

 

clear


n = input('');  %% 1001 for å løse euler28

k = 3;
A = ones(n);
l = length(A);
m = ceil(l/2);
teller = 2;



	i = 1;

	hn = teller + 1;
	vn = hn + 2*i;
	vo = vn + 2*i;
	ho = vo + 2*i;


	A(m, m+i) = teller;
	A(m+i, m+i:-1:m-i) = hn:vn;
	A(m+i:-1:m-1, m-i) = vn:vo;
	A(m-i, m-i:m+i) = vo:ho;


for i = 2:l-m

	teller = ho + 1;

	hn = teller + k;
	vn = hn + 2*i;
	vo = vn + 2*i;
	ho = vo + 2*i;

	A(m-i+1:m+i, m+i) = teller:hn;
	A(m+i, m+i:-1:m-i) = hn:vn;
	A(m+i:-1:m-i, m-i) = vn:vo;
	A(m-i, m-i:m+i) = vo:ho;

	k = k + 2;

end


summen = -1;	

for i = 1:length(A)
summen = summen + A(i,i) + A(i, length(A)-i+1);
end

summen

 

 

 

 

19:

 

 

clear

ukedag = 1-1;
ukedag = ukedag + 365;	%% pga 2001
ukedag = mod(ukedag, 7);  %% pga 2001
dagnr = 0;
teller = 0;
skudd = false;

for aar = 1901:2000

if mod(aar, 4) == 0
skudd = true;
	if mod(aar, 100) == 0
		if mod(aar, 400) != 0
			skudd = false;
		end
	end
else
skudd = false;
end


for maaned = 1:12

	if maaned == 1
		dager = 31;
	elseif maaned == 2
		if skudd == false
			dager = 28;
		else dager = 29;
		end
	elseif maaned == 3
		dager = 31;
	elseif maaned == 4
		dager = 30;
	elseif maaned == 5
		dager = 31;
	elseif maaned == 6
		dager = 30;
	elseif maaned == 7
		dager = 31;
	elseif maaned == 8
		dager = 31;
	elseif maaned == 9
		dager = 30;
	elseif maaned == 10
		dager = 31;
	elseif maaned == 11
		dager = 30;
	else dager = 31;
	end



	for dag = 1:dager
		dagnr = dagnr + 1;
		ukedag = ukedag + 1;
		if ukedag == 8
			ukedag = 1;
		end

		if (ukedag == 7 && dag == 1)
			teller = teller + 1;
		end

	end





end



end

teller

 

 

Lenke til kommentar
zotbar1234

zotbar1234

Skrevet
Skrevet
28:

<masse matlabkode>

 

Hvorfor så komplisert?

 

 

 

Den kritiske observasjonen er at tall på diagonalene er på formen (2n+1)^2, (2n+1)^2 - 2n, (2n+1)^2 - 4n og (2n+1)^2 - 6n for n = [0, ... grid size].

 

Koden blir da:

 

def solve():
grid_size = 1001
limit = (grid_size-1)/2
sum1 = 1 # the 0'th term, so to say
sum2 = 0 # not to count the center number twice
for n in range(1, limit + 1):
	sum1 += (2*n+1)**2 + (2*n + 1)**2 - 4*n
	sum2 += (2*n+1)**2 - 2*n + (2*n+1)**2 - 6*n

return sum1+sum2
# end solve

 

 

 

19: (...)

 

Ja, denne illustrerer vel at et kalenderbibliotek ville ha vært veldig nyttig :D

Lenke til kommentar
Deneb

Deneb

Skrevet
  • Forfatter
Skrevet

Quoter denne her:

 

en funksjon/måte å konvertere flersifrede tall, feks 1881 til en vektor ala [1 8 8 1].

 

Her er et forslag til Matlab kode for å sjekke om et tall er et palindrom. Det brukes ikke strenger. Jeg har skrevet det i gnu octave (mener å huske at fix heter trunc i Matlab):

 

function res=palindrome(n)
 res = false;
 i = 1;
 d = ceil(log10(n));
 v = zeros(d,1);
 while (n > 0)
v(i,1) = rem(n,10);
n = fix(n/10);
i = i+1;
 end

 if flipud (v) == v 
res = true;
 end

 

 

Fungerer veldig fint! =)

 

Men ironisk nok fant jeg svaret på problem 4 bare v.h.a en vanlig kalkulator ;)

Lenke til kommentar
snippsat

snippsat

Skrevet
Skrevet
Slik: 12345678910111213........9999991000000

import sys
for i in range(1,1000000):
sys.stdout.write(str(i))

1000000.rar

 

Ja, denne illustrerer vel at et kalenderbibliotek ville ha vært veldig nyttig

Ja, kan hjelpe bra til som du vet,viser litt av dette i python.

 

>>> import datetime
>>> dir(datetime)
['MAXYEAR', 'MINYEAR', '__doc__', '__name__', '__package__', 'date', 'datetime', 'datetime_CAPI', 'time', 'timedelta', 'tzinfo']
>>> #Bruker metode date og timedelta
>>> print datetime.date.today()
2010-01-11
>>>
>>> #Finner nå dager side 1 Jan 1901 
>>> one_day = datetime.timedelta(days=1)
>>> long_time_ago = datetime.date(1901, 1, 01)
>>> print to_day - long_time_ago
39822 days, 0:00:00

Vi ser fort at kalenderbibliotek kan være til mye hjelp.

Trenger nå og finne finne søndager som faller på første.

Vi kan bruke en "boolean operation" som "weekday() == 6 and day() == 1"

Hvor begge verdier må være True.

 

#python | euler 19
import datetime
date = datetime.date(1901, 1, 1)
days = 0
while date.year < 2001:
 if (date.weekday() == 6) and (date.day == 1):
days += 1  
 date += datetime.timedelta(days=1)
print 'Sundays that felled on the first month during the twentieth century was %s' % (days)

Python har flere sterke 3-parts bibliotek for kalender utregninger dateutil, mxDateTime eller søke PyPi

 

Primtall er som kjent viktig i mange av euler oppgavene.

Gjøre for en stund siden en del tester for og se hvor rask python kan være til og finne primtal opp til et satt tall(et rimlig høyt mål på 100 millioner prime_tall)

 

Testet forskjellige algoritmer som Sieve_of_Eratosthenes, Sieve_of_Atkin

Brukte i tillegg Psyco for og få opp farten(psyco_speed) :ohmy:

Dette var det beste jeg fikk til,prøv gjerne i andre språk for de som mener python er treg med 7,92 sek ;)

 

import math
import time
import psyco
psyco.full()

start = time.clock()
def sieveOfErat(end):
if end < 2: return []	
lng = ((end/2)-1+end%2)	
sieve = [True]*(lng+1)	
for i in range(int(math.sqrt(end)) >> 1):		
	if not sieve[i]: continue		
	for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):
		sieve[j] = False	
primes = [2]	 
primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])	
pri = primes[-1]
return pri
print sieveOfErat(100000000)
end = time.clock()
print '100000000 prime_numbers with python in %.3f seconds' % (end - start)  
'''
My output
99999989
100000000 prime_numbers with python in 7.923 seconds
'''

Lenke til kommentar
zotbar1234

zotbar1234

Skrevet
Skrevet (endret)
Primtall er som kjent viktig i mange av euler oppgavene.

Gjøre for en stund siden en del tester for og se hvor rask python kan være til og finne primtal opp til et satt tall(et rimlig høyt mål på 100 millioner prime_tall)

 

100'000'000 primtall med sieve er uaktuelt pga. minnebruk. En sieve med 50M primtall bruker 400+MB med minne her. Må nesten se an oppgaven -- kan være raskere å gå gjennom alle oddetall og teste hvorvidt de er primtall (3 kandidater med Miller-Rabin for tall < 2^32).

 

Ellers så ser det ut som at det å implementere en variant av ContinuedFraction til Mathematica kan være på sin plass.

 

Brukte i tillegg Psyco for og få opp farten(psyco_speed)

 

psyco er veldig fint, helt fram til man sjekker ut løsningen sin på en 64-bits platform :D

Endret av zotbar1234
Lenke til kommentar
zotbar1234

zotbar1234

Skrevet
Skrevet
zotbar: mener å huske at 100'000'000 primtall med sieve funket flott i Ruby for noen år siden. Gikk ikke superfort, men tok ikke mange minutter heller.

 

Hvis vi tar sieve på 64 bits platform -- hver celle i listen er på størrelse med en peker, 8 bytes. 100M*8 er 800MB bare for sieve. Litt mye, hvis det er firefox og denslags som rusler rolig ved siden av :)

Lenke til kommentar
zotbar1234

zotbar1234

Skrevet
Skrevet
Python er vel ikke rette språk dersom du er gjerrig på minne eller CPU ^^

Som sagt: minne er til for å brukes!

 

Tja, en sil i CPython vil ta like stor plass som en sil med longs i en typisk C-implementasjon (det ved siden av det er meningsløst å snakk om språk som er gjerrige på minne/CPU).

Lenke til kommentar

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
Gå til emneliste

  • Hvem er aktive   0 medlemmer

    • Ingen innloggede medlemmer aktive
×
×
  • Opprett ny...