首页 > 其他 > 详细

算法之旅 Euclid算法的扩展

时间:2014-01-23 04:17:51      阅读:283      评论:0      收藏:0      [点我收藏+]

Euclid算法的扩展

  • 真言

有时候真的感觉时间不够用,村里人事挺多的,时间就这么浪费了。

  • 算法

Euclid算法是求最大公约数的,介绍请点击在这
Euclid算法的扩展如下
引理 如果d整除a和b,同时存在整数x和y,使得d = ax+by成立,那么一定有d = gcd(a,b)。
证明如下
  1. d能整除 a和b,d <= gcd(a,b).
  2. 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 = d
but how can we get x and y? Solution follows
bubuko.com,布布扣
if(b == 0)
 x = 1, y = 0, d = a

  • 实验

bubuko.com,布布扣

  • 代码

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;
	}
}


算法之旅 Euclid算法的扩展

原文:http://blog.csdn.net/cqs_experiment/article/details/18670067

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!