問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本で知ったことをざっくりまとめてみた (part 1)
目次
- 目次
- コンピュータと2進法の関係
- なぜコンピュータでは2進法を使うのか
- 円周率(Πとは)
- ルートと平方根の違い
- C++のint
- 剰余(mod)
- 論理演算とは
- ビット演算の流れ
- 3つ以上のAND, OR, XORに対する性質
- 多項式関数
- 単調増加とは
- 常用対数とは
- 数学の関数とプログラミングの関数の違い
- 家庭用コンピュータの計算速度
- 全探索とは
- プログラムの実行時間をおおよそで見積もる方法
- 公倍数とは
- 最小公倍数とは
- 最大公約数とは
- 整数Nの約数とは
- 自然数N, Mの公約数とは
- 最大公約数と最小公倍数の関係
- n以下の自然数におけるxの倍数またはyの倍数の個数を求めるアルゴリズム
- 計算回数がN2回のアルゴリズムの特徴
- 線形探索法とは
- 二分探索法とは
- 対数関数が入力に対する計算回数を表す場合
- 計算回数とプログラムの実行時間の関係
- 部分集合
- int型とlong long型
- 階乗を計算するプログラム
- オーバーフローとは
- 素数とは
- 合成数とは
- 高速な素数判定法
- 「全ての合成数Nは2以上√N以下のいずれかの整数で割り切れる」の証明
- 約数列挙法
- 関数内のループ文でreturnを使う
- 素因数とは
- 自然数Nを素因数分解して、素因数を出力するプログラム
- 参考記事
コンピュータと2進法の関係
コンピュータの内部では0と1の2種類の数字だけで数を表す2進法を用いて計算が行われています。
なぜコンピュータでは2進法を使うのか
コンピュータは電気的に動いているため、on/offの情報(ビット)を用いて計算を行います。on/offの1 or 0の情報を用いた計算の場合、２進法と相性がいいので、2進法が使われています。
円周率(Πとは)
円周率（えんしゅうりつ、英: Pi、独: Kreiszahl）とは、円の直径に対する円周の長さの比率のことです。
ルートと平方根の違い
ルートaとは、x2 = a(a>=0の実数)となるような非負の実数xのことです。 aの平方根とは、x2 = aとなるようなxのことです。±どちらも含みます。
C++のint
C++のint型のデータは、桁数が2進法で8 ~ 64桁と決まっています。
剰余(mod)
a mod bとは、aをbで割った余りのことです。
8 mod 5 = 3(8 / 5は1余り3)
プログラミングでは、a % bで余りを計算できます。
論理演算とは
論理演算とは、1(TRUE)または2(FALSE)をとる値の間で行われる演算です。AND, OR, XOR等が有名です。
ビット演算の流れ
ビット演算は、コンピュータ上で行われる演算の1つです。
■ビット演算の流れ 1. 整数(通常は10進数)を2進数に変換する 2. 桁ごとに論理演算を行う 3. 論理演算の結果を整数(通常は10進数)に変換する
ex) 11 AND 14 = 10
注) ビット演算では、通常の足し算のような繰り上がり処理は発生しません。
3つ以上のAND, OR, XORに対する性質
3つ以上の整数に対してAND, OR, XOR演算を行うとき、以下の様な性質が成り立ちます。
| 演算 | 性質 |
|---|---|
| AND | すべての数についてその桁が1であれば、計算結果は1。そうでなければ0 |
| OR | どれか1つの数についてその桁が1であれば、計算結果は1。そうでなければ0 |
| XOR | その桁が1である数が奇数個あれば、計算結果は1。そうでなければ0 |
多項式関数
x3以上にも範囲を広げた関数のことを、多項式関数と言います。
注) 2次以下も多項式に含まれます。
単調増加とは
単調増加であるとは、xの値が増加するとyの値も増加するグラフの性質です。
常用対数とは
常用対数とは、log10Xのことです。この数は、10を何乗したらXになるかを表します。つまり、log10XはXを10進法で表した時のおおよその桁数を示します。
数学の関数とプログラミングの関数の違い
- プログラミングの関数は入力がなくても良い(引数なしの関数)
- プログラミングの関数は入力が同じでも呼び出すたびに違う値を出力する時がある。(グローバル変数を関数内部の計算で使用していると起きる)
家庭用コンピュータの計算速度
コンピュータの計算速度にも限界が存在します。家庭用コンピュータの場合、1秒間に約10億回(109回)しか計算しません。
全探索とは
全探索とは、あり得る全てのパターンをしらみつぶしに調べるアルゴリズムです。
全探索は最もシンプルなアルゴリズムの1つであるため、問題を解く際には、まず全探索をしても現実的な時間で実行が終わるのかどうかを検討することが大切です。
プログラムの実行時間をおおよそで見積もる方法
プログラムの実行時間をおおよそで見積もる場合、以下の2点を考えることが重要です。
- どんな入力が来るのか？(何個の入力が来るのか？)
- どんなアルゴリズムを使用するのか？( O(1), O(n), O(n2))
以上の2点を考えれば、実行時間の制限を満たすようなアルゴリズムを選定して、プログラムを作成することができます。
公倍数とは
公倍数とは、2つ以上の自然数があるとき、そのどちらの倍数にもなっている自然数のことです。 公倍数は無数にあり、いくらでも大きい公倍数があります。
最小公倍数とは
最小公倍数とは、２つの自然数の公倍数の “0 以外” の最小の正の数のことです。
最大公約数とは
最大公約数とは、2つ以上の自然数の共通な約数(公約数)のうち最大の数のことです。
整数Nの約数とは
整数Nの約数とは、ある整数Nを割り切ることができる整数またはそれらの集合のことです。1も約数に含まれます。
自然数N, Mの公約数とは
自然数M, Nの公約数とは、2つ以上の自然数N, M, etcについて、そのいずれの約数にもなることができる整数のことです。
最大公約数と最小公倍数の関係
2つの自然数a, bの最大公約数をMとすると、
a = M × (最大公約数Mに入れない数a')
b = M × (最大公約数Mに入れない数b')
が成立します。
※) a'とb'は互いに素です。
したがって、最小公倍数をLとすると、a × b = M × Lの関係が成立します。
n以下の自然数におけるxの倍数またはyの倍数の個数を求めるアルゴリズム
ユークリッドの互除法を用いる場合
#include <bits/stdc++.h> using namespace std; int main() { int n, x, y, a, b, m, l, r, tmp, count; cin >> n >> x >> y; a = x; b = y; // xとyの最大公約数を求める if(a < b) { tmp = a; a = b; b = tmp; } r = a % b; while (r != 0) { a = b; b = r; r = a % b; } m = b; // xとyの最小公倍数を求める l = (x * y) / m; // 最小公倍数の倍数の数を求めて引く count = (n / x) + (n / y) - (n /l); cout << count << endl; }
for文を用いる場合
#include <bits/stdc++.h> using namespace std; int main() { int n, x, y, count = 0; cin >> n >> x >> y; for (int i = 1; i <= n; i++) { if(i % x == 0 || i % y == 0) { count++; } } cout << count << endl; }
計算回数がN2回のアルゴリズムの特徴
計算回数がN2回のアルゴリズムの特徴は、入力データの大きさが増えるごとに実行時間が2乗で増えることです。入力データが10倍、100倍に増えると、実行時間が100倍、10000倍に増えます。
線形探索法とは
線形探索法とは、探しているデータが一致するかを先頭から末尾まで順番に調べるアルゴリズムです。
二分探索法とは
二分探索法とは、探索したいデータが中央の要素より大きいか小さいかを繰り返し調べて高速に探索を行うアルゴリズムです。
対数関数が入力に対する計算回数を表す場合
対数関数が入力に対する計算回数を表す場合、対数関数の増加は緩やかなので、入力を増やしても計算回数が急激に増加せず、効率が良いです。
計算回数とプログラムの実行時間の関係
計算回数が増加すると、それに比例してプログラムの実行時間も増加します。
部分集合
部分集合とは、ある集合の一部分である集合のことです。 ある集合とある集合の共通部分の集合は、積集合と呼ばれます。
int型とlong long型
変数を宣言すると、変数名でメモリ領域が確保されます。 intは109、long longは1018の桁数を表す整数型です。
階乗を計算するプログラム
階乗はnの値によって非常に大きな数になるので、1 <= n <=20の範囲では、計算結果を代入する変数の型をlong longで定義した方が良いでしょう。
#include <bits/stdc++.h> using namespace std; int main() { int n = 0; long long s = 1; cin >> n; for (int i = 1; i <= n; i++) { s *= i; } cout << s << endl; }
オーバーフローとは
オーバーフローとは、限界よりも大きい数字を代入しようとしておかしな値になってしまうことです。
素数とは
素数とは、2 以上の自然数で、正の約数が 1 と自分自身のみである数です。注意ですが、1は素数ではありません。
合成数とは
合成数とは、1とその数自身以外に約数をもつ数である。4は合成数です。 自然数Nが素数ではないなら、Nは1又は合成数であると言えます。
高速な素数判定法
ある数Nが素数かどうかは、Nを2 ~ N - 1の数でそれぞれ割って、余りが0かどうかで判定できます。余りが0になるような時が存在しないなら、その数は素数です。このアルゴリズムの計算量はO(N)です。実は2 ~ N - 1まで調べる必要はなく、√N以下の最大の整数までを調べて割り切れなければ、Nは素数だと言えます。つまり、逆に言うと、全ての合成数Nは2以上√N以下のいずれかの整数で割り切れます。
「全ての合成数Nは2以上√N以下のいずれかの整数で割り切れる」の証明
背理法を用いて証明する。
全ての合成数Nは2以上√N以下のいずれかの整数で割り切れる。つまり、全ての合成数Nは2以上√N以下の中に約数が存在する。これを事実Fとする。
事実Fが成り立たないと仮定する。つまり、「全ての合成数は2以上√N以下の中に約数を持たない」とする。この時、合成数の最小の約数をAとする。このAは1とその数自身以外の数とする。
AはNを割り切るので、N = A * BとなるようなNの約数Bが存在する。
B = N / A と式変形できるが、 2 < √N < Aより、N / A < √Nである。合成数Nの最小の約数はAであるが、Bは√Nより小さいので、Bが合成数Nの最小の約数になる。したがって、矛盾が生じる。
よって、仮定がなり立たず、事実Fが正しいことがわかる。
約数列挙法
素数判定法と同じような手順で、約数を列挙することができる。
- i = 1 ~ √N以下の最大の整数で、Nがiで割り切れるかどうか調べる。
- 割り切れる場合、iとN / i を約数に追加する。
関数内のループ文でreturnを使う
関数内のループ文でreturnを使うと、関数を終了させるので、強制的にループを抜けることができます。
素因数とは
自然数Nを素因数分解して、素因数を出力するプログラム
#include <bits/stdc++.h> using namespace std; int main() { long long n, i = 2, result; cin >> n; vector<int> vec = { 0, 0 }; vec.at(0) = i; result = n; while (i * i <= n) { if (result % i == 0) { result /= i; vec.at(1) = vec.at(1) + 1; } else { if (vec.at(1) != 0) { for (int j = 0; j < vec.at(1); j++) { cout << vec.at(0) << " "; } } i++; vec.at(0) = i; vec.at(1) = 0; } } if (result != 1) { cout << result << endl; } }
