アルゴリズムとデータ構造
演習第 1 回
イントロダクション

最初の演習では C 言語の復習も兼ねて、簡単なアルゴリズムのプログラム を作成します。C 言語を忘れてしまった人は、頑張って思い出しながら プログラムを書いてみてください。

問題１ ［印刷用 PostScript］

(1) 以下のそれぞれの ISBN について、検査数字（? になっている部分） を計算しなさい。

• ISBN: 4-08-858734-?
• ISBN: 4-08-872271-?

(2) 次の空欄を埋めて、3 x 3 の魔方陣を完成させなさい。

(1) は ISBN のエラーチェックに関する問題です。 ISBN は全部で 10 桁あり、9 桁目までが実際のコードで、 最後の一文字は検査数字と呼ばれ、 他の数字が間違っていないかのチェックに使われます。 検査数字は、1 桁目の数字に 1 を掛け、 2 桁目の数字に 2 を掛け、……、9 桁目の数字に 9 を掛け、 それらを全部足した合計を 11 で割った余りです。 ただし、余りが 10 になった場合は X と表記します。

例えば、4-08-873104 という ISBN の検査数字は 2 になります。

ISBN についての詳細は、
ISBN とバーコード
http://muse.cc.kurume-it.ac.jp/home/general/sibhome/isbn/isbnindex.html
を読んでみてください。

(2) は魔方陣（≠魔法陣）に関する問題です。 魔方陣は、縦、横、対角線上の数字の合計が同じになる並びをしています。

N x N の魔方陣の場合、合計は (N³+N)/2 になるはずなので、そうなるように魔方陣を埋めてください。

実行例１:
% ./a.out
Input ISBN:  4 0 8 8 7 3 1 0 4
Check Number:  2

実行例２:
% ./a.out
Input ISBN:  4-08-873104
ISBN => 4-08-873104-2

実行例１の方では、検査数字が 10 になっても、 そのまま 10 と出力してしまって構いません。 また、この実行例１では入力の際に、数字をスペースで区切っています。 こう入力することにより、scanf 関数の %d で 一文字ずつ読み込むことができます。

実行例２では、文字（文字型）を数字（整数型）に変換したり、 数字（整数型）を文字（文字型）に変換したりする必要があるので、 そこで混乱しないように注意してください。

実行例２は入力に数字以外の文字が混ざっているため、scanf 関数の %c で文字として読み込むと良いでしょう。 （%d はうまく使えない）。 読み込んだ文字が数字（'0'〜'9'）以外ならば無視し、 数字ならば atoi 関数などを使って整数型に変換しなければなりません。 ある文字が数字かどうかを調べるには、isdigit という標準関数が便利です。

また、実際の ISBN に近い形式にするには、読み込んだ文字をすべて配列などに とっておき、計算した検査数字を文字に（10 ならば X に） 変換する必要があります。

実行例：
% ./a.out
   4   3   8
   9   5   1
   2   7   6

いくつか方法を紹介しておくので、参考にしてください。

総当たり

力技で全通りを試していきます。単純に考えても 9!=362880 通りで、 プログラムでは 9 重ループになります。このくらいならば、 現在のコンピュータではそんなに時間はかかりません。 すべての解を求めるわけではないので、最初にひとつ見つけた時点で 表示して終了してしまって良いです。

乱数を使う

乱数を用いて適当に数字を配置し、それが魔方陣になっているかを 調べます。これを魔方陣が見つかるまでひたすら繰り返します。

公式を使う

奇数 x 奇数の魔方陣には一般解が存在します。その公式を調べて、 それを使っても構いません。