トップサイトへ

アルゴリズム比較

1）鶴亀算

課題

つるとかめの合計と足の合計からそれぞれの数をもとめる解き方について
方法１

すべてがウサギと仮定した場合、足の数の和に差が生じ、これはウサギと亀の足の数の差の２本から生まれたものである。よって、この足の数の差を２で割れば亀の数を求めることができるというプログラム
方法２

ウサギの数を１とすると、ウサギと亀の足の数の和は４×１＋２×亀の数になる。そこで、ウサギを２、３，４・・・進めていき、足の数の和が一致するところを見つけるプログラム

2）自然数の和

課題

自然数１からＮまでの自然数の和を求める解き方について
方法１

１＋２＋３・・・（ｎ－２）＋（ｎ－１）＋ｎ
式の通りに順番に足していくというプログラム
方法２

「１から１００までの自然数を足すといくつになるか計算しましょう。」という問題に対してガウス少年が先生を驚かせた計算方法

１＋２＋３・・・（ｎ－２）＋（ｎ－１）＋ｎ
ｎ＋（ｎ－１）＋（ｎ－２）・・・３＋２＋１
------------------------------------------------
（ｎ＋１）＋（ｎ＋１）＋（ｎ＋１）　
　・・・　（ｎ＋１）＋（ｎ＋１）＋（ｎ＋１）

上記のように、式を入れ替えて足すとｎ＋１がｎ個できるので、目的の自然数の和は2で割ると求めることができるというプログラム

３）最大公約数

課題

２つの数の最大公約数を求める解き方について
方法１

最大公約数は小さい方の数を越えることがないので、小さい数から始めて、１つずつ減らしていった数で２つの数を割る。それぞれ割ったときの余りが両方とも０になるまで繰り返して見つけるプログラム
方法２

大きい方の数を小さい方の数で割って余りを求め、この余りで小さい方の数を余りで割る。このことを余りが０になるまで繰り返して見つける（ユークリッド互除法）プログラム

４）並べ替え

課題

データを小さい順に並べ替える方法について
バブルソート

データの先頭から順に、隣り合う2つの要素を比較して、大小が逆になっていたら交換する。ことを最後まで繰り返して整列させるプログラム
挿入ソート

先頭から２つの要素を比較して小さい方を先頭に、大きい方を2番目に置く。次に3番目の値を取り出し、先頭・2番目と順に比較し、適切な位置に挿入する。4番目以降を同様にして最後まで繰り返して整列させるプログラム

5）検索

課題

条件に合う数を見つけ出す方法について
線形検索

検索値とリスト内のデータを先頭から順番に比較していき、一致するデータを見つけるプログラム
二分検索

リストの中から検索範囲を半分ずつ狭めながら目的のデータを見つけるプログラム