この記事は比較的アクセスが多いので別記事で説明したときにつかったガウスの計算方法についての動画を最初に張り付けておきますね。
さて今回はアルゴリズムの中で比較的、効果がわかりやすいガウスの計算法というものを記事にしてみたいとおもいます。
ガウスの計算法とは
ガウスの計算法とは、ドイツの天才数学者ガウスが「1 から 100 までの数字すべてを足すように」と課題を出された際に、単純に１から１００までを足していくのではなく、１と１００の和である１０１が５０個あるからだと瞬時に答えを出したというものです。
この計算法をガウスの計算法と正式にいうかわからないのですが、一般的にガウスの計算法といえば、あーあれねと通じるやつです。
ちなみにこれは数学でいうところの等差数列の和を求める公式になります。
フローチャートを書いてみる
では、普通に数字を順番に足していく計算法とガウスの計算法のフローチャートを書いてみます。
これをみると普通の計算法については、指定した数値まで順番に足していくということを繰り返す反復処理を行いますが、ガウスの計算法は順次処理で１回の計算式で終了です。というか、これは等差数列の和の公式なので厳密にはアルゴリズムには当てはまらないかもしれませんが・・・。
Scratchで作る
さてこれをScratchでつくってみました。複数のスプライト（キャラ）を使っているため一画面で処理を納めきれませんが、実行結果をキャプチャしたのがこちら。
Scratchのサイトでの共有はこちらです。
実行ボタンを押すといくつまでの数値の和を計算しますか？と聞いてくるので数値を入力すると、その数までの和をふつう犬とガウス犬が計算してくれます。最後に計算結果をそれぞれの犬が答えてくれるのですが、横にあるホイッスルくんが計算にかかった時間を言ってくれます。
10,000くらいまでの和であれば、それほど計算スピードに差はないですが、10,000,000くらいになると差が大きくなってきます。それより更に大きくなると、もう圧倒的にガウスの計算法がはやいですね。（なんたって公式に値を入れるだけだから）
Pythonでつくる
では、これをPythonでつくってみましょう。例によって入力する部分は面倒なのであらかじめ数える数値を決め打ちでプログラムに書いています。どちらも100までの数値で試してみましょう。
普通の計算法
普通の計算法はこちら
1 2 3 4 | sum=0 foriinrange(1,101): sum+=i print("合計は",sum) |
なお、range( )はかっこの中に数値を入れると、その分だけの配列を作ってくれるという大変便利な関数。ただし、以下のような形となるため今回は100まで数えたいためにrange(101)またはrange(1,101)としてやることが注意点ですね。※range(101)は0からスタートするけど0を足しても、今回のケースでは結果には影響なし。
range(10) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
range(1,10) = [ 1, 2, 3, 4, 5, 6, 7, 8, 9]
なので
range(101) = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, … ,98,99,100]
range(1,101) = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, … ,98,99,100]
ガウスの計算法
さて、お次はガウスの計算法で書いたものとなります。
1 2 3 4 | sum=0 n=100 sum= (1+n)*n/2 print("合計は",sum) |
Pythonの場合、いずれもシンプルに書けるので同じ４行で書けてしまうのですがScratchの例でみたとおり結果は一目瞭然となります。
まとめ
今回はアルゴリズムの１つとしてガウスの計算法について書いてみました。そもそも、これはアルゴリズムに分類されるものなのかというのは意見が分かれてしまうでしょうが、コンピュータに指示を与えるやり方が違えば、処理にかかる時間が大きくかわるという簡単でいい例であり、まさにアルゴリズムのツボってそこだよねってことを示せるいい例ではなかろうかというのが僕の意見です。
コメント