2014 年度「計算数学」 2014-12-19

§12.1 多倍長計算

(12.1.1) 工夫をして, 普通では計算機で扱えないような大きな整数などを扱うことを 「多倍長計算」という(らしい)。

(12.1.2) この授業では, int 型の配列に十進の一桁ずつを収める方法を用いる。 ここのパソコンの int 型には±約 21 億までの数を格納できるので, これはものすごく無駄の多いやり方である。 が,その分,プログラムは書きやすいと思う。

(12.1.3) 一つのプログラムでは同じ長さの配列だけを扱うので, #define DIGITS 10 と桁数を決める。 10 桁あれば,ここのパソコンの int 型に格納できる正の整数は格納できる。 課題では,実は int 型で扱える自然数だけを扱うので, 課題5を済ませるまでは桁数は 10 でよい。 配列 a[ ] には, a[0] に一の位を, a[1] に十の位を, a[2] に百の位を,……として整数を格納する。

(12.1.4) 関数 void num2str(int a[ ], int n) は, n の値を,上で述べた方式で長さ DIGITSint 型の配列 a[ ] に格納するもの, 関数 void printstr(int a[ ]) は長さ DIGITSint 型の配列 a[ ] に格納された数を画面に出力するもの,とする。 これらを書け。 初めは,12345 を出力する際 0000012345 となってもよいが, それが書けたら 12345 とだけ出力されるようにせよ。

(12.1.5) また,これらをテストする main() を書け。 キーボードから int 型に数を読み込み, それを num2str() で配列に入れ, printstr() で画面に出力してみればよい。 (最後には改行を出力するほうがよいだろう。)

(12.1.6) num は number を, str は string を短くしたものである。 2 は英語の to の意。 string は本来は文字列を意味するが,ここでは数字列の意味で使おう。

#include <stdio.h>

#define DIGITS 10

    /* 関数のプロトタイプ宣言をここに置く */

int a[DIGITS];

main() {
    /* 自分で本体を書く */
}

void num2str(int a[ ], int n) {
    /* 自分で本体を書く */
}

void printstr(int a[ ]) {
    /* 自分で本体を書く */
}

§12.2 【課題5】 足し算・引き算

(12.2.1) 関数 void add(int a[ ], int b[ ]) は 配列 a[ ] に格納された数に配列 b[ ] に格納された数を足す関数, 関数 void sub(int a[ ], int b[ ]) は 配列 a[ ] に格納された数から配列 b[ ] に格納された数を引く関数, とする。これらを書き足せ。 足し算で桁あふれする場合,引き算で結果が負になる場合,のことは考えなくてよろしい。 小学校のころを思い出して下の桁から計算してゆくのだが, くり上がり,くり下がりを覚えておく変数が必要になろう。 英語では carry, borrow というらしい。

(12.2.2) 正しく書けたかどうかを確認するための main() も書け。 二つの数を入力させ, 一方では「普通に足し算・引き算をして答えを出力」し, 他方では「配列に収めてから add(), sub() で足し引きしてその結果を printstr() で出力」するものを書けばよい。

(12.2.3) メールは,必ず,この授業で配布したアカウントから送れ。 メールの本文冒頭に, 学籍番号,名列番号,氏名(として大学に届けてあるもの)を忘れずに書け。 次に,レポートの内容を, 「多倍長計算で和と差を求める」程度に, 簡潔に書け。

(12.2.4) その次に,プログラムを載せよ。 その際,Active! mail のメール作成画面の「添付ファイル」 *ではなく* 本文の中にソースファイルを貼りつけること。

(12.2.5) 今回は実行結果は不要である。かかった時間を計る必要はない。

(12.2.6) 宛て先は私(岩瀬)の実習用アカウント((1.9.7) 参照)である。 件名は「?? kadai5」(←全て半角文字,小文字, ?? は自分の id の下二けた,その後ろに半角スペース一つ, kadai5 の間にはスペースを入れない)とせよ。

§12.3 課題5が終わったら

(12.3.1) 1234567890 はここのパソコンの int 型で扱えるが, その十倍は扱えない。 DIGITS を 11 に変更し, この数を二つ足したもの,三つ足したもの,……,十個足したもの, を出力するプログラムを書けば, ここのパソコンの int 型では扱えない数の計算をしたことになる。 (実は double 型に格納して扱うことができるが。)

§12.4 掛け算・割り算(課題ではない)

(12.4.1) 関数 void mul(int c[ ], int a[ ], int b[ ]) は配列 a[ ] と配列 b[ ] に格納されている数の積を配列 c[ ] に格納するものとする。 これを書け。 桁あふれのことは考えなくてよい。 配列 c[ ] の外に書き込まないように注意せよ。 また,この関数を確認するための main() を書け。

(12.4.2) 一つのアイディアを述べる。 12345 × 6789 だったら, 5 × 9, 5 × 80, ..., 2000 × 700, ..., 10000 × 6000 などを計算しなければならない。 これらを一つずつ int 型の配列に格納し, add() を使って足してゆく。

(12.4.3) この関数を利用し,100 の階乗を正確に計算するプログラムを書け。 DIGITS はかなり大きくしておかねばならないだろう。

(12.4.4) 関数 void div(int r[ ], int q[ ], int a[ ], int b[ ]) は 配列 a[ ] に格納されている数を配列 b[ ] に格納されている数で割り, 配列 q[ ] に商を,配列 r[ ] に余りを格納するものとする。 これを書け。 0 で割る場合,答えは不定でよいものとする。 また,この関数を確認するための main() を書け。

(12.4.5) 一つのアイディアを述べる。 98765 ÷ 432 なら,432 を 2 だけ左へシフトして 43200 とし,これと 98765 の大小を比べる。 前者のほうが大きいので,商として 100 をたて, 98765 から 43200 を引く。 これを引けなくなるまでくり返し, 次は 432 を 1 だけ左へシフトしたものを考える。

(12.4.6) 配列 b[ ] に格納された数を配列 a[ ] にコピーする関数 void strcopy(int a[ ], int b[ ]), 配列 a[ ] に格納された数と配列 b[ ] に格納された数を比較し, 前者が大きければ正の数,後者が大きければ負の数,等しければ 0 を返す関数 int comp(int a[ ], int b[ ]) を書いておくと楽かも。

(12.4.7) 100 の階乗を 1, 2, 3, ..., 100 で順にくり返し割ってゆくプログラムを書け。

(12.4.8) 二項係数 nCr を, nr が大きな数の場合にも計算するプログラムを書け。


岩瀬順一