*

アルゴリズム

ソートアルゴリズム

ソートアルゴリズム

  1. バケットソート
    最大値の個数分バケツを用意し、そこにデータを格納して並べ替えを行う
  2. 基数ソート
    数字の各桁に着目して、桁ごとに順番にデータの並べ替えを行う
  3. 単純選択法
    データの中から最小値(または最大値)を見つけ出して、先頭(または末尾)のデータと交換する
  4. 単純交換法(バブルソート)
    隣り合うデータ同士を比較して、大小関係が正しくなるように入れ替える。
  5. 単純挿入法
    対象のデータをデータの並び順の大小関係が正しくなる位置に挿入する。
  6. シェルソート
    ソート対象データ列を一定の個数にグループ分けして並べ替える。
  7. マージソート
    ソート対象データ列を分割していき、再度併合(マージ)することで並べ替える。
  8. クイックソート
    データ列から任意の数を選び、その値との大小で2分割することを繰り返して並べ替える。
  9. ビープソート
    ヒープ構造を利用して並べ替える。

 

最大公約数

最大公約数は、ユークリッド互除法で求める

ユーリッド互除法の定理

整数XとY(X≧Y)を与えたとき、XをYで割った時の余り(剰余)をRとすると、XとYの最大公約数は、YとRの最大公約数と等しい。

ただし。Xと0との最大公約数はXとする。

 

整数XとY(X≧Y)の最大公約数を変数GCDに求める

手順

  1. 変数RにX÷Yの剰余(余り)を代入
  2. 変数Rが0でない間、以下の手順3~5を繰り返す
  3. 変数Xに変数Yの値を代入する
  4. 変数Yに変数Rの値を代入する
  5. 変数RにX÷Yの剰余(余り)を代入する
  6. 変数GCDに変数Yの値を代入する