プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか? ITエンジニアに贈る、アルゴリズム入門。
「アルゴリズムって何?」。そう聞かれて、皆さんはすぐに答えられますか。ウィキペディアのアルゴリズムの項には、「なんらかの問題を解くための手順のことである」と記載されています(2007年9月時点)。
例えば、皆さんが週末に京都に旅行し、市内を観光するとしましょう。二条城や銀閣寺、東寺など、回りたいと思う観光地がいくつもあります。バスや電車、場合によっては徒歩など複数の交通手段のうち、どれを使ってどういう順番で回れば効率が良いかと考え、時刻表と格闘することになるでしょう。
この場合、観光地の効率の良い回り方が「問題」で、すべての観光地を最短時間で移動する経路を見つけ、効率良く回る手順を考えることが「問題を解くための手順」、すなわちアルゴリズムになります。
同じ問題でも解き方によって、解くまでにかかる時間が変わってきます。やり方によっては、100倍・1000倍の速度の違いが出てきます。この1000倍の差をハードウェアで吸収しようとすると、1000台のPCがあっても実現できないでしょう。やり方を考えるだけでそんなにも早く解けるなんて、面白いと思いませんか?
この連載では3回にわたって、皆さんに身近な問題からアルゴリズムに触れてもらいたいと思います。
皆さんがコンピュータに何かの処理をさせたいと思ったら、そのためのプログラムを書くことになりますね。でも、実際にプログラムを書く前に、まずどういったフローで処理させるかを考えると思います。
100個の数字を小さい順に並べたければ、ソートをしようと思うでしょう。環境によっては、コンピュータ言語がすでに並べ替えのための仕組みを持っていることがありますね。SQLであれば「order by」、CやJavaであればソート用の関数やAPIが使用できるでしょう。しかし、そういった言語の支援が受けられない場合はどうすればいいでしょうか。自分で並べ替えの方法を考えて、プログラムを書く必要があります。
例えば、遊び終わったトランプを並べ替えることを考えてみましょう。スペードのエースを先頭に、スペードの2、3と続いてキングまで、次にダイヤのエースからキングまで、クラブのエースからキングまで……というようにきれいに並べてしまっておこうと思ったら、どうやって整理しますか。52枚のカード(ジョーカーを除く)の山からスペードのエースを探して抜き出し、次にスペードの2のカードを抜き出し……という方法もありますし、7並べのようにあらかじめ各カードを置く場所を決めておき、そこにカードを当てはめていくといった方法もありますね(図1)。
これがトランプの並べ替えのアルゴリズムです。いま挙げた2つ以外にも方法はあるでしょうが、この2つの方法だけ見ても、並べ替えにかかる手間(時間)と必要なスペース(メモリ)は違うはずです。イメージはできましたでしょうか?
実際のアルゴリズムについて考えてみましょう。ここでは加減乗除を例として挙げます。
四則演算ができないちょっと変わったコンピュータがあったとします。でもこのコンピュータは、ある数値に+1をすることはできます。このコンピュータで2つの数字を加減乗除させる必要が出てきた場合、どういう処理をさせますか?
足し算をさせようと思ったら……。例として「5+3」を考えてみましょう。最初の5を読み込み、これに+3をするためには、+1を3回繰り返せばいいですね。
次に引き算です。「5−3」は、−3に+1することを5回繰り返せばいいのです。
掛け算と割り算は、それぞれ足し算・引き算を繰り返すと考えます。掛け算は足し算のアルゴリズムを使って、5を3回足し合わせます。割り算は、同様に引き算のアルゴリズムを使って、5から3を何回引けるかと考えます。
というわけで、+1という処理ができれば、四則演算は可能であるということが分かりました。
以下は、このアルゴリズムをC言語とJavaで表したものです。
C言語#include <stdio.h> |
import java.io.*; |
Copyright © ITmedia, Inc. All Rights Reserved.