有时候真的感觉时间不够用,村里人事挺多的,时间就这么浪费了。
Euclid算法是求最大公约数的,介绍请点击在这。Euclid算法的扩展如下引理 如果d整除a和b,同时存在整数x和y,使得d = ax+by成立,那么一定有d = gcd(a,b)。证明如下
- d能整除 a和b,d <= gcd(a,b).
- d能整除 a和b,d就能整除 ax和by,gcd(a,b) <= d.
so gcd(a,b) == d递归思想从上往下a,b -----> b, a mod b从下往上b*x‘ + (a mod b)*y‘ = d -----> a*x + b*y = dbut how can we get x and y? Solution follows
if(b == 0)x = 1, y = 0, d = a
test.cpp#include<iostream> using namespace std; class xyd { public: int x ; int y ; int d ; }; // function Euclid xyd * Euclid_extra(int a,int b); // function main int main() { int a,b,i = 0; xyd * R = new xyd; int max; while( i<55 ) { a = rand()%10; b = rand()%10; if( a<b ) { max = b; b = a; a = max; } R = Euclid_extra(a,b) ; if( R ) { cout<<"a="<<a<<",b="<<b<<",R->x="<<R->x<<",R->y="<<R->y<<",d="<<R->d<<endl; cout<<"a*x + b*y = "<<R->d<<endl; } i++; } system("pause"); return 0; } // function Euclid xyd * Euclid_extra(int a,int b) { if( a <= 0 || b < 0 ) { cout<<"exception of Euclid_extra input"<<endl ; return NULL ; } else { int max; if( a<b ) { max = b; b = a; a = max; } xyd * R = new xyd; if(b == 0) { R -> x = 1; R -> y = 0; R -> d = a; return R; } else { R = Euclid_extra(b,a%b); } xyd * R2 = new xyd; R2 -> x = R -> y; R2 -> y = (R -> x) - ( (a/b) * (R->y) ); R2 -> d = R->d; return R2; } }
原文:http://blog.csdn.net/cqs_experiment/article/details/18670067