最大公約数の計算__C++
6447 ワード
てんかいそうほう
数学では、転々とした相殺法は、ユークリッドアルゴリズム(英語:Euclidean algorithm)とも呼ばれ、最大公約数を求めるアルゴリズムです.転々相除法はユークリッドの「幾何学の元」(第VII巻、命題iとii)に初めて登場し、中国では東漢に現れた「九章算術」にさかのぼることができる.
転がり相除算は、2つの整数の最大公約数が、その中の小さい数と2つの数の差の最大公約数に等しいという原理に基づいている.
アルゴリズムの計算プロセスは次のとおりです.
kは、ステップ数(0からカウント)を示す各ステップの入力が、いずれも前2回計算した非負の剰余rk 1およびrk 2であるとする.各ステップで算出される残数は減少し続けているため、rk−1はrk−2より小さい.ステップkにおいて、アルゴリズムは、rk 2=qk*rk 1+rkのうち0≦rk実装コードは次のとおりです.
転がり相減算転がり相減算(最大公約数を求める)、すなわちニコマンチェス法は、一連の減算を行い、最大公約数を求めるのが特色である.
しかし、私にとっては転々と相殺する「引き算」版のような気がします.
具体的には、次のようになります.
貧挙法貧挙法はすべての可能性のある結果を2つの数の中から1つずつ減らし、2つの数で除算された残数が0を満たすかどうかを検証するために持ち込み、一致する最初の数字を見つければ最大公約数となり、最も非効率的で暴力的な方法と言える.
具体的には、次のようになります.
具体的なコードは次のとおりです.
コンパイル実行環境はVisual Studio 2017
以上のアルゴリズムと比較して、非常に大きな数字の最大公約数計算を行う場合、steinアルゴリズムはより効率的なアルゴリズムであり、具体的なアルゴリズムの概念と流れは参考にすることができる.http://blog.csdn.net/kemlkyo/article/details/22698597
参考資料:wikipediahttps://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95#.E6.9C.80.E5.A4.A7.E5.85.AC.E7.BA.A6.E6.95.B0
数学では、転々とした相殺法は、ユークリッドアルゴリズム(英語:Euclidean algorithm)とも呼ばれ、最大公約数を求めるアルゴリズムです.転々相除法はユークリッドの「幾何学の元」(第VII巻、命題iとii)に初めて登場し、中国では東漢に現れた「九章算術」にさかのぼることができる.
転がり相除算は、2つの整数の最大公約数が、その中の小さい数と2つの数の差の最大公約数に等しいという原理に基づいている.
アルゴリズムの計算プロセスは次のとおりです.
kは、ステップ数(0からカウント)を示す各ステップの入力が、いずれも前2回計算した非負の剰余rk 1およびrk 2であるとする.各ステップで算出される残数は減少し続けているため、rk−1はrk−2より小さい.ステップkにおいて、アルゴリズムは、rk 2=qk*rk 1+rkのうち0≦rk
//
int C_commondivisor::div_alg(m_num1, m_num2)
{
int tmp1 = m_num1;
int tmp2 = m_num2;
for (; tmp1 % tmp2 != 0; )
{
tmp1 = tmp1 % tmp2;
//tmp1 tmp2 ，tmp1
// ， tmp1
tmp1 = tmp2 - tmp1;
tmp2 = tmp2 - tmp1;
tmp1 = tmp1 + tmp2;
}
return tmp2;
}転がり相減算転がり相減算(最大公約数を求める)、すなわちニコマンチェス法は、一連の減算を行い、最大公約数を求めるのが特色である.
しかし、私にとっては転々と相殺する「引き算」版のような気がします.
具体的には、次のようになります.
//
int C_commondivisor::phase_sub()
{
int tmp1 = m_num1;
int tmp2 = m_num2;
for (; tmp1 - tmp2 != 0; )
{
tmp1 = tmp1 - tmp2;
// ， tmp1
if (tmp2 > tmp1)
{
tmp1 = tmp2 - tmp1;
tmp2 = tmp2 - tmp1;
tmp1 = tmp1 + tmp2;
}
}
return tmp2;
}貧挙法貧挙法はすべての可能性のある結果を2つの数の中から1つずつ減らし、2つの数で除算された残数が0を満たすかどうかを検証するために持ち込み、一致する最初の数字を見つければ最大公約数となり、最も非効率的で暴力的な方法と言える.
具体的には、次のようになります.
//
int C_commondivisor::exhaustion()
{
// ， ， ， ，
int i = 0;
for (i = m_num2; i <= m_num2; i--)
{
// ， ，
if ((m_num1 % i) == 0 && (m_num2 % i) == 0)
{
break;
}
}
return i;
}具体的なコードは次のとおりです.
コンパイル実行環境はVisual Studio 2017
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
// : commondivisor.cpp
// : EL.Gou
// : 2017.03.21
// : Visual Studio 2017
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include
using namespace std;
class C_commondivisor {
public:
C_commondivisor();
int input(); //
int output(int i); //
int mainmenu(); //
int div_alg(); //
int phase_sub(); //
int exhaustion(); //
private:
int m_num1;
int m_num2;
int m_result; //
};
C_commondivisor::C_commondivisor()
{
m_num1 = 0;
m_num2 = 0;
m_result = 0;
}
//
int C_commondivisor::input()
{
cout << " ：";
cin >> m_num1;
cout << " ：";
cin >> m_num2;
cout << "
" << endl;
// ， m_num1
if (m_num2 > m_num1)
{
//
m_num1 = m_num2 - m_num1;
m_num2 = m_num2 - m_num1;
m_num1 = m_num1 + m_num2;
}
return 0;
}
//
int C_commondivisor::output(int i)
{
cout << "
" << m_num1 << " " << m_num2;
if (i == 2)
{
cout << " ";
}
else if (i == 3)
{
cout << " ";
}
else
{
cout << " ";
}
cout << " ：" << m_result << "
" << endl;
return 0;
}
//
int C_commondivisor::mainmenu()
{
cout << " " << endl;
while (true)
{
cout << " ”1“" << endl;
cout << " ”2“" << endl;
cout << " ”3“" << endl;
cout << " ”0“" << endl;
cout << " ， " << endl;
cout << "
：";
int tmp = 0;
cin >> tmp;
if (tmp == 1)
{
input();
m_result = div_alg(); //
}
else if (tmp == 2)
{
input();
m_result = phase_sub(); //
}
else if (tmp == 3)
{
input();
m_result = exhaustion(); //
}
else if (tmp == 0)
{
break; // ，
}
else
{
input();
m_result = div_alg(); // ，
}
//
output(tmp);
}
return 0;
}
//
int C_commondivisor::div_alg()
{
int tmp1 = m_num1;
int tmp2 = m_num2;
for (; tmp1 % tmp2 != 0; )
{
tmp1 = tmp1 % tmp2;
//tmp1 tmp2 ，tmp1
// ， tmp1
tmp1 = tmp2 - tmp1;
tmp2 = tmp2 - tmp1;
tmp1 = tmp1 + tmp2;
}
return tmp2;
}
//
int C_commondivisor::phase_sub()
{
int tmp1 = m_num1;
int tmp2 = m_num2;
for (; tmp1 - tmp2 != 0; )
{
tmp1 = tmp1 - tmp2;
// ， tmp1
if (tmp2 > tmp1)
{
tmp1 = tmp2 - tmp1;
tmp2 = tmp2 - tmp1;
tmp1 = tmp1 + tmp2;
}
}
return tmp2;
}
//
int C_commondivisor::exhaustion()
{
// ， ， ， ，
int i = 0;
for (i = m_num2; i <= m_num2; i--)
{
// ， ，
if ((m_num1 % i) == 0 && (m_num2 % i) == 0)
{
break;
}
}
return i;
}
int main(int argc,char** argv[])
{
C_commondivisor CCD;
CCD.mainmenu();
return 0;
} 以上のアルゴリズムと比較して、非常に大きな数字の最大公約数計算を行う場合、steinアルゴリズムはより効率的なアルゴリズムであり、具体的なアルゴリズムの概念と流れは参考にすることができる.http://blog.csdn.net/kemlkyo/article/details/22698597
参考資料:wikipediahttps://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95#.E6.9C.80.E5.A4.A7.E5.85.AC.E7.BA.A6.E6.95.B0