西暦2400年はうるう年？ うるう年じゃない？：いまから始めるアルゴリズム（3）（1/2 ページ）

プログラミングの基礎となる考え方、アルゴリズムを理解しているだろうか？ ITエンジニアに贈る、アルゴリズム入門。

[鹿野恵祐，＠IT]

　連載第1回「『＋1』だけで四則演算をするには？」、第2回「ソート処理時間、選ぶアルゴリズムでこんな差が！」で、プログラミングにおけるアルゴリズムの重要性と面白さを紹介しました。

　最終回となる今回は、皆さんの身近にあるアルゴリズムとして、「うるう年」と「素因数分解」を取り上げてみたいと思います。

2000年問題って何だっけ？

　2000年問題という言葉、昔よく聞きましたね。西暦1999年から2000年になるに当たって発生した問題のことです。

　いまから20年以上前のコンピュータでは、プロセッサは8bitや16bitであることが多く、メモリも数Kbytes、多くて数Mbytesと、現在のものに比べて非力でした。そこでプログラミングにおいても、実行速度を稼ぐためのさまざまな工夫がされていました。なんとかデータを軽くしようと、上位部が変わらないものであれば省略して下位部のみを扱ったり、処理も極力省略したりしていたのです。

　例えば、西暦の4けたのうち上位2けたを省略することで、2bytes分のメモリ量や記憶領域を節約することができました。「1976」は「76」、「1989」は「89」として扱っていたのです。

　このことは、西暦1999年から2000年に移り変わるに当たり、どういう問題を引き起こすでしょうか？

　「1982,1993,1988,1997,1992,1999,2000,2001」というデータがあったとします。上位2けたを省略すると「82,93,88,97,92,99,00,01」になります。

　小さい順での並べ替えを行うと「00,01,82,88,92,93,97,99」となり、期待した「1982,1988,1992,1993,1997,1999,2000,2001」とはまったく異なる結果になってしまいます。元のデータに「19xx」と「20xx」が混在していたためです。

　これでは、最小値から最大値の範囲を算出しようとしたとき、1982年から2001年までの「19」年のつもりが、1900年から1999年までの「99」年になってしまいます。例えば銀行預金の利息の計算を行うときなど、こういう問題があっては結果が正しく出ませんね。

元のデータ	「1982,1993,1988,1997,1992,1999,2000,2001」
上位2けたを省略したデータ	「1982,1993,1988,1997,1992,1999,2000,2001」
実際の結果 （上記データの並べ替え結果）	「00,01,82,88,92,93,97,99」
本来、意図した結果 （元データの並べ替え結果）	「1982,1988,1992,1993,1997,1999,2000,2001」

うるう年は4年に1度？

　2000年問題というと、上記の問題を連想することが多いと思います。しかし2000年には、実はもう1つ「うるう年」という問題がありました。

　ご存じのとおり、うるう年にはうるう日として、ほかの年には存在しない2月29日があります。このため、うるう年に対応していないプログラムでは、月次処理・日時処理に問題が発生する可能性があります。月末処理が28日に行われてしまい、29日の売り上げが3月に含まれてしまうなどです。

　そんな大事なうるう年を、コンピュータに正しく判定させてみましょう。

　現在、日本を含む各国では「グレゴリオ暦」という暦が採用されています。グレゴリオ暦でのうるう年の定義は、

1. 4で割り切れる年はうるう年
2. ただし、100で割り切れる年は平年
3. ただし、400で割り切れる年はうるう年

となっています。

　例えば、1980年は4で割り切れるので、1の条件を満たしていてうるう年の可能性があります。次に2と3の条件で判定を行うと、100でも400でも割り切れません。これで1980年はうるう年であることが分かりました。

　同様に、1900年・2000年・2100年を判定してみましょう。1900年と2100年は1と2の条件を満たしますが、3の条件は満たさないため平年です。2000年は、1と2と3の条件を満たすため、うるう年ということになります。

		1900	2000	2100
条件1	4で割り切れる？	YES	YES	YES
条件2	100で割り切れる？	YES	YES	YES
条件3	400で割り切れる？	NO	YES	NO
平年orうるう年？		↓	↓	↓
		平年	うるう年	平年

　上記の例のように、100の倍数の年でもうるう年である場合とない場合があります。2000年当時、3の条件を考えず、2000年を平年として取り扱っているプログラムが存在していたため、2000年2月29日にはいくつかの大きな問題が起きました。

　私が実際に目にしたプログラムのパッチにも、修正内容として「うるう年の問題に対応した」と記載されているものがありました。実装として上記3つが網羅されていなかったのかもしれませんし、判定のロジックが間違っていたのかもしれません。

　このように、プログラムを作ったときには想像もしていなかった、もしくはそれほど問題にはならないだろうと考えていたことが、大きな障害になることもあります。作ったプログラムが長く動き続けたとき、どういった問題が起きる可能性があるかをできるだけ考えておくと、将来のトラブルを未然に防ぐことにもつながります。

このアルゴリズムを基に作成したソースファイルのダウンロード（C・Java）