アルゴリズムーバイリンガル
どうもです。
そろそろこのブログの更新頻度も元に戻していこうかな・・・と思い立ち、今日から誕生日まで毎日ではありませんが、英語のアルゴリズム文書を読み、その知識を広めていこうとおもいます( ｰ`дｰ´)ｷﾘｯ
なんで誕生日まで？って気になる方もいると思うのでとりあえずまずは本のご紹介。
TopCoder社公式のCookbookです。内容的には色んな人がTopCoderについての記事を色々あつめてかんじだとはおもいますが、今回この本が11/22、つまり誕生日の翌日に発売ということで思い切って誕生日プレゼントとして頼んじゃいました笑
まぁ英語ということなので、その特訓としてもこんな企画を思いついたわけです。
ちなみにタイトルのバイリンガルというのは、僕がこの企画のなかで英語で知識を取り入れ日本語で知識をおっぴろげるこの行為がまさにバイリンガルだからです（正式な言葉の定義上）。
というわけで、もともと関西弁と標準語のバイリンガルな僕が英語も仲間に加えて成長したということですね☆・・・まぁこんな話してもつまらないと思うのでこのぐらいにしときますが。。。
スピードはまだまだなのでとりあえず少しずつ。
今日はMathematics for TopCodersというTopCoder内のチュートリアル文書の一つをちょこっとです。
やはりアルゴリズムと数学は強く結びついているもので、今日読んだ範囲では素数と最小公倍数および最大公約数の話がされています。
素数のさわりではまず素数判定の話がされています。
これはアルゴリズムやっていると割合よく知られている話ですが、ある数nが素数かどうかを判定するために試さなければいけない数は√nまでの自然数でいいという話です。
これは√n以上のnの約数はそれ以下の約数でnを割ることによって求められる約数であるため試すだけ無駄という理由があります。
それを踏まえると、これは次のような関数が最適な判定となります。
さて、このあとは素数列挙の話に移ります。
列挙となると先程の関数を使っていては膨大な計算量になってしまいます。というわけで、これは実際の数学でもよく使われるエラトステネスの篩を使うことになります。
これは割合有名なので、説明は省略しますが列挙の最適なコードは以下のようになります。
このあとこれで得られたbool配列を使って素数列挙をすれば完璧です。
ここらへんで本文は次の話題に移ります。
最大公約数は英語の略称から通称GCD、対して最小公倍数はLCMと呼ばれます。
GCDなどは愚直に割っていけば求められますが、やはりこれも工夫しない素数判定と同じように膨大な計算量が必要とされます。
ここで考え出されたのがユークリッドの互除法です。数学の世界ではあまり使われませんが、パソコンでのGCDは必ずこの方法でみちびくことになります。
簡単に説明すると、ある数a,b(a>bとする)の最大公約数を求めるとき、まずaをbで割って余りをだし（以下余りをa%bと表記する）、次にbをa%bで割って余りをだし、さらにa%bをbを割って出てきた余りで割り、と再帰的に繰り返していくと、余りが0になったときの割られる数が最大公約数になっているというものです。
再帰的なところがパソコンにあっている上、比較的少ない計算量で済むのでとても多用されます。
省略系で書いてしまいましたが、つまりbが0でないときはgcd(b,a%b)を返し、0の時aを返すという意味です。
最後にLCMの方はこのgcdを利用しa*b/gcd(a,b)で求められます。
今日のところは以上です。
今回は簡単な範囲でしたが、それでも知っているか知らないかで大きく競技プログラミング中の運命を左右される重要な範囲でもあります。
数学好きからプログラミングに入った以上、僕としても数学問題は解けるようになっていきたいのでこの続きもしっかりと読んでいこうと思います。
久々の長文でしたが、ここまで読んでくれた方はありがとうございました。
それでは
そろそろこのブログの更新頻度も元に戻していこうかな・・・と思い立ち、今日から誕生日まで毎日ではありませんが、英語のアルゴリズム文書を読み、その知識を広めていこうとおもいます( ｰ`дｰ´)ｷﾘｯ
なんで誕生日まで？って気になる方もいると思うのでとりあえずまずは本のご紹介。
TopCoder社公式のCookbookです。内容的には色んな人がTopCoderについての記事を色々あつめてかんじだとはおもいますが、今回この本が11/22、つまり誕生日の翌日に発売ということで思い切って誕生日プレゼントとして頼んじゃいました笑
まぁ英語ということなので、その特訓としてもこんな企画を思いついたわけです。
ちなみにタイトルのバイリンガルというのは、僕がこの企画のなかで英語で知識を取り入れ日本語で知識をおっぴろげるこの行為がまさにバイリンガルだからです（正式な言葉の定義上）。
というわけで、もともと関西弁と標準語のバイリンガルな僕が英語も仲間に加えて成長したということですね☆・・・まぁこんな話してもつまらないと思うのでこのぐらいにしときますが。。。
スピードはまだまだなのでとりあえず少しずつ。
今日はMathematics for TopCodersというTopCoder内のチュートリアル文書の一つをちょこっとです。
やはりアルゴリズムと数学は強く結びついているもので、今日読んだ範囲では素数と最小公倍数および最大公約数の話がされています。
素数のさわりではまず素数判定の話がされています。
これはアルゴリズムやっていると割合よく知られている話ですが、ある数nが素数かどうかを判定するために試さなければいけない数は√nまでの自然数でいいという話です。
これは√n以上のnの約数はそれ以下の約数でnを割ることによって求められる約数であるため試すだけ無駄という理由があります。
それを踏まえると、これは次のような関数が最適な判定となります。
bool isprime(int n) {
if (n <= 1) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (int i=3; i<=sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
さて、このあとは素数列挙の話に移ります。
列挙となると先程の関数を使っていては膨大な計算量になってしまいます。というわけで、これは実際の数学でもよく使われるエラトステネスの篩を使うことになります。
これは割合有名なので、説明は省略しますが列挙の最適なコードは以下のようになります。
vectorprime(int n) {
vectorisprime(n + 1, true);
isprime[0] = false;
isprime[1] = false;
for (int i = 2; i <= n; i++) {
if (isprime[i]) {
for (int j = i + i; j <= n; j += i) isprime[j] = false;
}
}
return isprime;
}
このあとこれで得られたbool配列を使って素数列挙をすれば完璧です。
ここらへんで本文は次の話題に移ります。
最大公約数は英語の略称から通称GCD、対して最小公倍数はLCMと呼ばれます。
GCDなどは愚直に割っていけば求められますが、やはりこれも工夫しない素数判定と同じように膨大な計算量が必要とされます。
ここで考え出されたのがユークリッドの互除法です。数学の世界ではあまり使われませんが、パソコンでのGCDは必ずこの方法でみちびくことになります。
簡単に説明すると、ある数a,b(a>bとする)の最大公約数を求めるとき、まずaをbで割って余りをだし（以下余りをa%bと表記する）、次にbをa%bで割って余りをだし、さらにa%bをbを割って出てきた余りで割り、と再帰的に繰り返していくと、余りが0になったときの割られる数が最大公約数になっているというものです。
再帰的なところがパソコンにあっている上、比較的少ない計算量で済むのでとても多用されます。
int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
省略系で書いてしまいましたが、つまりbが0でないときはgcd(b,a%b)を返し、0の時aを返すという意味です。
最後にLCMの方はこのgcdを利用しa*b/gcd(a,b)で求められます。
今日のところは以上です。
今回は簡単な範囲でしたが、それでも知っているか知らないかで大きく競技プログラミング中の運命を左右される重要な範囲でもあります。
数学好きからプログラミングに入った以上、僕としても数学問題は解けるようになっていきたいのでこの続きもしっかりと読んでいこうと思います。
久々の長文でしたが、ここまで読んでくれた方はありがとうございました。
それでは
