演習(第二回)・小テスト(2)の解答例

1. 割算の余り(剰余)の出力
   自然数 j をひとつ入力して, 1 から j までの整数で j を割った 余りを順番に出力するプログラム (冒頭の宣言などは省略 - 以後も)

   赤色の部分が重要箇所を示している.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
   
     gets(buf);
     j = atoi(buf);
     for(i=1; i<=j; i++){
       k = j % i;
       printf("%d %% %d = %d\n", j, i, k);
     }
   }
   

   繰り返しの各回ごとに出力を行うのだから, printf はループの中に置く.

2. 約数だけを出力
   ループの中で条件に合う場合だけ処理を行なうことが要点.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
   
     gets(buf);
     j = atoi(buf);
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         printf("%d\n", i);
       }
     }
   }
   

3. 約数の個数を出力
   個数を数える時には, そのための変数(ここでは n)を用意して, 初期値ゼロを与えておく. あとは, 条件が成立した場合だけ n = n + 1 (これは n++ と書いても同じ) を行なうことで, ループが終了した時点での個数が n に残る.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     n = 0;
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         n = n + 1;
       }
     }
     printf("%d\n", n);
   }
   

4. 素数かどうかを出力
   前のプログラムで, ループ終了時の約数の個数がふたつ(1と自分) であることを判断しているだけ.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     n = 0;
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         n = n + 1;
       }
     }
     if(n == 2){
       printf("%d is prime\n", j);
     } else {
       printf("%d is not prime\n", j);
     }
   }
   

5. 計算の手間を改善 (余裕があれば, の問題)
   
   • 1 で割って割り切れるのは自明なのでやらない
   • j の平方根以下の約数がないなら, それより大きな約数もないはず.
     j の平方根を計算するのは面倒なので「i の二乗が j 以下である」という条件に 置き換えている(これなら四則計算でできる).
   • j が奇数の場合, 偶数の約数を持つことはありえない.
     偶数か奇数かの判断を最初にやってしまうことで, 奇数を 2 で割ってみるという無駄な計算を省いている.
   こうすると, 素数の場合には n が 0 でループを抜けるはずなので, それで判定することにしてある.

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     if(j % 2 == 0){		/* 偶数の場合 */
       if(j == 2){  /* 偶数の素数は 2 のみ */
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     } else {			/* 奇数の場合 */
       n = 0;
       for(i=3; (i*i)<=j; i += 2){
         /* 除数の範囲を, 3 から j の平方根までの奇数に限定 */
         k = j % i;
         if(k == 0){
   	n = n + 1;
         }
       }
       if(n == 0){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     }
   }
   

   さらに, 割り切れる場合がひとつでも見つかったらその先を計算しないプログラム. 「break文」は教科書 P.201 に説明があるが, 現在実行中のループから イキナリ脱出して次に進むためのものである. (この例は一重のループだが, 多重のループの場合には, 一番内側のループから脱出する.)

   int main(void){
     char buf[80];
     int j;
     int i;
     int k;
     int n;
   
     gets(buf);
     j = atoi(buf);
     if(j % 2 == 0){		/* 偶数の場合 */
       if(j == 2){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     } else {			/* 奇数の場合 */
       n = 0;
       for(i=3; (i*i)<=j; i += 2){
         /* 除数の範囲を, j の平方根までの奇数に限定 */
         k = j % i;
         if(k == 0){
   	n = n + 1;
   	break;			/* 割り切れたらfor文から脱出 */
         }
       }
       if(n == 0){
         printf("%d is prime\n", j);
       } else {
         printf("%d is not prime\n", j);
       }
     }
   }
   

前の問題同様, 段階的に考えてみる.

1. i から j までの連続する整数の和
   

   int main(void){
     char line[80];
     int i,j, sum;
     int k;
   
     gets(line);
     i = atoi(line);
   
     gets(line);
     j = atoi(line);
   
     sum = 0;
     for(k=i; k<=j; k++){
       sum = sum + k;
     }
   
     printf("%d + ... + %d = %d\n", i, j, sum);
   }
   

   等差数列の和の公式を使ってsumを一気に計算するなら, 赤色の部分は

     sum = (i+j)*(j-i+1)/2;
   

   とすればよい. (そしてこちらの方が繰り返しがないぶん高速)

2. j は入力して, i の方を 1 から (j-1) まで変化させるプログラム

   int main(void){
     char line[80];
     int i,j, sum;
   
     gets(line);
     j = atoi(line);
   
     for(i=1; i<j; i++){
       sum = (i+j)*(j-i+1)/2;
       printf("%d + ... + %d = %d\n", i, j, sum);
     }
   }
   

   合計の計算は等差数列の和の公式を使うことにした.

3. 入力としては, j の上限となる値を与え, i と j のすべての組み合わせに ついて「連続和」を求めるプログラム
   二つの変数のすべての組み合わせを処理するには, 二重のループを用いる. ここでは, 外側のループで j を変化させ, その j に対して内側のループで i を変化させている.

   int main(void){
     char line[80];
     int i,j, sum;
     int max_j;
   
     gets(line);
     max_j = atoi(line);
   
     for(j=1; j<=max_j; j++){
       for(i=1; i<j; i++){
         sum = (i+j)*(j-i+1)/2;
         printf("%d + ... + %d = %d\n", i, j, sum);
       }
     }
   }
   

   外側のループでは j は 1 から max_j まで変化し, 内側では外側の j がひとつきまったときに i を 1 から (j-1) まで変化させる. つまり, 内側のループをまわる回数は毎回異なる. (j が 1 のときは0回, j が 2 のときは1回, … というぐあい)

4. そもそもの問題をとくプログラム.
   前のステップの連続和がちょうど n になる時だけ出力すればできあがり.

   int main(void){
     char line[80];
     int i,j, sum;
     int n;
   
     gets(line);
     n = atoi(line);
   
     for(j=1; j<=n; j++){
       for(i=1; i<j; i++){
         sum = (i+j)*(j-i+1)/2;
         if(n == sum){
   	printf("%d + ... + %d = %d\n", i, j, sum);
         }
       }
     }
   }
   

与えられた数 n を 2 からの順次の整数 i で割っていく. 割れた場合には, n を割り算の結果に更新し, i はそのままでさらに割ってみる. 割れなかった場合には, i を次の整数に進める. 割っていくにつれて n は次第に小さくなっていき, 最後の素因数で割ると 1 になる. これが繰り返しの終了条件である.

n がそもそも素数だった場合, 一度も割り切れることなく i がどんどん大きくなる. いずれ i が n と等しくなったときにはじめて割り切れて, 結果は 1 になって無事終了.

#include <stdio.h>

int main(void);

int main(void)
{
  int	n, i;
  char buf[256];

  gets(buf);
  n = atoi(buf);

  i = 2;
  while(n > 1){
    if(n%i == 0){
      printf("%d\n", i);
      n = n / i;
    } else {
      i = i + 1;
    }
  }
  return(0);
}