アルゴリズムとデータ構造レポート

大学 programing C/C++

初レポート。内容は

  1. C言語でリスト構造を作れ
  2. C言語で整数環を作れ

というもの。

リスト

リストは以前作った事があるので、よく分かる。双方向リンクリストを実装した。
でも、来週からはSchemeを授業でやるらしいけど、LISPのリスト構造にしてみた方が良いのかも。
そうすると、例えばforやwhileは使わず再帰を使って実装したほうが美しい。
純LISPというものは

  1. car
  2. cdr
  3. cons
  4. atom
  5. eq

の５つのみからなり、チューリング完全らしい。
この5種類だけで例えばi番目の要素を取り出す等の演算を実装してみると面白いかも。
この場合算術演算が使えない。というか整数型が無い。
で、集合と位相の授業で習ったけど
nilが0,(nil)が1,((nil) nil)が2, (((nil) nil) nil)が3
等として整数を定義できるとか言ってた気がする。(だったかな？)
a + 1 => (cons a nil)
a - 1 => (car a)
a == 0 => (eq a nil)
みたいな感じか。
でもCの構造体として実装するんだからいちいち整数を指定するのにcons(cons(cons(...), ...), ...)とか書いてらんない。
そのうちSchemeインタプリタ実装するらしいし面白いと思ったけどやめとこ。

整数環

整数環とは

  1. 加法が閉じている。零元、逆元がある。
  2. 結合則を満たす乗法がある。
  3. 加法と乗法について分配法則が成り立つ。

ものらしい。
これを作れって事は多倍長整数演算を実装せよって事だろうな。(まだやってない)

んで、これをCで作れと？？まじですか？？
Cでコード書くなら

big_integer a, b, c;
a = bi_zero(); /* 零元 */
b = bi_init("でかい整数。文字列で指定");
c = bi_minus(b); /* 逆元 */
assert(a == bi_add(b, c));
...
assert(bi_mul(a, bi_mul(b, c)) == bi_mul(bi_mul(a, b), c)); /* 乗法の結合則 */
assert(bi_mul(a, bi_add(b, c)) == bi_add(bi_mul(a, b), bi_mul(a, c))); /* 分配法則 */

見たいなコードを書けってことか？正直言って見た目がヤバイ。
C++使って演算子オーバーロードしちゃいけないのだろうか...