初心者のC言語とアルゴリズム

初心者のためのC言語とアルゴリズムの解説

AOJ ALDS_1_C: PrimeNumbers

今日はAOJのALDS_1_Cの問題を解きます。 問題は以下のリンク先にあります。

Prime Numbers | Aizu Online Judge

問題は入力の中にある素数の個数を求めるものです。 まず、素数について簡単におさらいしましょう。 素数とは、約数として1とその数自身のみしか持たない自然数のことですね。

上記のことから与えられた整数xに対する簡単なアルゴリズムは、xをfor文を用いて2~x-1の数で割ってみるということが考えられます。しかし、これではxが大きくなるにつれて計算量も大きくなってしまいます。

ここではもう少し工夫して問題を解いていきましょう。 皆さんも考えてみてください。 解答は以下のようになります。

f:id:ginkgonut0:20170620234238p:plain

ここではエラトステネスの篩というアルゴリズムを用いました。 エラトステネスの篩の特徴は以下のようになります。

  1. 2以上の整数を考える
  2. 最小値の2を残し、その倍数を消去する
  3. 次に残った値の最小値の3を残し、その倍数を消去する
  4. 以下は同様に5, 7, 9と繰り返す

また、問題や問題のサイズによっては整数を配列に保持しておくことで、プログラムがより良くなります。

ALDS1_1_B: Greatest Common Divisor

今日は前回に続き、ALDS1_1_Bの問題を解いていきたいと思います。 問題のリンクを以下に貼っておきます。

最大公約数 | アルゴリズムとデータ構造 | Aizu Online Judge

前回はソートアルゴリズムでした。ソートアルゴリズムは重要なのでしっかり理解しましょう。 今回は最大公約数を求める問題であり、数学的な思考が要求されます。 実装は以下のようになります。

f:id:ginkgonut0:20170619225322p:plain

このプログラムの中で return y ? gcd(y, x % y) : x; の部分はいくらか複雑かもしれません。 これは以下のプログラムを再帰関数により再現したものと考えてもらえれば理解しやすいと思います。

f:id:ginkgonut0:20170619225814p:plain

このアルゴリスム(計算方法)はユーグリッド互除法と呼ばれるものです。 ユーグリッド互除法に関する数学的証明は省略させていただきます。 気になる方は検索してみてください。 自分で考えて見るのも良い勉強になると思います。

AOJ(会津オンラインジャッジ)のALDS問題を解く

初めまして。 記念すべき初投稿です。 記念と言っても、私にしかあまり関係ありませんね(笑)。

今回からC言語を用いてAOJのADSL問題を解いていきたいと思います。 以下はAOJへのリンクとなります。

AIZU ONLINE JUDGE: Programming Challenge

オンラインジャッジを利用する理由は、解答の正誤判定がとても簡単に行えるからです。 自分でサンプルの入力などを作ったりするのは正直めんどくさいですね。

では、今回はADSL1_1_A Insertion Sort問題を解いていきましょう。 問題はリンク先を開き、COURSE→Algorithms and Data Structure I → Getting Started → Insertion Sortの順で見ることができます。 ユーザー登録などは不要です。(オンラインジャッジを利用するためには登録が必要です。)

解答は以下のようになります。 f:id:ginkgonut0:20170618192008p:plain

これは問題文にも擬似コードが書かれているので特に問題はないのではないでしょうか。 計算量はO(N2)になります。また、挿入ソートは離れた要素を直接変更することはないので、安定なソートアルゴリズムとなります。