アルゴリズムとデータ構造入門1
当記事について
Aizu Online Judgeに掲載されている問題をC++で解くという遊びをしているので、考え方の例と解けたコード例を記録していこうかと思います。コード例はたたんでおこうかと思います。クリックやタップでコード例を開けます。
問題のリンクはこの辺りになります:
今回は、アルゴリズムを4問解いてみました。最初の方なのでかなり簡単ですが、C++が久々なのでここからやっています。
うっかりコンテナ型を使わないで配列で書いてしまったので反省してます。しかもdelete[]してませんでした。猛省しています。
ALDS1_1_A: Insertion Sort: 挿入ソート
まずは1問目。擬似コード通りに実装すれば動かすことはできます。
標準入力と標準出力は自分でなんとかします。というかほぼその練習になります。
考えたこと
簡単なのですぐ終わってしまいますが、ただ実装しておわるよりはコードで何をしているかも考えたほうがいいです。トランプの札で例えられているように、手札を並び替えるときの視線の動きをループを使って表現しています。と言っても1つの数字を選んだ後は、その数字の1つ手前から遡って見ていく感じになります。
コード例
C++での実装例になります。出力時の空白の調整があまりスマートでないのでなんとかしたいと思っています。
コード例は折り畳んであります。
// Insertion Sort
#include <iostream>
void insertionSort(int *A, int n);
void showArray(int *A, int n);
int main()
{
int n;
std::cin >> n;
int *A = new int[n]{0};
for (size_t i = 0; i < n; i++)
{
std::cin >> A[i];
}
showArray(A, n);
insertionSort(A, n);
}
void insertionSort(int *A, int n)
{
for (size_t i = 1; i < n; i++)
{
int v = A[i];
size_t j = i - 1;
while (j >= 0 && A[j] > v)
{
A[j + 1] = A[j];
j--;
}
A[j + 1] = v;
showArray(A, n);
}
}
void showArray(int *A, int n)
{
int *p = A;
for (size_t i = 0; i < n; i++)
{
std::cout << *p++;
if (i < n - 1)
std::cout << " ";
}
std::cout << std::endl;
}ALDS1_1_B: Greatest Common Divisor: 最大公約数
2つの数が与えられてその最大公約数を出力する問題。小さい方の数字を使って1ずつ小さくして割り切れるか試すのは時間がかかるので、ユークリッドの互除法を使うよくあるものですね。
再帰関数で実装するのがよくあるパターンですが、whileループの方が好きなのでこちらで実装しました。剰余計算では大きい数字を小さい数字で割るために2数の入れ替えを行います。
考えたこと
whileループで書くなら、終了条件を再帰関数のものと大体同じになることを意識すると書きやすいです。変数の更新には注意しましょう。
コード例
C++で実装しました。
コード例は折り畳んであります。
// greatest common divisor
#include <iostream>
int gcd(int x, int y);
int main()
{
int x, y;
std::cin >> x >> y;
int gcDivisor = gcd(x, y);
std::cout << gcDivisor << std::endl;
}
int gcd(int x, int y)
{
if (x < y)
std::swap(x, y);
while (x % y != 0)
{
int newX = y;
int newY = x % y;
x = newX;
y = newY;
}
return y;
}ALDS1_1_C: Prime Numbers: 素数
与えられた数字が素数かどうか判別する問題。1からその数字まで順に割り切れるか試すのが簡単に思いつきますが、それでは桁が大きくなると時間がかかってしまいます。この問題では$10^8$が最大なので、恐らくそのままで順番に判定するには時間が足りないでしょう。工夫を考えていきます。
考えたこと
ある数字について、自身の次に大きい約数は自身の数の高々半分です。しかしこれでは、$0.5\times10^8$回の判定なので時間は足りないかもしれません。
ここで例として、$12$の約数を考えて見ます。この約数は、$1,2,3,4,6,12$の6つであり、この並びの中で、$1$と$12$、$3$と$4$のように2数をかけて$12$になる組み合わせは中央を軸のように見ると左右対称になっています。つまり約数のうち2番目に大きなものにはそれより小さい数の組みが存在することがわかります。
また、$16$は約数が$1,2,4,8,16$の奇数個であり、この場合は中央の数字が重なっている、つまり$4$と$4$の組み合わせだと考えられます。 こうなる他の数を考えると、それは全て平方数になることが分かりますね。
この2つのことから、ある数$n$について$\sqrt{n}$以下の約数が2個あれば、その数は素数ではなく、合成数であると判定できると考えられます。これなら、最大の数$10^8$であっても判定回数は$10^4$回になり、時間切れの可能性はかなり小さくできます。
述べておくこともないですが、素数$p$の約数は$p$と$1$しかありません。
コード例
以上をもとに実装していきます。
コード例は折り畳んであります。
// Prime Numbers
#include <iostream>
#include <cmath>
bool isPrime(int n);
int main()
{
int n, anumber, count;
count = 0;
std::cin >> n;
for (size_t i = 0; i < n; i++)
{
std::cin >> anumber;
count += isPrime(anumber) ? 1 : 0;
}
std::cout << count << std::endl;
}
bool isPrime(int n)
{
if (n == 2)
{
return true;
}
int sqrtn = std::floor(std::sqrt(n));
for (size_t i = 2; i <= sqrtn; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}ALDS1_1_D: Maximum Profit: 最大の利益
株式取引でいうキャピタルゲインの計算のような問題。与えられた数字の列を時系列のように捉え、ある時点の数字とこれまでの数字の最小値との差、つまり利益が最大になるような時の利益を出力します。
考えたこと
これまでの最小値$cr$とこれまでの最大利益$cm$を保持していれば、問題なく実現できそうです。
数列の各々の数$R_t$は、$1 \leq R_t \leq 10^9$の範囲なのでループの最初に$cm := -10^{10}$として、次ループ以降に更新するようにします。門番と言われるものですね。今回はこの門番の練習といったところでしょう。
コード例
変数の命名が少し分かりづらくなってしまって反省しています。$cr$は現時点での数字の最小値です。Current Rのつもりでしたが、rminとかの方が良かったです。$cm$は現時点での利益の最大値です。Current Maxのつもりでしたが、maxProfitで良かったなと思います。
コード例は折り畳んであります。
// Maximum Profit
#include <iostream>
int main()
{
int n, r, cr, cm;
std::cin >> n;
for (size_t i = 0; i < n; i++)
{
std::cin >> r;
if (i == 0)
{
cr = r;
cm = int(-10e10);
continue;
}
if (r - cr > cm)
{
cm = r - cr;
}
if (r < cr)
{
cr = r;
}
}
std::cout << cm << std::endl;
}おわり
今回はだいぶ簡単に済みました。まとめられそうな時はなるべくまとめたいと思います。
Pythonでは割と進めていたので、見かけたような問題もありますが、とりあえずC++を多少は使えるようにしていきたいです。
Cだとゴリ押しできるとかどこかで見た気もするけど本当なのかな。。なるべくしないけど。
以上です。
Amazonアソシエイト
コメント