アルゴリズム(ガウスの足し算)

電卓のボタン拡大プログラム

さて今回はアルゴリズムの中で比較的、効果がわかりやすいガウスの計算法というものを記事にしてみたいとおもいます。

ガウスの計算法とは

ガウスの計算法とは、ドイツの天才数学者ガウスが「1 から 100 までの数字すべてを足すように」と課題を出された際に、単純に1から100までを足していくのではなく、1と100の和である101が50個あるからだと瞬時に答えを出したというものです。

ガウスの計算方法

この計算法をガウスの計算法と正式にいうかわからないのですが、一般的にガウスの計算法といえば、あーあれねと通じるやつです。

ちなみにこれは数学でいうところの等差数列の和を求める公式になります。

 

フローチャートを書いてみる

では、普通に数字を順番に足していく計算法とガウスの計算法のフローチャートを書いてみます。

ガウスの計算法フロー

これをみると普通の計算法については、指定した数値まで順番に足していくということを繰り返す反復処理を行いますが、ガウスの計算法は順次処理で1回の計算式で終了です。というか、これは等差数列の和の公式なので厳密にはアルゴリズムには当てはまらないかもしれませんが・・・。

 

Scratchで作る

さてこれをScratchでつくってみました。複数のスプライト(キャラ)を使っているため一画面で処理を納めきれませんが、実行結果をキャプチャしたのがこちら。

ガウスの計算法Scratch

Scratchのサイトでの共有はこちらです。

https://scratch.mit.edu/projects/337723111/

 

実行ボタンを押すといくつまでの数値の和を計算しますか?と聞いてくるので数値を入力すると、その数までの和をふつう犬とガウス犬が計算してくれます。最後に計算結果をそれぞれの犬が答えてくれるのですが、横にあるホイッスルくんが計算にかかった時間を言ってくれます。

10,000くらいまでの和であれば、それほど計算スピードに差はないですが、30,000くらいになると差が大きくなってきます。それより更に大きくなると、もう圧倒的にガウスの計算法がはやいですね。(なんたって公式に値を入れるだけだから)

なお、かかった時間は厳密にはスタートボタンを押してから結果が返るまでの時間です。そのため、いくつまでの数にしようかなと悩んでいる時間もカウントされてしまっています。これを改善するため、単純に実行時間だけを出すために途中でタイマーをリセットする等の操作も試みてみたのですが、ガウスの計算法では、即答えがでるため0秒と出てしまい、あまりうまくいきませんでした。そんなわけでタイマーについては、スタートボタンを押してからの時間でとらえてください。

 

Pythonでつくる

では、これをPythonでつくってみましょう。例によって入力する部分は面倒なのであらかじめ数える数値を決め打ちでプログラムに書いています。どちらも100までの数値で試してみましょう。

普通の計算法

普通の計算法はこちら

sum = 0
for i in range(1, 101):
    sum += i
print("合計は",sum)

なお、range( )はかっこの中に数値を入れると、その分だけの配列を作ってくれるという大変便利な関数。ただし、以下のような形となるため今回は100まで数えたいためにrange(101)としてやることが注意点です。

range(10)    =  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

range(1,10) =  [ 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

ガウスの計算法

さて、お次はガウスの計算法で書いたものとなります。

sum = 0
n = 100
sum =  (1+n)*n/2
print("合計は",sum)

Pythonの場合、いずれもシンプルに書けるので同じ4行で書けてしまうのですがScratchの例でみたとおり結果は一目瞭然となります。

 

まとめ

今回はアルゴリズムの1つとしてガウスの計算法について書いてみました。そもそも、これはアルゴリズムに分類されるものなのかというのは意見が分かれてしまうでしょうが、コンピュータに指示を与えるやり方が違えば、処理にかかる時間が大きくかわるという簡単でいい例であり、まさにアルゴリズムのツボってそこだよねってことを示せるいい例ではなかろうかというのが僕の意見です。

コメント

タイトルとURLをコピーしました