Project Euler

Проект Euler (именуван по Леонард Ојлер) е веб-страница посветена на серија пресметковни проблеми наменети да се решат со компјутерски програми. Проектот привлекува возрасни и студенти заинтересирани за математика и компјутерско програмирање. Од создавањето во 2001 година од Colin Hughes, Проектот Euler се здобил со значење и популарност низ целиот свет. Вклучува над 750 проблеми, со нов додаден приближно на секои две недели. Проблемите се со различна тежина, но секој од нив е решлив за помалку од една минута од процесорот со помош на ефикасен алгоритам на компјутер со скромно напојување.

Project Euler

Вид место	Problem Solving Website for Computational Mathematics
Создавач	Colin Hughes
Адреса	projecteuler.net
Комерцијално	No
Зачленување	Free
Пуштено	October 5, 2001

Од 27 април 2021 , проектот Euler има повеќе од 1,000,000 корисници кои го решиле барем едниот од проблемите, на над 100 различни програмски јазици со што било постигнато големо достигнување.

Одлики на страницата

Форум специфичен за секое прашање може да се види откако корисникот точно одговори на даденото прашање. Проблемите се подредуваат по лична карта, број што треба да се реши и тешкотија. Учесниците го следат нивниот напредок преку нивоа на постигнувања врз основа на бројот на решени проблеми. Се постигнува ново ниво за секои 25 решени проблеми. Постојат специјални награди за решавање на специјални комбинации на проблеми. На пример, постои награда за решавање на педесет првични нумерирани проблеми. Постои специјално ниво "Eulerians" за следење на постигнувањата базирани на најбрзите педесет решавачи на неодамнешните проблеми, така што поновите членови можат да се натпреваруваат без решавање постари проблеми.

Пример за проблем и решенија

Првиот проблем на проектот Euler е повеќекратни 3 и 5 (Multiples of 3 and 5)

Ако ги наведеме сите природни броеви под 10 што се множители на 3 или 5, добиваме 3, 5, 6 и 9. Збирот на овие множители е 23. Најдете го збирот на сите множители на 3 или 5 под 1000.

Иако овој проблем е многу поедноставен од типичниот проблем, тој служи за да ја илустрира потенцијалната разлика што ја прави ефикасниот алгоритам. Алгоритмот за brute сила (brute-force) го испитува секој природен број помал од 1000 и води тековна сума од оние што ги исполнуваат критериумите. Овој метод е едноставен за спроведување, како што е прикажано со следниот псевдокод (англиски: pseudocode):

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

Решенија во Python (програмски јазик) (автор е Agnimandur) и Befunge (автор е JarJar ).

N = 1000
print(sum([i for i in range(N) if i%3==0 or i%5==0]))

25*:*25**1-00p010p>00g 3% #v_10g00g+10pv
         |p00:-1g00 <     <   <
       @.g01<    > ^
              >00g5%#v_10g00g+10p^
              ^    <

За потешките проблеми, станува поважно (анг: inсreasingly important) да се одреди ефикасен алгоритам. За овој проблем, се намал 1000 операции на неколку со користење на inclusion-exclusion principle и формула за closed-form summation.

${\begin{aligned}\mathrm {sum} _{\text{3 or 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{aligned}}$

Еве, $\mathrm {sum} _{k}(n)$ означува збир од множители на $k$ подолу $n$. На големата О ознака (big O notation), алгоритамот за brute-сила (brute-force algorithm) е $O{\bigl (}n{\bigr )}$ а ефикасниот алгоритам е $O{\bigl (}1{\bigr )}$ (под претпоставка аритметички операции со постојано време).

Поврзано

• Список на награди за компјутерски науки
• Список на нешта именувани по Леонард Ојлер

 

Надворешни врски

• Почетна страница
• Врски до проекти за превод на неколку други јазици