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

演習問題 1 (素数 - prime number)
演習問題 2 (連続する整数の和)
小テスト - 円内の格子点

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

割算の余り(剰余)の出力
自然数 j をひとつ入力して, 1 から j までの整数で j を割った余りを順番に出力するプログラム (冒頭の宣言などは省略 - 以後も)
赤色の部分が重要箇所を示している.
```
int main(void){
  char buf[80];
  int j;
  int i;
  int k;

  gets(buf);
  j = atoi(buf);
  printf("%d\n", j);
  for(i=1; i<=j; i++){
    k = j % i;
    printf("%d mod %d -> %d\n", j, i, k);
  }
}
```
繰り返しの各回ごとに出力を行うのだから, printf はループの中に置く.

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

int main(void){
  char buf[80];
  int j;
  int i;
  int k;

  gets(buf);
  j = atoi(buf);
  printf("%d\n", j);
  for(i=1; i<=j; i++){
    k = j % i;
    if(k == 0){
      printf("%d\n", i);
    }
  }
}

約数の個数を出力
個数を数える時には, そのための変数(ここでは 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);
  printf("%d\n", j);
  n = 0;
  for(i=1; i<=j; i++){
    k = j % i;
    if(k == 0){
      n = n + 1;
    }
  }
  printf("%d\n", n);
}
```

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

int main(void){
  char buf[80];
  int j;
  int i;
  int k;
  int n;

  gets(buf);
  j = atoi(buf);
  printf("%d\n", j);
  n = 0;
  for(i=1; i<=j; i++){
    k = j % i;
    if(k == 0){
      n = n + 1;
    }
  }
  if(n == 2){
    printf("prime\n");
  } else {
    printf("not prime\n");
  }
}

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

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

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

int main(void){
  char line[80];
  int i,j, sum;
  int k;

  gets(line);
  i = atoi(line);
  printf("%d\n", i);

  gets(line);
  j = atoi(line);
  printf("%d\n", j);

  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;

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

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

int main(void){
  char line[80];
  int i,j, sum;

  gets(line);
  j = atoi(line);
  printf("%d\n", j);

  for(i=1; i<j; i++){
    sum = (i+j)*(j-i+1)/2;
    printf("%d + ... + %d = %d\n", i, j, sum);
  }
}

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

入力としては, 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);
  printf("%d\n", max_j);

  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回, … というぐあい)

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

int main(void){
  char line[80];
  int i,j, sum;
  int n;

  gets(line);
  n = atoi(line);
  printf("%d\n", n);

  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 以下であるかを判定してその個数をカウントすればよい.

点(x,y)と原点との距離を求めるには平方根の計算が必要となるが, 平方根をとらなくても

x*x + y*y <= n*n

で等価な条件となる.

対象となる格子点は, x, y についての二重ループですべてを訪問できる. この場合, 繰り返しの範囲が -n から n までとなることに注意.

#include <stdio.h>

main(){
  int n, x, y, z, c;
  char line[256];

  gets(line);
  n = atoi(line);
  printf("%d\n", n);

  c = 0;
  for(y = -n; y <= n; y++){
    for(x = -n; x <= n; x++){
      z = x*x + y*y;
      if(z <= n*n){
	c++;
      }
    }
  }

  printf("%d\n", c);
}

この問題で, 円内の格子点の個数をいきなり n の多項式などでもとめようとがんばっていた人が多かったけれど, 上のプログラムのように点ひとつずつ地道に調べるのが早道.
なお, 問題にもあったとおり「(格子点の数)/(n*n)」は πに収束するはずであるから, そのような格子点の個数を整数係数の n の多項式では表現できないのではないかと思う.

また, 別解として x をひとつ決めたときに y = 「(n*n - x*x)の平方根の整数部」とするとその x での格子点の個数は y*2+1 となる. プログラムはこんな感じ:

#include <stdio.h>

int isqrt(int i){
  int r = 0;
  while(r*r <= i){
    r++;
  }
  // rがiの平方根を越えたところでループ終了
  // したがって，iの平方根の整数部は(r-1)
  return (r-1);
}

int main(){
  int n, x, y;
  int c;
  char line[256];

  gets(line);
  n = atoi(line);
  printf("%d\n", n);

  c = 0;
  for(x=-n; x<=n; x++){
    y = isqrt(n*n - x*x);
    c += y * 2 + 1;
  }

  printf("%d\n", c);
}

ここで, isqrtというのが, 平方根の整数部を求める関数である. 関数についての説明はつぎの授業で!