1から10を足すアルゴリズム

「掛け算のアルゴリズム」の参照が多いようなので、こんな単純な算法の話題もいいかと思い、今回は「1から10を足すアルゴリズム」というのを取り上げてみることにした。こんな簡単なものにアルゴリズムなんて必要なの?と思ったあなたは読まなくてよろしい。

さて、1から10を足して、それを画面に出すことを考えてみる。すると、こんな風に書けるはず。

print 1+2+3+4+5+6+7+8+9+10;
> 55

面倒なので、どんな言語でもあるような、printという画面表示のためのメソッド(命令、関数)で表示させている。「>」の右側が実際に表示された文字。さて、これで目的は達成できた。終わりである。

だがこれで終わりではこの記事の意味がない。よくあるいじわるで、今度は1から100を足して画面に出すことを考えよう。いや、もっといじわるして1から1000ではどうだろうか?上記のような方法で画面に出すことを考えてみて欲しい。

print 1+2+3+4+5+6+7+…+999+1000;
> 500500

いちおう答えは書いているが、「…」の部分をすべてタイプする人はいるだろうか。おそらくはいないと思う。ミスをするかも知れないし、1行の長さがとてつもないことになり、はたして書けるのだろうか?という制約も生まれそうだ。

ところで、もし「変数」というものの意味や使い方を知っていれば、こんな風に書くことを考える人もいるのではないだろうか。

sum = 0;
sum += 1;
sum += 2;
sum += 3;
sum += 4;
sum += 5;
sum += 6;
sum += 7;

sum += 999;
sum += 1000;
print sum;
> 500500

sumは累計値を入れる変数で、これを最初に0にしたあと、順に数を足していく(+=というのは、左辺に右辺の値を加えて新しい左辺の値とするC言語やJava言語などにある演算子である。これがない場合は、「sum = sum+1;」というように書く)。これなら、1行の長さの制約もない。ただ、1000行も、似たような行を書かなければならない。1から10000を足すなら、10000行書かなければならない。おそらく、こんなことをする人もいないだろう。

では、「こんなことするはずがない」のなら、替わりに何をするのか。そこで導入するのが「アルゴリズム」、日本語で言えば「算法」である。アルゴリズムを考えて、スムースに求める答えを得ることを考える。もちろん、ぐだぐだと長い行を書いたり、同じような行を何行も書かなくて済むように、である。

さて、上記の「sum += …」によるプログラムは、実はすでにアルゴリズムの領域に少し踏み込んでいる。なぜなら、sumという変数に、順番に1から足していく、しかも1000までね、ということをわかっていなければ、こうは書けないからだ。

ここで注目したいのは、「sum +=」の部分である。これは、各行で共通の部分だ。違うのは、右にある数値の部分である。とすると、「sum +=」を書くのは1回だけで済ませ、変わる部分をその都度書けないのだろうか、と思ったあなたは鋭い。つまり、こういうことだろうか。

sum = 0;
sum += { 1, 2, 3, 4, 5, 6, 7, …, 999, 1000 };
print sum;

あらら、最初の、1行に何でも書いてしまうというパターンに逆戻りしてしまった。しかも、書く量はたいして変わっていないぞ。さらに言えば、こんな風に書けるプログラミング言語は存在しない(おそらく)。つまり、1から1000まで足す、というのを別の何らかの方法で書いてやらなければならないのだ。

これには、たいていのプログラミング言語には構造として用意されている「繰り返し」を用いる。繰り返しとは文字どおり、同じようなことを何度も繰り返すことだ。繰り返しの回数とか、繰り返す内容を指定してやる。繰り返しの回数とは、繰り返しの条件だったりする。一般的には、こんな風に書く。

while(繰り返し条件)
  繰り返すこと

この記事のお話しは、繰り返しの構造を詳しく説明することではないので飛ばしてしまうと、「繰り返し条件」と「繰り返すこと」をうまく決めてあげれば、1から10000までを足すことが簡単にできるのではないか?と思うだろう。

ここで、先ほどの「sum +=」を思い出して欲しい。これは、べた書きした場合でも必ず出てくる、共通の部分である。とすると、これを「繰り返すこと」に入れればいいのではないだろうか。

sum = 0;
while(繰り返し条件)
    sum +=;
print sum;

何とも不完全であるが、こういうのは徐々に埋めていけばよろしい。「sum +=」の右は、1から10000の間で変化するのだということは、今までの展開からわかる。変化する値を扱う場合には、「変数」を使う。sumと同じである。これは意外と言い切られないことで、「変化する値には変数」という当たり前のことを押さえておく。

これを踏まえると、こうなる。

sum = 0;
while(繰り返し条件)
    sum += x;
print sum;

変数には、xを用いてみた。数学などでも変数はx, y, zなので、わかりやすいだろう。ここは、単なる呼び名なので、何でもよい。xを1から10000の間で変化させてあげればよい、ということになる。

さて、「1から10000の間で変化」というくだりは、「xを1から始めて、1を加えながら、10000まで」といったことに等しい。とすると、最初に「xを1にする」ということをまず追加する。

sum = 0;
x = 1;
while(繰り返し条件)
    sum += x;
print sum;

「1を加えながら」はどうするか?ここで冒頭のコードを思い出せば、変数xを使うパターンをべた書きすればこんな風になるんじゃないかと思うだろう。

sum = 0;
x = 1;
sum += x;
x += 1;
sum += x;
x += 1;
sum += x;
x += 1;
sum += x;
x += 1;
………
print sum;

こうなれば、こんな風に書けることは容易に想像がつく。

sum = 0;
x = 1;
while(繰り返し条件)
    sum += x;
    x += 1;
print sum;

最後の「10000まで」はどうするか?これは、「xが10000以下の間」というようにできるだろう。実は、この「xが10000以下の間」というのを表現するのが、繰り返しを作るときにはもっとも難しいのだ。

sum = 0;
x = 1;
while(x<=10000)
    sum += x;
    x += 1;
print sum;

「<=」は、「左辺が右辺以下」といった比較のための演算子である。数学記号の≦を上下分けて書いたようなものだ。

実は、疑似プログラムとしてはこれで完成である。whileのカッコの中の10000を別の数にすれば、いくらでも大きな数までの総和を求めることができる。また、「x = 1;」の右辺である1を変えれば、「いくらからいくらまでの総和」というのも簡単に求めることができる。さらに、「x += 1;」の右辺の1を変えれば、「いくらからいくらまでの総和をいくら刻みに」みたいな感じにもできる。このとき、プログラムを大きく書き換える必要はない。部分的に数字を書き換えるだけである。ここが非常に重要だ。

ちょっと無理な展開かな?というような気もするが、あえて簡単な問題を長々と書いてみた。こういう風に書いているプログラミングの本は存在しまい(ページのムダだからだ)。だが、繰り返しを作るとき、何を共通にして、何を可変にするか、といった目の付け所のヒントのようなものにはなるのではないかな?と思った。

コメント