ProjectEulerを使用した1つのタスクのカスタムソリューション

Project Eulerの問題は、同じタスクに対してさまざまな難易度で楽しみながら脳を鍛えることができるため、優れています。 最も単純なアプローチはブルートフォースです。 最初の20個のタスクは、このようなアプローチによって99％解決されます。 タスクに正解を送信した後、フォーラムスレッドがそのタスクで開きます。 数十カ国のアマチュアが競い合い、ソリューションをより洗練された形で引用します。 より高度なものは、ソリューションが記述されている言語の組み込み機能を使用しますが、本質は同じです-バスティングまたはネストされたループの束による明示的または特別な関数の呼び出しによる暗黙的です。 PythonまたはRuby（多くの場合1行または2行）で特に美しく見えますが、JavaおよびC ++ではより冗長です。 遠ければ遠いほど、BigIntegerのようなクラスを使用して、より真っ直ぐな「パワー」ソリューションが見えます。 タスク数が増えると、ブルートフォースの使用はますます難しくなります。 純粋な数学には多くの問題があり、紙の問題を解決し、完全に複雑でないものをエンコードする必要があります。 コードをまったく作成せずに作成できる場合もあります。たとえば、組み合わせの使用など、多くのタスクがあります。



しかし、完全に非標準的なソリューションを見つけた方が快適な場合もあります。





例。 タスク9 。 a + b + c = 1000のような整数a、b、cのピタゴラスのトリプレットを見つけます。ピタゴラスのトリプレットは3つの正の整数a <b <cであり、直角三角形の辺である、つまり a ^ 2 + b ^ 2 = c ^ 2。 最も有名な学校の例：3、4、5。



検索ソリューションは明らかです。 時間の大幅な短縮が実現します。このようなトリプレットの特性を知っていれば、多くの反復を節約できます。 しかし、私たちは反対に行きます。



ソリューションのすべてのバージョンのMS Excelスイートでソルバー最適化ツールを使用します。







ソルバーは、解を見つけるための非常に強力なツールになる可能性がありますが、非常に多次元の場合には失敗すると言います。 数十個の変数の巨大な連立方程式の解、または少なくとも局所的な近似を探していた男性を見たとき、私はまだこの写真を覚えています。 彼は経済学の修士号を書きました。 彼は確かにいくつかの言語のいずれかでコードを書くことができましたが、それはスクラップでした。 ソルバーの設定を非常に大きな反復回数、非常に長い検索時間に設定し、職場のコンピューターで起動しました。 そこにあるものが結果としてカウントされました。



ところで、 最大パスの合計の問題を解決するためにソルバーを使用することはできませんでした。そこでは、関数は完全に滑らかではなく、ランダムです。



私が言ったように、いくつかの問題はコードなしで分析的に解決されました。 二項係数を計算しなければならなかったとき、私はこれにWindowsエンジニアリング計算機を使用しました。 最初の100の最後の1つの問題はSQLを使用して解決されました-必要なのは、データをテーブルにコピーすることだけでした-DDLスクリプトを作成するNotepad ++の通常の方法です。その後、テーブルにデータが入力され、クエリが1行になります。



projectEulerの統計を見るのもとても楽しいです。 使用される最も効率的な言語と環境はC ++ \ Javaではなく、フランス語のmatpack PARI / GP、Mathematica、Python、Haskelです。 多くのエキゾチックなものが使用されます（投稿執筆時の統計）：

	言語	ユーザー数	平均解決率	スコアインデックス
1	パリ/ GP	79	23％	99
2	Mathematica	1272	13％	92
3	Python	26887	8％	81
4	ハスケル	4680	8％	67
5	セージ	180	12％	62
6	Perl	2237	8％	61
7	C / C ++	28454	6％	61
8	APL / J / K	254	11％	60
9	Java	18158	6％	58
10	C＃	9122	6％	54
11	ML	436	9％	54
12	もみじ	265	9％	49
13	ルビー	4229	6％	49
14	スカラ	1270	7％	49
15	おたふく風邪	22	16％	49
16	Lisp	1096	7％	48
17	デルファイ	451	8％	48
18	F＃	936	7％	47
19	スキーム	744	7％	46
20	Matlab	2122	6％	45
21	マグマ	21	15％	45
22	ラケット	140	9％	44
23	コンポーネントパスカル	7	22％	42
24	ベーシック	1162	6％	42
25	行く	414	7％	41
26	フリンク	10	18％	41
27	クロージュア	991	6％	41
28	D	163	8％	40
29日	鉛筆/紙	805	6％	39
30	パスカル	601	6％	38
31	Tcl	65	9％	37
32	R	496	6％	37
33	RPL	14	14％	36
34	スプレッドシート	412	6％	35
35	ギャップ	26	11％	35
36	組立	152	7％	34
37	ルア	332	6％	34
38	Fortran	308	6％	34
39	フォース	39	9％	32
40	Smalltalk	90	7％	31
41	SAS	17	10％	28
42	エイダ	97	6％	27
43	ECMAScript	834	4％	26
44	Q	74	6％	25
45	アーラン	580	4％	25
46	ジュリア	36	7％	24
47	オートホットキー	12	10％	24
48	プロローグ	114	5％	23
49	Php	2445	3％	23
...	...	...	...	...
53	オクターブ	63	5％	20
54	ブー	17	7％	19
55	コブラ	3	18％	19
56	ロゴ	26	6％	19
57	グルーヴィー	38	5％	18
58	SQL	37	5％	17
59	COBOL	19	6％	17
60	Powerhell	68	4％	16
...	...	...	...	...
68	ボーンシェル	32	3％	10
...	...	...	...	...

もちろん、ほとんどの人は米国から、約2万8千人、中国とロシアからは約同数、約3,000人です。しかし、この国に突っ込んで仕事のトップ100を見ると、中国人がより効果的であることがわかります。 400、350、300など タスク。 また、インドでは、反対に、参加者は約2.5倍多くなりますが、スーパーソルバーはロシアよりも少なくなります。 私の意見では、すべてを人々の数に正規化し、統計的に有意な数の参加者から始めれば、その国の高等教育の有効性の評価を得ることができます。