- PVSM.RU - https://www.pvsm.ru -
Задачки с Project Euler [1] хороши тем, что позволяют развлечься и потренировать
Но иногда приятнее найти совсем нестандартное решение.
Пример. Задача 9 [3]. Найти пифагорейский триплет целых чисел a, b, c, такой что a + b + c = 1000. Напомню, пифагорейский триплет — это три целых положительны числа a < b < c, являющиеся сторонами прямоугольного треугольника, т.е. a^2 + b^2 = c^2. Самый известный школьный пример: 3, 4, 5.
Переборное решение очевидно. Она сильно сокращается по времени, если знать свойства таких триплетов, можно много итераций сэкономить. Но мы пойдем другим путем.
Будем использовать для решения оптимизационный инструмент Solver в комплекте MS Excel любой версии.
Solver может быть очень мощным инструментом поиска решения, хотя говорят, что в очень многомерных случаях он пасует. До сих пор вспоминаю картину, когда я увидел человека, искавшего Solver-ом решение или хотя бы локальное приближение для огромной системы уравнений на несколько десятков переменных. Писал для магистерского диплома, что-то по экономике. Он точно мог бы написать код на любом из нескольких языков, но было в лом. Поставил настройки в Solver на огромное максималное число итераций, огромное максимальое время поиска и запустил на своем компе на работе. Что-то там насчитал в результате.
Кстати, Solver мне не удалось приткнуть для решения задачи о максимальной сумме пути [4] — там совсем негладкая получается функция, случайная.
Несколько задачек, как я говорил, удалось решить без кода, аналитически. Один раз пришлось посчитать биномиальный коэффициент, для этого использовал инженерный калькулятор Windows. Одна задача в конце первой сотне решилась с помощью SQL — надо было только скопировать данные в табличу — регулярка в Notepad++, создающая DDL скрипт, после чего заполнение таблицы и запрос в одну строку.
Очень улекательно также посмотреть на статистику projectEuler. Максимально эффективные используемые языки и среды — не C++Java, а французский матпакет PARI/GP, Mathematics, Python и Haskel. Используется множество экзотических (статистика на момент написания поста):
Language | Number of Users | Average Percent Solved | Score Index | |
---|---|---|---|---|
1 | PARI/GP [5] | 79 | 23% | 99 |
2 | Mathematica [6] | 1272 | 13% | 92 |
3 | Python [7] | 26887 | 8% | 81 |
4 | Haskell [8] | 4680 | 8% | 67 |
5 | Sage [9] | 180 | 12% | 62 |
6 | Perl [10] | 2237 | 8% | 61 |
7 | C/C++ [11] | 28454 | 6% | 61 |
8 | APL/J/K [12] | 254 | 11% | 60 |
9 | Java [13] | 18158 | 6% | 58 |
10 | C# [14] | 9122 | 6% | 54 |
11 | ML [15] | 436 | 9% | 54 |
12 | Maple [16] | 265 | 9% | 49 |
13 | Ruby [17] | 4229 | 6% | 49 |
14 | Scala [18] | 1270 | 7% | 49 |
15 | MUMPS [19] | 22 | 16% | 49 |
16 | LISP [20] | 1096 | 7% | 48 |
17 | Delphi [21] | 451 | 8% | 48 |
18 | F# [22] | 936 | 7% | 47 |
19 | Scheme [23] | 744 | 7% | 46 |
20 | Matlab [24] | 2122 | 6% | 45 |
21 | Magma [25] | 21 | 15% | 45 |
22 | Racket [26] | 140 | 9% | 44 |
23 | Component Pascal [27] | 7 | 22% | 42 |
24 | BASIC [28] | 1162 | 6% | 42 |
25 | Go [29] | 414 | 7% | 41 |
26 | Frink [30] | 10 | 18% | 41 |
27 | Clojure [31] | 991 | 6% | 41 |
28 | D [32] | 163 | 8% | 40 |
29 | Pencil/Paper [33] | 805 | 6% | 39 |
30 | Pascal [34] | 601 | 6% | 38 |
31 | Tcl [35] | 65 | 9% | 37 |
32 | R [36] | 496 | 6% | 37 |
33 | RPL [37] | 14 | 14% | 36 |
34 | Spreadsheet [38] | 412 | 6% | 35 |
35 | GAP [39] | 26 | 11% | 35 |
36 | Assembly [40] | 152 | 7% | 34 |
37 | Lua [41] | 332 | 6% | 34 |
38 | Fortran [42] | 308 | 6% | 34 |
39 | Forth [43] | 39 | 9% | 32 |
40 | Smalltalk [44] | 90 | 7% | 31 |
41 | SAS [45] | 17 | 10% | 28 |
42 | Ada [46] | 97 | 6% | 27 |
43 | ECMAScript [47] | 834 | 4% | 26 |
44 | Q [48] | 74 | 6% | 25 |
45 | Erlang [49] | 580 | 4% | 25 |
46 | Julia [50] | 36 | 7% | 24 |
47 | AutoHotkey [51] | 12 | 10% | 24 |
48 | Prolog [52] | 114 | 5% | 23 |
49 | PHP [53] | 2445 | 3% | 23 |
... | ... | ... | ... | ... |
53 | Octave [54] | 63 | 5% | 20 |
54 | Boo [55] | 17 | 7% | 19 |
55 | Cobra [56] | 3 | 18% | 19 |
56 | Logo [57] | 26 | 6% | 19 |
57 | Groovy [58] | 38 | 5% | 18 |
58 | SQL [59] | 37 | 5% | 17 |
59 | COBOL [60] | 19 | 6% | 17 |
60 | PowerShell [61] | 68 | 4% | 16 |
... | ... | ... | ... | ... |
68 | Bourne Shell [62] | 32 | 3% | 10 |
... | ... | ... | ... | ... |
Больше всего народу, конечно, из Штатов — около 28 тысяч, из Китая и России примерно одинаковое число — около 3000. Но если ткнуть в страну и посмотреть топ 100 по задачам, видно, что китайцы эффективнее — там больше число людей, решивших, более 400, 350, 300, итд. задач. А в Индии наоборот — участников примерно в 2.5 раза больше, но супер-решателей поменьше, чем в РФ. По-моему если нормализовать это все на число населения, то начиная с какого-то статистически значимого числа участников на страну можно получить оценку эффективности высшего образования в ней.
Автор: makondo
Источник [63]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/46990
Ссылки в тексте:
[1] Project Euler: http://projecteuler.net/about
[2] мозг: http://www.braintools.ru
[3] Задача 9: http://projecteuler.net/problem=9
[4] задачи о максимальной сумме пути: http://projecteuler.net/problem=18
[5] PARI/GP: http://language=PARI%252FGP
[6] Mathematica: http://language=Mathematica
[7] Python: http://language=Python
[8] Haskell: http://language=Haskell
[9] Sage: http://language=Sage
[10] Perl: http://language=Perl
[11] C/C++: http://language=C%252FC%252B%252B
[12] APL/J/K: http://language=APL%252FJ%252FK
[13] Java: http://language=Java
[14] C#: http://language=C%2523
[15] ML: http://language=ML
[16] Maple: http://language=Maple
[17] Ruby: http://language=Ruby
[18] Scala: http://language=Scala
[19] MUMPS: http://language=MUMPS
[20] LISP: http://language=LISP
[21] Delphi: http://language=Delphi
[22] F#: http://language=F%2523
[23] Scheme: http://language=Scheme
[24] Matlab: http://language=Matlab
[25] Magma: http://language=Magma
[26] Racket: http://language=Racket
[27] Component Pascal: http://language=Component%2BPascal
[28] BASIC: http://language=BASIC
[29] Go: http://language=Go
[30] Frink: http://language=Frink
[31] Clojure: http://language=Clojure
[32] D: http://language=D
[33] Pencil/Paper: http://language=Pencil%252FPaper
[34] Pascal: http://language=Pascal
[35] Tcl: http://language=Tcl
[36] R: http://language=R
[37] RPL: http://language=RPL
[38] Spreadsheet: http://language=Spreadsheet
[39] GAP: http://language=GAP
[40] Assembly: http://language=Assembly
[41] Lua: http://language=Lua
[42] Fortran: http://language=Fortran
[43] Forth: http://language=Forth
[44] Smalltalk: http://language=Smalltalk
[45] SAS: http://language=SAS
[46] Ada: http://language=Ada
[47] ECMAScript: http://language=ECMAScript
[48] Q: http://language=Q
[49] Erlang: http://language=Erlang
[50] Julia: http://language=Julia
[51] AutoHotkey: http://language=AutoHotkey
[52] Prolog: http://language=Prolog
[53] PHP: http://language=PHP
[54] Octave: http://language=Octave
[55] Boo: http://language=Boo
[56] Cobra: http://language=Cobra
[57] Logo: http://language=Logo
[58] Groovy: http://language=Groovy
[59] SQL: http://language=SQL
[60] COBOL: http://language=COBOL
[61] PowerShell: http://language=PowerShell
[62] Bourne Shell: http://language=Bourne%2BShell
[63] Источник: http://habrahabr.ru/post/196966/
Нажмите здесь для печати.