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

演習問題 1 (素数 - prime number)

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);
     }
   }
   

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. 素数かどうかを出力
   前のプログラムで, ループ終了時の約数の個数 n が 2 (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. 計算の手間を改善
   
   • j の平方根以下の約数がないなら, それより大きな約数もないはず.
   • j が奇数の場合, 偶数の約数を持つことはありえない.
   j の平方根を計算するのは面倒なので「i の二乗が j 以下である」という条件に 置き換えている(これなら四則計算でできる). また, 偶数か奇数かの判断を最初にやってしまうことで, 奇数を 2 で割ってみるという無駄な計算を省いている.

   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;
         }
       }
       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);
       }
     }
   }
   

演習問題 2 (連続する整数の和)

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

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);
       }
     }
   }
   

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);
         }
       }
     }
   }
   

小テスト

1. まず, 与えられた数の約数の個数を求める処理. これは演習問題1で解決済みで, その部分を取り出すとこんな感じ: (ここでは, j の約数の個数を n に求めている)

     n = 0;
     for(i=1; i<=j; i++){
       k = j % i;
       if(k == 0){
         n++;
       }
     }
   

2. 次に, j を一定範囲で変えながら, 最大の n を持つ場合を捜し出す.
   順に計算を繰り返して, 最大の場合を求めるためには, 「それまでの最大の値」(つまり「暫定トップ」ですな)を 記録する変数(max_n)を新しくひとつ用意して, 初期値としては「ありえないくらい小さい値 -- ここでは -1」を入れておく. あとは, ループの中で求まった結果(ここでは約数の個数 n)とその「暫定トップ」を 比較して, 記録が更新された場合にはその処理を行なえばよい. ループをすべて終了すれば, 最大値が求まっている.

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

   ループ中での一回の結果と「暫定トップ」を比較する際に, ここでは > を用いている. もし同じ最大値が複数あった場合には, この比較によれば最初に出現したものが優先することになる. 比較として >= を用いれば, 最後の出現が優先される.