Den store project euler tråden

[Deneb]

Fant ingen annen Project Euler tråd - så derfor lager jeg det!

 

Håper det kan bli en liten tråd hvor man kan tipse hverandre om de forskjellige problemene!

 

Driver på med problem 48 - fant ingen annen måte enn å bruteforce problemet - men da gir matlab ut tallet som inf... Hva kan man gjøre da?

(Hjelper heller ikke å konvertere tallet i string og bare be om de 10 siste talla i stringen.. )

 

Noen lure tips?

Endret 3. januar 2010 av slux

[OeO]

For å unngå infinity, kan du ikke plukke ut de siste 10 sifrene av hvert tall, og legge til det?

 

Edit: Hvorfor hjelper ikke dette? Klarer den ikke plukke ut, eller klarer ikke matlab 1000^1000 med presisjon?

Endret 3. januar 2010 av oysteina

[Deneb]

Hmm, kunne ha plukket ut de 10 siste sifrene i hvert tall - der sa du noe. Men ser ut som at summen av hele greia blir for stor for matlab - selv om jeg aldri displayer tallet.

 

edit: Ser ut som at selv 1000^1000 blir inf..

 

Edit2: strengt tatt kan jeg vel bare unngå tall som 1000 men det vil jo ikke utgjøre store forskjellen..

Endret 3. januar 2010 av slux

[Deneb]

Siden matlab ironisk nok ikke takler store tall har jeg gått over til problem nr 20, men holder på å bli gal da jeg ikke finner noen måte å finne tverrsummen av et tall på. Latterlig at det ikke finnes noen innebygd funksjon på dette?

 

Mitt forsøk:

 

 

 

p=num2str(tallet)

v=1:1:length(p)

for i=1:length(p)

v(i)=str2num(p(i))

end

sum(v)

 

 

men neida.

Endret 3. januar 2010 av slux

[snippsat]

Ser litt på euler 48 med python.

1000^1000 er ikke noe problem da må man ha med et par nuller til.

Da får minnet kjørt seg.

 

>>> #** == ^ eller man kan bruke pow(n,n)
>>> a = 1000 ** 1000
>>> b = str(a)
>>> #Gjør om til string og teller antall nuller
>>> len(b)
3001
>>> #Trekke ut de 10 siste siffrere
>>> b[-10:]
'0000000000'

>>> 1**1 + 2**2 + 3**3
32
>>> 1**1 + 2**2 + 3**3 +4**4 + 5**5
3413
>>> #Kjøre en loop 1-1001,en variable number som fanger opp n ** n

>>> number = 0
>>> for n in xrange(1,1001):
	number += n ** n
	print str(number)[-10:] #printer 10 siste tall 1^1 til 1000^1000

 

number = 0
for n in xrange(1,1001):	
number += n ** n	
print str(number)[-10:]
'''-->output
9110846700
'''

 

Med tid,ikke langt tid på dette.

import datetime
s = datetime.datetime.now()

number = 0
for e in xrange(1,1001):	
number += e ** e	
print str(number)[-10:]

e = datetime.datetime.now()
print "Time elapsed: ", (e - s)
'''-->output
9110846700
Time elapsed:  0:00:00.047000
'''

[steingrim]

Lenge siden jeg puslet med euler, så jeg husker ikke noe av hva jeg tenkte, men siden vi er inne på problem 48, her er hva jeg gjorde i python, som man ser så er den "rask nok" med en brute-force løsning

 

$ time python problem48.py 
<svaret har jeg tatt bort!>

real	0m0.109s
user	0m0.096s
sys	0m0.010s

 

 

 

$ cat problem48.py 
#!/usr/bin/env python

print str(sum( (i**i for i in xrange(1, 1000+1)) ))[-10:]

 

 

 

En-linjers python-løsninger er alltid gøy

Endret 3. januar 2010 av steingrim

[GeirGrusom]

Fikk ikke til noen en-linjer i C#, men her er min løsning:

Klikk for å se/fjerne innholdet nedenfor

[color="#0000FF"]using[/color] System;
[color="#0000FF"]using[/color] System.Numerics;

[color="#0000FF"]namespace[/color] ProjectEuler
{
   [color="#0000FF"]class[/color] Program
   {
       [color="#0000FF"]static[/color] [color="#0000FF"]void[/color] Main([color="#0000FF"]string[/color][] args)
       {
           BigInteger val = 0;
           [color="#0000FF"]for[/color] (var i = 1; i < 1001; i++)
               val += BigInteger.Pow(i, i);
           Console.WriteLine((val % 10000000000).ToString());
       }
   }
}

edit: 0.067 s tok det.

Endret 3. januar 2010 av GeirGrusom

[Deneb]

Takk for svar folks! ser ut som det er matlab som rett og slett er dårlig i forhold til andre språk ja - ganske latterlig da et som skal være spesialisert innenfor matematikk og vitenskap ikke takler store tall. Sitter å lurer på om jeg skal lære meg et annet språk da - men vegrer meg litt da det ikke ser så ufattelig logisk ut

[zotbar1234]

Takk for svar folks! ser ut som det er matlab som rett og slett er dårlig i forhold til andre språk ja - ganske latterlig da et som skal være spesialisert innenfor matematikk og vitenskap ikke takler store tall.

 

Jeg ble litt overrasket da jeg fant ut hvor kjapp bignum-håndteringen er i Python (lenge siden jeg løste 48) -- i flere av oppgavene som ligner på #48 kan man bare regne med bignums uten store problemer. En opplagt optimalisering er å gjøre eksponensieringen selv og betrakte kun de siste 10 siffre. Jeg tittet litt raskt på oppgavelisten (gud, det er *mange* oppgaver med "digits" i beskrivelsen ), og f.eks. #97 lar seg ikke løse slik steingrim foreslo innen rimelig[1] tid. Ah, der var den -- #104 lar seg ikke løse "rett frem" selv med rask bignum-aritmetikk og man må gjøre noe lurt.

 

[1] "rimelig tid" er selvsagt ikke 1 minutt, men 1 sekund. De aller fleste oppgaver lar seg løse innen 1s uansett språk på en moderne cpu.

Endret 4. januar 2010 av zotbar1234

[GeirGrusom]

Ja, jeg ble også imponert over hvor rask Python var på dette.

Endret 4. januar 2010 av GeirGrusom

[Deneb]

+1

 

Tror jeg holder meg til Matlab intill videre, men det innebærer også at jeg må holde meg unna digits oppgaver til jeg lærer meg det. Litt irriterende da jeg strengt tatt kan utføre hovedtingen i oppgaven, bare kke det de vil gjøre for å forenkle det. Menmen nuvel. Skrella av ytterligere 4 problem tidligere. Hvor mange problem har dere løst totalt folkens? Virker som det ikke er så rent lite?

[zotbar1234]

Hvor mange problem har dere løst totalt folkens? Virker som det ikke er så rent lite?

 

Ikke engang halvparten, dessverre. Jeg liker litt for dårlig matematikkoppgaver, og med unntaket av 81-83, er det mer matematiske enn IT-problemer.

 

Har noen et forslag til en side lik projecteuler.net, bare vinklet mye mer mot databehandling?

Endret 4. januar 2010 av zotbar1234

[steingrim]

Hvor mange problem har dere løst totalt folkens? Virker som det ikke er så rent lite?

Ikke særlig mange, usle 46.

 

Har noen et forslag til en side lik projecteuler.net, bare vinklet mye mer mot databehandling?

The Python Challenge er jo fin, til tider litt kryptisk, man trenger slettes ikke bruke Python for å løse oppgavene. Dessverre ser det ut til at jeg har mista alle løsningene mine. URK!

[Jassogitt]

Har løst 19 oppgaver (også #48 og #20). Holder på med #59 nå, i Perl, som jeg ikke kan så godt.

[zotbar1234]

The Python Challenge er jo fin, til tider litt kryptisk, man trenger slettes ikke bruke Python for å løse oppgavene.

 

Bortsett fra "import this" og pickle-oppgavene Men det er bare 33 puzzles der.

 

Dessverre ser det ut til at jeg har mista alle løsningene mine. URK!

 

Backup er lurt, vettu

[Senyor de la guerra]

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

[zotbar1234]

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

 

For hvilken oppgave?

[Senyor de la guerra]

48

[zotbar1234]

48

 

"Find the last ten digits of the series, 1^(1) + 2^(2) + 3^(3) + ... + 1000^(1000)" -- man skal skrive de siste 10 siffrene av denne rekken. Ingen input, og de minste signifikante 10 siffrene (som output)

[Senyor de la guerra]

Altså så skal det bli:

 

ans = 0405071317