アルゴリズム学習ノート(1)----最大公約数
533 ワード
2つの整数aを求めて、bの最大公約数は転がり相除算法で得ることができて、その具体的な証明は以下の通りです:a>bを仮定します a=bt+r、すなわちgcd(a,b)=gcd(b,r)を証明すると仮定し、gcd(a,b)=c、a=mc、b=nc とする. r=a-bt=mc-ntc=(m-nt)cであれば、m-ntとnの相互作用 を証明するだけである.反証法:m-ntとnが互いに素を持たないと仮定すると、m-nt=xd、n=yd(d>1)、a=mc=(nt+xd)c=(ytd+xd)c=(yt+x)dc、b=nc=ydc、gcd(a,b)=dcとなり、既知の条件に反するため、m-ntとnが互いに素であるため、gcd(b,r)=c=gcd(a,b) コードは次のとおりです.
int gcd(int a, int b) //a>b
{
int c;
do {
c = a % b;
a = b;
b = c;
}while( c != 0);
return a;
}