解答2.1

POSIXでは整数型変数のサイズ毎の最大値と最小値は limits.hというヘッダファイルに CHAR_MIN, CHAR_MAXなどとして定義されている. Uで始まるのは符号なし型の最大値である(最小値はすべて0)

#define CHAR_MIN (-128)
#define CHAR_MAX (127)
#define UCHAR_MAX (255)
......

プログラムで最大値/最小値を求めるにはオーバフローを利用する.
変数値を1ずつ増やして行った場合、最大値を越えるとオーバフローが発生し、 値が0に戻る. すなわち増加前の値より小さくなるのでそれを検出すればよい.

ただしlong intやlong long intに同じアルゴリズムを適用すると、 (数億回のループになるため)非常に時間がかかる. 加算をシフトに変更すれば数回で終了するが、 その場合の最大値はold_xでもxでもなくx-1である点に注意する必要がある.

printfの引数を修正するのを忘れないこと. long intの場合は"%ld", long long intならば"%lld", 符号なしの場合は"d"を"u"に変える必要がある.

なおC99ではinttypes.hを読み込むことで、 特定のビット幅をもつ整数型の利用と 表示指定ができるようになった. 例えば32ビット符号付きならそれぞれint32_t,PRId32である.

#include <inttypes.h>
int32_t x;
......
printf("max=%" PRId32 "\n", x-1);

解答2.2

既に解答2.1で使用しているとおり、オーバフロー、アンダフローは エラーメッセージも何も表示されない. 0除算は実行時エラーとなり、 プログラムはそこで終了する.

除数が定数の場合に限り、コンパイル時に警告を発生する環境もある. ただし除数が0であっても変数の場合は警告を発生しないので、 除数の検査はプログラマの責任である.

int a = 3/0; // 警告
int b = 0;
int c = 3/b; // 警告なし

解答2.3

int main() {
    int n;
    do {
      scanf("%d", &n);
      if (n==0) 
        printf("end\n"); 
      else if (n==1)
        printf("invalid input\n"); 
      else 
        printf("%d\n", prime(n)); 
    } while (n>0);
    return 0;
}

breakを削除するのを忘れるとdo-whileループを終了してしまうので注意

解答2.4

どちらも繰り返しの条件が正しくないのが誤動作の原因である.

1. iの初期値がnなので、n%n==0が常に成立しすべて素数でないと判定される.

(修正) int i=n ⇒ int i=n-1

2. n%(++i)==0 は余りを判定する前にiを1増加させる. iの初期値は2なので、
   最初の判定時にiは3になっている. このため3が素数でないと判定される.

(修正) n%(++i)==0 ⇒ n%(i++)==0
    while (i<=n)⇒ while (i<n)

解答2.5

hi,mi,loに8桁ずつ格納する. あとは乗算時に繰り上がりの処理を行えばよい.
この問題ではkは20以下なので、各桁の値は8桁の最大値(99999999)でも 乗算結果はintの最大値(約21億)を越えない.

実行結果は

% ./fact3
20
000002432902008176640000

同様に30の階乗を求めるには変数を4個使用する. この場合は関数mul中の乗算でオーバフローの可能性があるので、 unsigned intを利用して約42億まで扱えるようにする.

実行結果を最後の5行だけ示す.

26:00000403291461126605635584000000
27:00010888869450418352160768000000
28:00304888344611713860501504000000
29:08841761993739701954543616000000
30:65252859812191058636308480000000

ちなみにint(符号付き)のままだと27の階乗を計算中にオーバフローする.
(1の位が4になるので明らかに間違いだとわかる)

26:0000040329146112660563134284000000
27:0001088886945041835204494198850304
28:003048464234461129423857258803691520
29:088405174240288437425952076507054080
30:652154944254601516423157136811622400

3章で学習する配列を使用することでさらに大きな数の階乗も計算できるが、 その場合でもオーバフローに注意すること. 乗算のみ64ビットで行い、結果を8桁ずつ配列に 格納するのが安全である.

解答2.6

アで再開したいのは外側のyのループであるが、 外側ループ先頭へのcontinueは直接記述できないので、 一旦内側のxのループを脱出させる. このときif文が成立したことを記録する変数fを用意して、 正常にxのループが終了した場合と区別する. このような変数をフラグと呼ぶことがある. ループ先頭でフラグのクリアを忘れないこと.

int foo(int n) {
   int x,y;
   int c=0;
   for(y=1;y<=n;y++) {
/*イ*/ int f=0;
       for (x=1;x<=n;x++) {
           if (x+y == n)
/*ア*/        { f=1; break; }
           c++;
       }
       if (f) continue;
       printf("%d ", c);
   } 
   printf("\n");
   return c;
}

なお任意の場所に無条件分岐するgoto文もあるが、 処理の流れがわかりにくくなるので なるべく使用しないのが望ましい. 複雑な処理はいくつかの補助関数に分割するなどして、 理解しやすいプログラムを作成するように心がけること. この例ではxのループを分離して以下のようにすればよい.

int foosub(int y,int n) {
   int c=0;
   for (x=1;x<=n;x++) {
       if (x+y == n) return c;
       c++;
   }
   return c;
}

int foo(int n) {
   int x,y;
   int c=0;
   for(y=1;y<=n;y++) {
     c += foosub(y,n);
     printf("%d ",c);
   }
   printf("\n");
   return c;
}

解答2.7

最初に行の数を入力する. 1から100までの範囲になければエラーとする
あとは1行ずつ整数を入力するが、途中でファイル終了(EOF)に達したら エラーメッセージを出力する. 合計と平均の計算は本文中で説明したとおり.

解答2.8

xCrを計算する部分を関数とする. これは内部で自分自身を呼び出す再帰関数である.
再帰関数には再帰を止める(=これ以上再帰しなくなる)条件分岐文が 1つ以上必要である. この例ではrが0かxの時は1を返す.

関数mainの中の#ifdefは結果をカラーで出力する場合の処理である. 方法は環境に依存するが、ほとんどのPOSIX互換環境では 17-18行目の"\x1b"で始まる特殊な 文字列(エスケープシーケンス)を出力することで、 文字と背景の色を変更できる. 23行目は文字と背景の色を元に戻す文字列である.

なおこのアルゴリズムは再帰の回数が指数関数的に増加するため、 nが大きくなると極端に遅くなる(n=30の場合、2GHzのCPUでも数分).
3章で学習する配列(2次元配列)を使用して、 一度計算したxCrの値を配列C[x][r]に保持するようにすれば 劇的に改善される(1秒以下). 各自試してみよ.