Project Euler - Project Euler

Projekt Euler

Type websted	Problemløsning til websted for computermatematik
Lavet af	Colin Hughes
URL	projecteuler.net
Kommerciel	Ingen
Registrering	Gratis
Lanceret	5. oktober 2001

Project Euler (opkaldt efter Leonhard Euler ) er et websted dedikeret til en række beregningsproblemer, der skal løses med computerprogrammer. Projektet tiltrækker voksne og studerende, der er interesseret i matematik og computerprogrammering . Siden oprettelsen i 2001 af Colin Hughes har Project Euler vundet opmærksomhed og popularitet på verdensplan. Det inkluderer over 750 problemer, med et nyt tilføjet cirka hver anden uge. Problemer har forskellige vanskeligheder, men hver kan løses på mindre end et minuts CPU -tid ved hjælp af en effektiv algoritme på en beskedent drevet computer. Den 27. april 2021 har Project Euler mere end 1.000.000 brugere, der har løst mindst ét ​​problem på over 100 forskellige programmeringssprog.

Funktioner på webstedet

Et forum, der er specifikt for hvert spørgsmål, kan ses, efter at brugeren har besvaret det givne spørgsmål korrekt. Problemer kan sorteres på ID, nummer løst og vanskeligheder. Deltagerne kan følge deres fremskridt gennem præstationsniveauer baseret på antallet af løste problemer. Et nyt niveau nås for hver 25 løste problemer. Der findes særlige priser for at løse særlige kombinationer af problemer. For eksempel er der en pris for at løse halvtreds primtallede problemer. Der findes et særligt "Eulerians" -niveau for at spore præstationer baseret på de hurtigste halvtreds løbere af de seneste problemer, så nyere medlemmer kan konkurrere uden at løse ældre problemer.

Eksempel problem og løsninger

Det første Project Euler -problem er multipler af 3 og 5

Hvis vi angiver alle de naturlige tal under 10, der er multipler af 3 eller 5, får vi 3, 5, 6 og 9. Summen af ​​disse multipler er 23.

Find summen af ​​alle multiplerne af 3 eller 5 under 1000.

Selvom dette problem er meget enklere end det typiske problem, tjener det til at illustrere den potentielle forskel, som en effektiv algoritme gør. Den brute-force algoritme undersøger hver naturligt tal mindre end 1000 og holder løbende sum af dem, der opfylder kriterierne. Denne metode er enkel at implementere, som vist af følgende pseudokode :

total := 0
for NUM from 1 through 999 do
    if NUM mod 3 = 0 or NUM mod 5 = 0 then
        total := total + NUM
return total

For sværere problemer bliver det stadig vigtigere at finde en effektiv algoritme. Til dette problem kan vi reducere 1000 operationer til et par stykker ved hjælp af inklusions-ekskluderingsprincippet og en summeringsformel i lukket form .

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

Her betegner summen af ​​multipla af nedenstående . I stor O-notation er brute-force-algoritmen, og den effektive algoritme er (forudsat at man regner med konstant tid). ${\ displaystyle \ mathrm {sum} _ {k} (n)}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle O {\ bigl (} n {\ bigr)}}$${\ displaystyle O {\ bigl (} 1 {\ bigr)}}$

Se også

• Liste over datalogipriser
• Liste over ting opkaldt efter Leonhard Euler

Referencer

eksterne links

• Hjemmeside
• Links til oversættelsesprojekter til flere andre sprog