プロのプログラマーを目指して、経験や知識を共有するブログです。ご参考になれば。。
最大公約数を探すアリゴリズム。
XをYで割った時の剰余をRとすると、XとYの最大公約数は、YとRの最大公数に等しい
XをYで割った時の剰余をRとすると、
XとYの最大公約数は、YとRの最大公数に等しい
この定理を利用し、
R=0となるまで、YとRを変えながら、探す。
X ≧ Y とする。
1. X÷Y を Rとする
2.R が0 でない間、3から5を繰り返す
3.XにYを代入
4.YにRを代入
5.X÷Y を Rに代入
6.R=0となった時のYが最大公約数
総当たりアルゴリズム すべての場合をためし、解を求める。 近似アルゴリズム ・正解に近い解を探す ・正解との誤差がある範囲におさまると保証されているものを 精度保証付アルゴリズムという。 ・精度の保証のないアルゴリズムを、発見的手法(ヒューリスティック) という。
0 件のコメント:
コメントを投稿