16進数字列を整数値に変換する関数。

たとえば、16進数字列 “A4C” → 値 2636。

<関数名>
  hexsz2int —- 16進数字列を整数値に変換する

<形式>
  int hexsz2int(char *str);

<引数>
  str 16進数ASCIZ文字列
  先頭に符号(+/-)が入ってもOK。各桁は0〜9、A〜F、または、a〜f。

<関数値>
  16進数字列に相当する整数値(10進数)

<注意事項>
  整数のオーバーフローに注意。

用例
  hexsz2int(“B6119”);

<関数本体>
  hexsz2int.c

<説明>
  16進数字列の先頭から、まずホワイトスペースを読み飛ばす。つぎに符号を処理し、16進数字の各桁を変換していく。各桁の 変換においては、0-9、A-F、a-fのような場合分けを考慮する。

多くのデータから、最大値、または、最小値を求める関数。

たとえば、5個のデータ 1 6 3 8 7 では、最大値は 8、最小値は 1、といった具合。

<関数名>
  maxmin —- n個のデータから最大値および最小値を求める

<形式>
  void maxmin(int *max, int *min, DATA *data, int nmem);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  max  (出力) キーの値が最大のレコード配列の番号(先頭番号は 0)
  min  (出力) キーの値が最小のレコード配列の番号(先頭番号は 0)
  data  (入力) レコード配列
  nmem (入力) レコード配列の大きさ

<関数値>
  なし

<用例>
  maxmin-test.c

<関数本体>
  maxmin.c

<説明>
  最も簡単なやり方は、最初 n-1 回の比較で最大値 max を見つけ、つぎに残りの n-1 個のデータから n-2 回の比較で最小値 min を見つける方法だ。この場合、計 2n-3 回の比較が必要。
  一方、関数のように、n 個のデータを半分ずつに分け、その各々のグループより最大最小を見つけたとすると、全体の最大値は2つの最大の大きいほう、全体の最小値は2つの最小の小さいほうとなる。この操作を再帰的に各グループの要素が2つになるまで行う。この場合、比較回数は 3/2n – 2 であり、上記の単純比較法のそれよりも小さい。
  ご利用には、データ構造を実際の問題に合わせて修正してほしい。

必ず知らないといけない、ソート・アルゴリズムのひとつ。

最悪の計算時間はO(n2)だが、平均計算時間はO(n log n)。他のソート法と比べて、最も高速だといわれているが、安定ソートではない。また、クイックソートの欠点は、順序よく並んだデータでは極端に遅くなってしまう。

<関数名>
  quickSort —- クイックソート

<形式>
  void quickSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  quickSort-test.c

<関数本体>
  quickSort.c

<説明>
  C. A. R. Hoare (ホア) によるクイックソート(quick sort)は、平均的に最も速いソートアルゴリズムだといわれている。クイックソートでは、昇順ソートの場合、
  1. 適当な値 x を選ぶ。その際、配列の x 以下の要素の数と x 以上の 要素の数とはなるべく同程度になるようにする。
  2. x 以下の要素を配列の前半に、x 以上の要素を配列の後半に集める。
  3. 配列の前半が要素数が2以上なら、配列の前半を再帰的にクイック ソートする。
  4. 配列の後半が要素数が2以上なら、配列の後半を再帰的にクイック ソートする。
  このように、配列をつぎつぎに2つにして、それぞれについてソートを行う。
  ご利用の際、データ構造を実際の問題に合わせて修正して欲しい。

ソート・アルゴリズムの一つで、挿入ソートを改良したもの。

データを数個とびに拾い集めて挿入ソートをかけ、次第にソートする要素の間隔を詰めていき、最後に単純な挿入ソートで完全にソートさせる。

大幅に離れた2つのデータを一気に交換することで交換回数を減らし、高速化をはかったアルゴリズムだが、クイックソートなどに比べると若干速度は落ちる。

ちなみに、シェルの名はアルゴリズムの考案者 D.L.Shell の名前に由来する。

<関数名>
  shellSort —- シェルソート

<形式>
  void shellSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  shellSort-test.c

<関数本体>
  shellSort.c

<説明>
  挿入ソートが遅いのは、隣の要素同士しか交換しないからである。たとえば、最小の要素がたまたま最後にあった場合は、それを最初に移動させるにはN回の比較と交換かかる。シェルソートは、挿入ソートのの拡張として、遠く離れている要素の間でも交換するように高速化をはかったものだ。
  そのアイデアとしては、h要素分だけ離れた要素同士をまずソートし、h の値をだんだん小さくしながらソートを繰り返す。最後には、h=1でソート。

もっとも基本的なソート・アルゴリズムの一つ。別名 インサーションソート (Insersion Sort)。

まず、並んだデータのうち最初の2つを取り出し比較し、望む順序(昇順か降順)に並べる。次に、3つ目のデータをソートした2つと順に比較し、適切な位置に挿入する。4つ目以降も同様にして、ソート済みの列の適切な位置に一つずつ挿入していく。

与えられたデータがソート済み状態に近ければ比較的高速だが、要素が逆順に並んでいると遅くなってしまう。この欠点をある程度緩和した改良版に、これから紹介する シェルソート がある。

ちなみに、挿入ソートは人間がもっとも簡単に行えるソート方法だといわれている。

<関数名>
  insertSort —- 挿入法によるソート

<形式>
  void insertSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;    /* 比較のキーとなるフィールド */
    int info;    /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  insertSort-test.c

<関数本体>
  insertSort.c

<説明>
  挿入ソートでは、すでにソート済のレコードに新しいレコードを正しい場所に挿入する。つまり、最初の2つのレコードについてまず入れ換えにより正しい順序にする。つぎに、3つ目のレコードを前の2つのレコードと比較して、必要に応じて入れ換えを行う。これで、3つのレコードが正しい順序になる。このように最後のレコードまで繰り返す。
  挿入ソートは人間のよくやるソート法であり、ブリッジでカードを並べるときにもよく使う方法。
  本関数を利用するには、データ構造を実際の問題に合わせて修正して欲しい。

多くのソートアルゴリズムの中で、直感的に最も理解しやすいのは、バブルソートといわれている。バブルとは「泡」のことで、並べ替えの過程でデータが下から上へ移動する様子が、泡が浮かんでいくように見えることからこの名前がついたらしい。

<関数名>
  bubbleSort —- バブル法によるソート

<形式>
  void bubbleSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;   /* 比較のキーとなるフィールド */
    int info;   /* その他のフィールド */
  } DATA;
  data (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  bubbleSort-test.c

<関数本体>
  bubbleSort.c

<説明>
  縦方向一列に並んだレコードの中で、値の小さいレコード(昇進の場合)は軽く、泡(バブル)のように上に浮かんでいく、というようにイメージすれば分かりやすい。
  まず下から全体を走査して、隣接する2つのレコードの大小順序が狂ったとき、2つを入れ換える。この走査で、一番値の小さい(軽い)レコードが1番上に浮かびあがる。つぎに下から上2つ目のレコードまで走査して隣り同士を必要に応じて入れ換えることにより、その中の最小のものが上から2つ目のレコードに浮かびあがる。このように最後のレコードまで繰り返して終了。
  ご利用の際、データ構造を実際の問題に合わせて修正してほしい。

ソート (sort、整列) とは、データをある規則に従って並び替えることをいう。例えば、英語辞書は頭文字のアルファベット順にソートされている。

また数字を小さいものから大きいものに並べることを、昇順という。例: 1, 2, 3, 4, 5。
逆に、大きいものから小さいものまでの並び方を、 降順という。例: 5, 4, 3, 2, 1。

文字になるとややこしくなる。考え方としては、文字の内部コード(コンピュータ内の文字コード、例えばアスキーコードとか)を基準にソートすることが多いが、必ずしも常識と一致しないこともあるので、ご注意を。

なお、漢字のソートとなると、読み方が複数あるので、漢字の代わりに読み方でソートすることがほとんど。ということで、実際のソートは数字以外だと、結構大変。現場のひとによく聞いて、そこのルールに従うしかないかも。

ソートのプログラムに、速度の遅いもの、複雑ですが高速なもの、動きの安定するもの、色々なアルゴリズムが考え出されている。アルゴリズムの良し悪しを考えるのにいい素材になると思う。

プログラマとして食っていくには、多くのアルゴリズムを習得しないといけないし、アルゴリズムの良し悪しをご自分で判断できることも大切。判りやすくて高速なものがあれば万万歳だが、世の中はそうはあまくない。

さて、まずは選択ソートの関数。別名 セレクションソート(Selection Sort)。

<関数名>
  selectSort —- 選択法によるソート

<形式>
  void selectSort(DATA *data, int nmem, int asdes);

<引数>
  typedef struct {
    int key;   /* 比較のキーとなるフィールド */
    int info;   /* その他のフィールド */
  } DATA;
  data  (入出力) データレコードの配列
  nmem (入力) レコード配列の大きさ
  asdes (入力) 昇順・降順別、0:昇順, 1:降順

<関数値>
  なし

<用例>
  selectSort-test.c

<関数本体>
  selectSort.c

<説明>
  選択ソートでは、まず全体を走査して最小のレコード(昇順の場合) を見つけ、それを最初のレコードと入れ換える。つぎに2つ目のレコードから最後まで走査してその中の最小のものを見つけ、2つ目のレコードと入れ換える。このように最後のレコードまで繰り返して終了。
  ご利用の際、データ構造を実際の問題に合わせて修正してほしい。


日食、黒い太陽ともいう。それを信仰する、黒い太陽教もあると聞く(笑)。

地球からみて、太陽が月の背後に隠された天体現象。地球、月、太陽の相対位置により、皆既食、金環食、部分食の三つあるらしい。

日食は新月のときにしか起きないが、月と地球との軌道面が傾いているため合致する機会が少なく、年数回しか起きない。しかも、月食と違って観測できる場所がきわめて限られる。

本プログラムは日食の時刻を表示してくれる。正しく計算できるかな。

<プログラム本体>
eclipse.c —- 最大日食の時刻計算

<入力>
求めたい年(西暦年)

<出力>
計算した、最大日食の時刻表示(分まで)

実行例

<注意事項>
関数 solarPos()太陽の位置計算)、および、関数 lunarPos()月の位置計算) が必要。
また、関数 ut2jd()ユリウス日への換算)、jd2ut()ユリウス日からの換算)も必要。

<説明>
年の365(または366)日に対し、太陽と月の黄径をそれぞれ計算し、互いにもっとも近く、さらに、月の黄緯が0に近い時刻、を求める。
なお、日付は日本標準時に修正してある。海外では1日ずれることもある。

日食時刻
2000年 2月 5日 20時25分
7月 2日  8時59分
7月31日  8時 3分
12時26日 2時24分
2001年 6月21日 21時 0分
12月15日 5時49分
2002年 6月11日 8時48分
12月 4日 16時36分
2003年 5月31日 13時22分
11月24日 8時 1分
2004年 4月19日 22時22分
10月14日 11時50分
2005年 4月 9日 5時33分
10月 3日 19時30分
2006年 3月29日 19時17分
9月22日 20時47分
2007年 3月19日 10時53分
9月11日 21時46分
2008年 2月 7日 12時45分
8月 1日 19時14分
2009年 1月26日 16時55分
7月22日 11時36分
2010年 1月15日 16時12分
7月12日  4時42分


太陽、地球、月、の3天体が一直線上にあり、月が地球の影にはいってみえなくなる現象を、月食という。満月のときにのみ起きる。

月食の回数は日食より少ないが、一地点で見える回数は月食のほうが多い。満月のたびに月食が起きないのは、月の軌道面と地球の軌道面が若干傾いているためで、最大年3回しか起きないそうだ。

本プログラムは月食の時刻を教えてくれるもの。果たしてうまくいくか、実際にその日にならないと判らないかな。

<プログラム本体>
lunarEclipse.c —- 最大月食の時刻計算

<入力>
求めたい年(西暦年)

<出力>
計算した、最大月食の時刻表示(分まで)

実行例

<注意事項>
関数 solarPos()太陽の位置計算)、および、関数 lunarPos()月の位置計算) が必要。
また、関数 ut2jd()ユリウス日への換算)、jd2ut()ユリウス日からの換算)も必要。

<説明>
年の365(または366)日に対し、太陽と月の黄径をそれぞれ計算し、その差が180度にもっとも近く、さらに、月の黄緯が0に近い時刻、を求める。
なお、日付は日本標準時に修正してある。海外では1日ずれることもある。

月食時刻
2000年 1月21日 13時42分
7月16日 22時57分
2001年 1月10日  5時26分
7月 6日  0時 6分
2003年 5月16日 12時37分
11月 9日 10時16分
2004年 5月 5日  5時35分
10月28日 12時10分
2005年10月17日 16時14分
2006年 3月15日 13時36分
9月 8日  8時 7分
2007年 3月 4日  8時18分
8月28日 19時37分
2008年 2月21日 12時31分
8月17日  6時18分
2010年 6月26日 20時31分
12月21日 17時14分

満月とは、真丸に輝く月のこと。地球からみて太陽と反対方向になったときの月。つまり、月の黄径と太陽の黄径との差が180度になったときだ。

満月の夜、なんとなく、ロマンチックに感じるのが私だけかな。

このプログラムでは満月の日を教えてくれる。デートの予約に利用できるかも(笑)。

<プログラム本体>
  fullMoon.c —- 満月の日の計算

<入力>
  求めたい年(西暦年)
  
<出力>
  計算した、満月の日の画面表示

実行例

<注意事項>
  関数 solarPos()太陽の位置計算)、および、関数 lunarPos()月の位置計算) が必要。
  また、関数 ut2jd()ユリウス日への換算)、jd2ut()ユリウス日からの換算)も必要。

<説明>
  年の365(または366)日に対し、太陽と月の黄径をそれぞれ計算し、その差が180度にもっとも近い日を満月の日とする計算。
  なお、日付は日本標準時に修正してある。海外では1日ずれることもある。
  プログラムをさらに精度よく計算させれば、満月となる時刻まで正確に求められるかも。

  満月の日(2003年版、12回)
  1/18、 2/17、3/18、4/17、5/16、6/14、7/14、8/12、9/11、10/10、11/9、12/9。

  満月の日(2004年版、13回)
  1/8、 2/6、3/7、4/5、5/5、6/3、7/2、8/1、8/30、9/28、10/28、11/27、12/27。

ちなみに、ネット上に 満月カレンダー のようなものは結構見かける。