解決すべき別の問題がある皆さん、ようこそ!今日は三角数とその約数、特に巨大な数について話します。 自然界の三角数を表現した私の素晴らしい芸術的表現を賞賛することができますが、いつもの免責事項を述べておきます。 この問題は素晴らしいウェブサイトによって提供されています  、購読できます ！解決すべき数学とコーディングの問題は 800 を超え、それらに関する議論の膨大なアーカイブがあります。文字通り、頭をかき回して新しいことを学ぶのに最適なツールです。ぜひチェックして、あなたの課題も解決してみてください! プロジェクトオイラー.net ここ 私は専門プログラマーではありません。ただ、この種のことについて書くのが好きで、自分のショットを共有するのが好きな人です。これが最適な解決策ではないことは確かです。そのため、より良い解決策や、それを最適化する方法についてのアイデアがある場合は、共有していただければ大歓迎です。 話はこれくらいにして、今日の問題が何を提供するかを見てみましょう。 三角数列は自然数を加算することで生成されます。したがって、7 番目の三角形の数は 1+2+3+4+5+6+7=28 となります。最初の 10 項は次のようになります:1、3、6、10、15、21、28、36、45、55、…   最初の 7 つの三角形の数の因数をリストしてみましょう。   28 が、約数が 5 を超える最初の三角形の数であることがわかります。 約数が 500 を超える最初の三角形の数値はいくらですか? 問題は非常に単純です。 が 500 を超える最初の は何かを理解するように求められます。まず最初に、三角数とは何か、約数とは何かをよく見てみましょう。 約数 三角数 三角数字 三角数は、特定の数までのすべての自然数の合計によって形成される数の特定のサブセットです。 ため、三角形と呼ばれます。ここではいくつかの例を示します。  いつでも三角形として配置できる 上の画像では、3番目、4番目、5番目の三角数字です。したがって、たとえば、3 番目の数字は 1+2+3 = 6 として形成され、4 番目の数字は 1+2+3+4 = 10 として形成されます。一般的に言えば、nᵗʰ 三角数 Tₙ は次と等しいです。 もちろん、これは数学で最も有名な級数の 1 つであり、 によっても提示され、連続する整数の合計は以下に等しいと述べました。 ガウス したがって、基本的に、たとえば 3 番目の三角数を計算したい場合は、単純に 3*4/2 = 6 を計算します。これは、解を書き始めるときに非常に役立ちます。 ディバイザーズ 数値 の (または ) の定義を与えるのは非常に簡単です。 たとえば、3 と 6 を掛けて再び 18 を得ることができるため、3 は 18 の約数です。 n 約数 因数 数値 に別の整数 を乗算して、再び 求めることができます。 j k n を ただし、5 と掛け算して 18 になる数 存在しないため、5 は 18 の約数ではありません。 k は この定義により、重要な特性も得られます。j を 乗算して を取得できるため  j が n の約数である場合、  を乗算して を取得できるため、  も k に n 、 j n k n の約数です。 (実際、  常に 1 であり、  は である可能性があります)。 このようにして、数値 は常に少なくとも 2 つの約数 と があることを確認できます n に j k j は k n また、別の言い方をすると、  。したがって、たとえば、18/3 = 6 となり、余りは 0 になります。 の余りが 0 に等しい場合、数値 は数値 の約数になります n / j j n   の場合、  の約数であるという を使用して、この概念をより適切に形式化できます。つまり、この 2 番目のプロパティを取得します。  n % j = 0 j は n モジュラー演算 私たちが興味を持っている 3 番目で最後の特性 これは非常に簡単に理解できます。最初の特性から、因子が 1、…、n の範囲で何らかの形で「リンク」されていることがわかります。 は、  自体ではなく より大きい数 の約数は存在できないということです。 n 、n/2 n これも、    したがって、  もう一度 18 を例として取り上げ、その約数を見つけて、この特性を反映するように色を付けてみましょう。  j \ n の場合、 j * k = n であるためです。 k\n も同様です。 したがって、たとえば、  およびその逆の場合、  これは、1 以外に使用できる最小の 2 であることを意味し、これにより最大の が得られます。可能、   (この場合は 9)  これは機能します: j = 3、k = 6 の場合、 j = 6、k = 3 の場合、 j は k n/2 。 偶数の場合、最大の係数は n の半分に正確に等しくなります。 奇数の場合:  を 2 で割ることができない場合 (奇数であると有理数が得られるため)。これは、  常に n j > 2 のみを使用できることを意味し、 k < n/2 の結果が得られます。 最後に、  たとえば、  考えられる因数 別の因数 を生成します。このケースについては、後のコード部分で詳しく説明します。 と 等しくなるケースは 1 つだけあり、それは が平方数の場合です。 j k が n n = 36 の場合、 j = 6 は k = 6 もちろん、これらの概念は非常に些細なものですが、ソリューションでは非常に重要になります。 コード コードは で書かれます。これは、非常に高速な言語でありながら、優れた可読性を維持しているためです。解を 2 つに分割します。まず、 。 Go 数値の約数を求める関数を作成し、次にそれを三角数に適用します まず関数を見てみましょう。   https://gist.github.com/NicolaM94/8fb97503da0c4d4431fcd5a858d13cdb?embedable=true 整数 を受け入れ、約数を含む整数の配列 返す関数を作成します。その後、自明な因数、つまり 1 と 自体を します。 n out n out 次に、   2 から までループし始めます (2 番目のプロパティから。n  偶数の場合、  が によって約数に加算されるため、   /2 自体には興味がないことにも注意してください)。  反復: これが、 j≤ n/    で停止する理由です)。 j n/2 n k = n/2 j = 2 n/2 j = 2 j<n/2 j≤ n/2 このようにして、  の前半でのみ約数をチェックできるため、プロセスがかなり高速化されます。 n 各ループで 3 つのことをチェックします。  3 番目の if ステートメントは、実際には かどうか、つまり 0 ≡ n (mod j) かどうかをチェックします。そうであれば、因子が見つかったので、リストに を追加します。  を計算して次の に進むことで、対応する をリストに追加することもできます。 n%j==0 j n/j j k  2 番目の if ステートメントは、  が正方形であるかどうか、つまり が の根であるかどうかをチェックします。その場合、重複を避けるために、除数  1 つだけ に追加され、アルゴリズムは次に進みます。 n j n j out   と仮定します。この小さなブロックが欠落している場合、3 番目の if ステートメントがトリガーされ、  が および を受け取ることになり、重複が作成されます。 n = 36 out j = 6 k = n/j = 36/6 = 6 最初の if ステートメントは最も複雑です。その目的は、  ペアの繰り返しが始まっているかどうかを確認することです。そうであれば、因子はすべて in  にすでに存在するため、ループを即座に中断できます。 jk out この 3 番目の点については、特に または  2 つのケースをチェックする必要があります。 out[len(out)-1] == j out[len(out)-2] == j 最初のケースは古典的なケースです。たとえば、数値 T₇ = 28 を考えます。   の場合、最後に挿入された値と等しくなります。したがって、ループを断ち切ることができます。 j = 7  2 番目のケースは、正方形 見つかった場合にのみ発生します。たとえば、36 を再度取り上げます。 n   の場合、これは の平方根の前に追加される最後の値と等しくなります。この値は 1 回だけ現れます。したがって、この時点でループを解除できます。 j = 9 n 最後に、単純に約数 ができます。 return out 結果の適用 関数が完成したので、それをすべての三角数に適用できます。三角数のジェネレーターとして機能するカウンター を作成します。ガウス方程式を使用して関連する三角数 を計算し、その約数がいくつあるかを確認します。 c tn  500 を超える場合は、その を結果として返します。 tn   https://gist.github.com/NicolaM94/b01fb72874cb903982b887846fcc5c0c?embedable=true#file-main-go しかし…落とし穴があります！   数学のなぞなぞや問題を提示することに加えて、 。 ProjectEuler.net は本当に素晴らしいプロジェクトです。 その主な焦点は数学について学び、考え、推論するためのツールを提供することです そして、私はそれが気に入っています。彼らは非常に熱心なので、問題の結果やガイドを公開することは実際には禁止されています (これは最初の 100 の問題の 1 つなので、許可されているのは理解しています)。 このことを考えると、 。このため、私は実際の解決策を提供するつもりはありません。自分で試してみて、私のアルゴリズムよりも優れたアルゴリズムを考え出すようにしてください (アルゴリズムはたくさんあります)。ごめんなさい、みんな！ 😅 単にコピペで解決策を提示して実績を取得するのは公平ではないと思います 時間計算量 これはかなりひどいショットだと思うので、もっと良い解決策がたくさんあると私は確信しています。   関数は線形時間で実行されます。これは、インスタンス のサイズに依存し、最大でも ループも実行されるためです。それは O(n) であると考えることができます。 FindDivisor n n/2 ただし、最初に各三角数を計算する必要があり、これにも O(tn) 時間がかかります。tn は結果 (実際に最後に計算したもの) です。これを考慮すると、アルゴリズム全体の時間計算量はおよそ O(tn*n) になるはずです。   が引数または関数となり、その中で最大 個のループを実行するため、時間計算量は O(tn*tn/2) = O(tn²/2) = O(tn²) として書き換えることができます。したがって、 が、残念ながら! tn n/2 二次時間の解になります しかし、アルゴリズムがその程度の複雑さであるにもかかわらず、それにもかかわらず、かなり高速に実行されることに驚きました。私のマシン (AMD Ryzen 5、平均 2700 MHz) で結果を出すには、322.564227 ミリ秒かかりました。 ただし、約数 1000 を超える最初の三角数を見つけようとすると 3.827144472 秒かかったので、時間の消費が急速に増加していることがはっきりとわかります。 結論 ついに成功しました！この記事を楽しんでいただければ幸いです。また、そこから何か興味深いものを受け取っていただければ幸いです。もしそうなら、拍手を 1 ～ 2 回残して、このトピックに興味を持つ可能性のある誰かと記事を共有してください。  ProjectEuler の素晴らしい仕事に改めて感謝の意を表します。ぜひ行って、彼らが提供できるものをチェックしてみてください。きっととても面白いと思うでしょう！ そしていつものように、読んでいただきありがとうございます。 ニコラ

Read My Stories

このオーディオは、ストーリーの元の言語で制作されています。

長すぎる; 読むには

Make resilience your competitive advantage

毎日のコーディング問題: 三角数と大約数

About Author

コメント

ラベル

この記事は

Related Stories

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

AI の力を解き放つ。最先端技術の体系的レビュー: 概要と序論

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

フォーラムからフィードへ: ソーシャルメディアアルゴリズムがデジタルインタラクションを形作る仕組み

AI の力を解き放つ。最先端技術の体系的レビュー: 概要と序論

Claude Sonnet 3.5 システムプロンプトの漏洩: 法医学的分析

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps