Projekt Euler

Projekt Euler
Typ av webbplats	Problemlösningswebbplats för beräkningsmatematik
Skapad av	Colin Hughes
URL	projecteuler.net
Kommersiell	Nej
Registrering	Fri
Lanserades	5 oktober 2001

Project Euler (uppkallat efter Leonhard Euler ) är en webbplats tillägnad en serie beräkningsproblem som är avsedda att lösas med datorprogram. Projektet lockar akademiker och studenter som är intresserade av matematik och datorprogrammering . Sedan det skapades 2001 av Colin Hughes, har Project Euler vunnit uppmärksamhet och popularitet över hela världen. Den innehåller 800 problem den 30 maj 2022, med ett nytt till cirka varje vecka. Problem är av olika svårighetsgrad, men var och en är lösbar på mindre än en minuts CPU-tid med hjälp av en effektiv algoritm på en måttligt driven dator. Den 27 april 2021 har Project Euler mer än 1 000 000 användare som har löst minst ett problem, på över 100 olika programmeringsspråk.

Funktioner på webbplatsen

Ett forum specifikt för varje fråga kan visas efter att användaren har svarat korrekt på den givna frågan. Problem kan sorteras på ID, antal löst och svårighetsgrad. Deltagarna kan följa sina framsteg genom prestationsnivåer baserat på antalet lösta problem. En ny nivå nås för varje 25 lösta problem. Särskilda utmärkelser finns för att lösa speciella kombinationer av problem. Till exempel finns det ett pris för att lösa femtio primtalsproblem. En speciell "Eulerians"-nivå finns för att spåra prestationer baserat på de snabbaste femtio lösare av senaste problem så att nyare medlemmar kan tävla utan att lösa äldre problem.

Exempel på problem och lösningar

Det första Project Euler-problemet är multipler av 3 och 5

Om vi listar alla naturliga tal under 10 som är multiplar av 3 eller 5 får vi 3, 5, 6 och 9. Summan av dessa multiplar är 23.

Hitta summan av alla multiplar av 3 eller 5 under 1000.

Även om detta problem är mycket enklare än det typiska problemet, tjänar det till att illustrera den potentiella skillnaden som en effektiv algoritm gör. Brute -force- algoritmen undersöker varje naturligt tal mindre än 1000 och håller en löpande summa av de som uppfyller kriterierna. Denna metod är enkel att implementera, vilket visas av följande pseudokod :

 
      
        
  totalt  := 0  för  NUM  från 1 till 999  gör  om  NUM  mod 3 = 0  eller  NUM  mod 5 = 0  då  totalt  :=  totalt  +  NUM  returnerar  totalt

För svårare problem blir det allt viktigare att hitta en effektiv algoritm. För det här problemet kan vi reducera 1000 operationer till ett fåtal genom att använda principen för inkludering och uteslutning och en summeringsformel i sluten form .

{\begin{aligned}\mathrm {summa} _{\text{3 eller 5}}(n)&=\mathrm {summa} _{3}(n)+\mathrm {summa} _{5}(n)-\mathrm {summa} _{15}(n)\\[4pt]\mathrm {summa} _{k} (n)&=\summa _{i=1}^{\left\lfloor {\frac {n-1}{k}}\right\rfloor}ki\\[4pt]\sum _{i=1} ^{p}ki&={\frac {kp(p+1)}{2}}\end{aligned}}

Här betecknar $\mathrm {summa} _{k}(n)$ summan av multiplar av $k$ under $n$ . I big O-notation är brute-force-algoritmen $O{\bigl (}n{\bigr )}$ och den effektiva algoritmen är $O{\bigl (}1 {\bigr )}$ (förutsatt aritmetiska operationer med konstant tid).

Se även

externa länkar

Officiell hemsida
Project Euler forum [1]
Länkar till översättningsprojekt till flera andra språk