^284）総和を求める関数

1からnまでの公差が1の数列の総和を、ガウスの公式n(n+1)/2とfor文の累積加算のどちらで求めるか、というアンケートを見かけた。ぼくは計算量の少なさからガウスの公式を推したい。ガウスの公式なら値に関係なく計算量は常に一定だが、for文や再帰関数だと少なくともn回分の計算量が必要になるからだ。

しかし、ガウスの公式にも欠点がある。それは桁あふれが起きやすいことだ。なぜなら、計算時にnの2乗を挟むので、その時点でint型の上限を超える可能性があるからだ。対策として、nかn+1のうち偶数になる方を先に2で割ったり、戻り値の型をlongにする、などが考えられる。

// ガウスの公式
// nかn+1のうち、偶数を先に2で割る
static int getSumGauss(int n)
{
  if (n % 2 == 0) {
    return (n / 2) * (n + 1);
  } else {
    return ((n + 1) / 2) * n;
  }
}

ただし、文末に書いたよう、なんでも数学知識で書けばよい、という訳でもないし、for文の方が、公差を変えたり総乗（総積）に変更するのが簡単だ。

// 初項1が公差が2の等差数列の第n項までの積を返す
static long getProductDiff2(int n)
{
  long product = 1;
  for (int i=1, d=2; i <= n*d; i+=d) {
    product *= i;
  }

  return product;
}

総和は、ガウスの公式やfor文以外でも求めることができる。たとえば、再帰関数があげられる。でも、総和は計算する回数が決まっているので、再帰にする意味は薄い。

// 再帰関数
static int getSumRcv(int n)
{
  if (n > 0) {
    return n + getSumRcv(n - 1);
  }
}

変わり種なら、総和の結果のテーブルを用意する、printf関数の引数に式を書いてコンパイル時に計算させる、なんて方法も考えられる。次のコードは、printfの引数に1からnまでの総和の式を作成する。

// printfの引数に総和の式を作成し表示する
static void makePrintfSum(int n)
{
  printf("printf(\"%%d\\n\", ");
  for (int i = 1; i <= n; i++) {
    if (i == n) {
      printf("%d", i);
      break;
    }
    printf("%d + ", i);
  }
  printf(");\n");
}

for文や再帰関数を使った総和の計算は、あくまでも構文を覚えるための題材で、それがいつのまにかアルゴリズムとして定着してしまったのだろう。まあそれぞれの特徴が分かっていれば、どの書き方でもいいと思う。

ちなみに、単純な総和の計算だからガウスの公式を選択しただけで、難しいなら別の書き方を選ぶ。たとえば、各項が直前の4項の和であるテトラナッチ数列の第n項の値を返す関数なんて、for文以外で書けないし、そもそも何も思いつかない。

// テトラボッチ数列の第n項の値を返す
static long getTetranacciNumber(int n)
{
  if (n < 1)  return -1; // 1項未満はエラー値を返す
  if (n < 4)  return 0;
  if (n == 4) return 1;

  long *t = malloc(sizeof(long) * n);
  long result;

  t[0] = 0; t[1] = 0; t[2] = 0; t[3] = 1;

  for (int i = 4; i < n; i++) {
    t[i] = t[i-1] + t[i-2] + t[i-3] + t[i-4];
    result = t[i];
  }

  free(t);

  return result;
}

$ ./a.out 70
3661260108881759077

もし、テトラナッチ数列の値を漸化式に合わせて再帰関数で書くと、スタックが四重に必要になるので処理速度がとっても遅いと思う。というわけでプログラムにおいては無条件に数学知識を披露すればよい、という話ではないのだ。以前、似た話をしたことを思い出した（「プログラミングに理系知識は必要か」）

2023-09-18