C#で Project Euler P6
問題
Problem 6 「二乗和の差」
最初の10個の自然数について, その二乗の和は,
12 + 22 + ... + 102 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.
Problem 6 - PukiWiki
解答
using System;
public static class P6 { public static void Main() { Console.WriteLine(Calc()); } private static long Calc() { long res = 0; long sum = 0; for(int a = 100 - 1; a >= 1; a--) { sum += a + 1; res += sum * a; } return res * 2; } }
計算量 $O(n)$
二乗の和を式１、和の二乗を式２とすると、
\begin{align*}
式２=&(N_1 + N_2 + N_3 + ... + N_n)^2 \\
= &N_1N_1+N_1N_2+N_1N_3+...+N_1N_n+N_2N_1+N_2N_2+N_2N_3+...+N_2N_n+ \\
&N_3N_1+N_3N_2+N_3N_3+...+N_3N_n+...+N_nN_1+N_nN_2+N_nN_3+...+N_nN_n \\
= &(N_1^2+N_2^2+N_3^2+...+N_n^2)+2\{N_1(N_2+N_3+...+N_n)+N_2(N_3+...+N_n)+...N_{n-1}(N_n)\}\\
=&Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}j
\end{align*}
ここで、
\begin{align*}
式１ = &Σ_{k=1}^n N_k^2
\end{align*}
であるため、
\begin{align*}
式２-式１ = &Σ_{k=1}^n N_k^2 + 2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j - Σ_{k=1}^n N_k^2\\
=&2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j
\end{align*}
と表せる。
この形で実装しやすいように、$2Σ_{k=1}^{n-1}N_kΣ_{j=k+1}^{n}N_j$を降順にした。
C#で Project Euler P5
問題
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Problem 5 - PukiWiki
解答
P5.cs
using System; public static class P5 { [STAThread] public static void Main() { Console.WriteLine(Calc()); } private static ulong Calc() { ulong res = 1; for(ulong num = 1; num <= 20; num++) { res = res * num / MyMath.EuclideanAlgorithem(res, num); } return res; } }
MyMath
public static class MyMath { // O(log n) public static ulong ModPow(ulong n, ulong p, ulong m) { ulong res = 1; for(; p > 0; p >>= 1) { res = (p & 1) == 1 ? res * n % m : res; n = (n * n) % m; } return res; } // O(log n) public static ulong EuclideanAlgorithem(ulong a, ulong b) { ulong work; while(b != 0) { work = b; b = a % b; a = work; } return a; } }
計算量 $O(n\log n)$
最大公約数から最小公倍数を求めていって掛け合わせるだけ。
C#で Project Euler P4
問題
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
Problem 4 - PukiWiki
解答
using System; public static class P4 { public static void Main() { Console.WriteLine(Calc()); } private static long Calc() { int ret = 0; for(int i = 999; i > 100; i--) { for(int j = 999; j > 100; j--) { string s = (i * j).ToString(); Console.WriteLine(i * j); if(IsRenum(i * j)) { Console.WriteLine(i + ", " + j); ret = i * j; goto End; } } } End: return ret; } private static bool IsRenum(int num) { var re = 0; for(var work = num; work > 0; work /= 10) { re = re * 10 + work % 10; } return re == num; } }
計算量 $O(n^2\log n)$
やり方が思い付かなかったので愚直に総当たりしました。
回文数の性質を調べればもっと計算量抑えられそう。
調べてないけど、直観的に11の倍数になりそうな気はする？
C#で Project Euler P3
はじめに
P2はフィボナッチ数列の級数に関する問題だけど、問題に魅力を感じなかったので飛ばしました。
で、僕としては好みなP3をやります。
そういや問題には直接関係ないけど、C#って末尾再帰の最適化してくれないのね。。。
再帰的に書こうと思ってたけど再帰はなるべく減らしてます。
問題
Problem 3 「最大の素因数」
13195 の素因数は 5, 7, 13, 29 である.
600851475143 の素因数のうち最大のものを求めよ.
Problem 3 - PukiWiki解答
P3.cs
using System; public static class P3 { public static void Main() { Console.WriteLine(Calc()); } private static ulong Calc() { ulong n = 600851475143; ulong index; for(index = 0; n != 1; index++) { while(n % PrimeGenerator.GetPrime(index) == 0) { n /= PrimeGenerator.GetPrime(index); } } return PrimeGenerator.GetPrime(index - 1); } }
PrimeGenerator
using System; using System.Linq; using System.Collections.Generic; public static class PrimeGenerator { private static ulong primeIndex; // 素数の添え字 private static ulong primeCounter; // 素数を探すために回すカウンタ private static readonly Predicate<ulong> TryDivision; // 試し割りを行うデリゲート private static Dictionary<ulong, ulong> primeList = new Dictionary<ulong, ulong>(); // 見つけた素数をバッファする空間 // 初期化 static PrimeGenerator() { primeList.Add(0, 2); // 2の登録 primeIndex = 1; primeCounter = 1; ulong multi = 1; // 素数の積、偶数はとばす為2は登録しない while(primeIndex < 10) { while(MyMath.EuclideanAlgorithem(primeCounter += 2, multi) != 1){ } primeList.Add(primeIndex++, primeCounter); multi *= primeCounter; } // 試し割りの登録、素数の積との最大公約数が1であるかで判定する TryDivision = n => MyMath.EuclideanAlgorithem(multi, n) == 1; } // 指定した添え字の素数を取得する public static ulong GetPrime(ulong idx) { while(primeIndex <= idx) { while(!PrimeTest(primeCounter += 2)){ } primeList.Add(primeIndex++, primeCounter); } return primeList[idx]; } // 素数判定を行う private static bool PrimeTest(ulong n) { // 試し割り、O(log n) if(!TryDivision(n)) { return false; } // フェルマーテスト、O(log n) if(MyMath.ModPow(2, n - 1, n) != 1) { return false; } // ミラーラビンテスト、O(m * (log n)^2) if(!MillerRabinTest(n)) { return false; } // 全てのテストに合格 return true; } private const int BigIntegersTestCount = 15; // 大きな素数判定の時は適当に15回くらいテストする private static readonly ulong[] MRTestPattern4759123141 = new ulong[]{ 2, 7 , 61 }; private static readonly ulong[] MRTestPattern341550071728321 = new ulong[]{ 2, 3, 5, 7, 11, 13, 17 }; // ミラーラビンテスト private static bool MillerRabinTest(ulong n) { // テストパターンの選択 IEnumerable<ulong> testPattern = MRTestPattern4759123141; if(n < 4759123141) { // 初期化で代入した為処理なし } else if(n < 341550071728321) { testPattern = MRTestPattern341550071728321; } else { // これより大きい数字のテストパターンを知らないので // 適当な素数を乱択する testPattern = GetRandomTestPattern().Take(BigIntegersTestCount); } // 全てのパターンでテストする foreach(var testNum in testPattern) { if(testNum >= n) { break; } if(!MillerRabinTestSub(n, testNum)) { return false; } } return true; } private static Random rnd = new Random(); static List<ulong> usedPrimes = new List<ulong>(); // 素数を乱択して返すシーケンス private static IEnumerable<ulong> GetRandomTestPattern() { usedPrimes.Clear(); ulong index; while(true) { index = (ulong)rnd.Next(primeList.Count); if(usedPrimes.Contains(index)) { continue; } usedPrimes.Add(index); yield return primeList[index]; } } // ミラーラビンテストを実際に行う private static bool MillerRabinTestSub(ulong n, ulong a) { ulong m1 = n - 1; // n - 1 // n - 1 を r * d へ分解、ただし r = 2^s, d ≡ 1 (mod 2) ulong r = m1 & (~m1 + 1); // 2のべき乗要素 ulong d = m1 / r; // 奇数要素 ulong pow2 = 0; ulong mp = MyMath.ModPow(a, d, n); // 2の0乗で 1 または -1 の場合は合格 if(mp == 1 || mp == m1) { return true; } for(pow2 = 1; pow2 <= r; pow2 <<= 1) { mp = MyMath.ModPow(a, pow2 * d, n); // 1 より先に -1 が出た場合は合格 if(mp == m1) { return true; } // 1 が -1 より先に出た場合は不合格 if(mp == 1) { return false; } } // 合格して抜けなければ不合格 return false; } public static IEnumerable<ulong> GetPrimeList() { ulong index = 0; while(true) { yield return GetPrime(index); index++; } } public static IEnumerable<ulong> GetPrimeList(Func<ulong, ulong, bool> predicator) { for(ulong index = 0; predicator(index, GetPrime(index)); index++) { yield return GetPrime(index); } } }
MyMath.cs
public static class MyMath { // O(log n) public static ulong ModPow(ulong n, ulong p, ulong m) { ulong res = 1; for(; p > 0; p >>= 1) { res = (p & 1) == 1 ? res * n % m : res; n = (n * n) % m; } return res; } // O(log n) public static ulong EuclideanAlgorithem(ulong a, ulong b) { ulong work; while(b != 0) { work = b; b = a % b; a = work; } return a; } }
計算量 $O(m\varphi(n)(\log n)^2)$
ただし、m はミラーラビンテストのテストパターン数、φはオイラーのトーシェント関数。
計算量あってるか怪しいけど多分これくらい！
計算量でφ関数とか見たことないけどこうとしか書けなかった。
最大の素因数を求めるということで、素直に素因数分解した。
総当たりの計算量$O(\sqrt{n})$くらいになるのかな？に比べればφ関数で母数をぐっと減らせるから速いと思う。
↑違いました、素因数でない素数の判定も行っているので$O(\sqrt{n}m(\log n)^2)$。
下限を出そうと思ったけどある自然数以下の素数を数える方法がわからずに表現できませんでした。。。
でも、使う素数の範囲があらかじめわかるので、素数判定するよりもエラトステネスの篩で素数表を作った方が速いかも。
C#で Project Euler P1
はじめに
暇だったのでやってみた。
本家 ： About - Project Euler
日本語： Project Euler - PukiWiki
テンプレート
using System; public static class P { public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { } }
これに対し、クラス名に問題番号を付けてCalcメソッドを実装する形でやっていこうと思います。
また、問題も載せますが日本語訳された方から引用します。
問題
Problem 1 「3と5の倍数」
10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.
Problem 1 - PukiWiki
解答
using System; public static class P1 { [STAThread] public static void Main() { Console.WriteLine(Calc()); } private static int Calc() { return Sum(3) + Sum(5) - Sum(3 * 5); } private static int Sum(int n) { var m = (1000 - 1) / n; return (n * (1 + m)) * m / 2; } }
計算量 O(1)
3の倍数と5の倍数それぞれの総和から重複してるところを引く。
等差数列なので繰り返しなしで求められる。
C# VSで埋め込んだリソースの場所
わからなくてはまったのでメモ
<プロジェクトの名前空間>.<リソースを追加したときに格納されるフォルダ、デフォルトで"Resources">.<追加したリソースのファイル名>
にあった。
調べ方はこんな感じ。
var asm = System.Reflection.Assembly.GetExecutingAssembly(); var resources = asm.GetManifestResourceNames(); foreach(var resource in resources) { System.Console.WriteLine(resource); }
色々調べまわってはまったけども、素直にMSDN見るのが一番と学べた。
コード : アセンブリでのリソース名の検索 (Visual C#)
あと、ソリューションエクスプローラの階層ってそのまま名前空間になってそう。
ソリューションに依存しないけどdllにするには大げさなモジュールとかどうやって扱ってるんだろうみんな。
C# EventArgsの継承とかイベントのnullチェックがめんどくさい
のでこんな拡張メソッド作ってみた、便利。
using System; ///<summary>汎用のEventArgsを生成するためのクラス</summary> public static class GenericEventArgs { public static GenericEventArgs<TArg> Create<TArg>(TArg arg) { return new GenericEventArgs<TArg>(arg); } } ///<summary>汎用のEventArgs</summary> ///<remarks>EventArgsを継承して指定された型の値を持つだけ</remarks> public class GenericEventArgs<TArg> : EventArgs { public TArg Value{ get; private set; } public GenericEventArgs(TArg arg) { this.Value = arg; } } ///<summary>デリゲートに関する拡張メソッド定義用クラス</summary> public static class DelegateExtensionMethods { ///<summary>素直なイベントハンラ型デリゲートの実行</summary> public static void Run( this EventHandler handler, object sender, EventArgs e ){ if(handler != null) { handler(sender, e); } } ///<summary>汎用イベントハンドラ型デリゲートの実行</summary> public static void Run<TEventArgs>( this EventHandler<TEventArgs> handler, object sender, TEventArgs e ) where TEventArgs : EventArgs { if(handler != null) { handler(sender, e); } } ///<summary>汎用EventArgsを用い、引数を生で渡して実行</summary> ///<remarks>EventArgsを継承するのが面倒で横着したいときに使う</remakrs> public static void Run<TArg>( this EventHandler<GenericEventArgs<TArg>> handler, object sender, TArg e ){ handler.Run(sender, GenericEventArgs.Create(e)); } }
使い方はこんな感じ。
using System; public class MainApp { [STAThread] public static void Main() { var eventRaiser = new EventRaiser(); Console.WriteLine("イベント未登録時にイベント発行"); eventRaiser.OnEvent("hoge"); Console.WriteLine("イベント登録"); eventRaiser.Event += (sender, e) => Console.WriteLine(e.Value); Console.WriteLine("イベント登録後にイベント発行"); eventRaiser.OnEvent("fuga"); } } public class EventRaiser { public event EventHandler<GenericEventArgs<string>> Event; public void OnEvent(GenericEventArgs<string> e) { this.Event.Run(this, e); } public void OnEvent(string e) { this.Event.Run(this, e); } }
結果はこんな感じ。
イベント未登録時にイベント発行 イベント登録 イベント登録後にイベント発行 fuga 続行するには何かキーを押してください . . .
きっちり落ちずに流してくれる！
ちょー便利！！
