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

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

問題1印刷用 PostScript

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

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

(2) は魔方陣(≠魔法陣)に関する問題です。 魔方陣は、縦、横、対角線上の数字の合計が同じになる並びをしています。
魔方陣の例
N x N の魔方陣の場合、合計は (N3+N)/2 になるはずなので、そうなるように魔方陣を埋めてください。

問題2

ISBN の検査数字を計算するプログラムを作成しなさい。

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

余裕があれば、次のように余計な文字が入力されても無視し、結果は実際の ISBN に近い形式で出力するようにしなさい。

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

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

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

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

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

問題3

3 x 3 の魔方陣をひとつ出力するプログラムを作成しなさい。 魔方陣を作る方法は、どんな方法でも良い。 ただし、プログラム中の配列などに結果を埋め込み、それを表示するだけ、 というのは禁じ手とする。

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

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

総当たり

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

乱数を使う

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

公式を使う

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


Written by わかまつなおき