没有合适的资源?快使用搜索试试~ 我知道了~
欧几里德算法和扩展欧几里德算法.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 76 浏览量
2022-05-06
12:24:26
上传
评论
收藏 45KB DOC 举报
温馨提示
试读
5页
欧几里德算法和扩展欧几里德算法.doc
资源推荐
资源详情
资源评论
欧几里德算法和扩展欧几里德算法
欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个整数 a,b 的最大公约数。其计
算原理依赖于下面的定理:
定理:gcd(a,b) = gcd(b,a mod b)
证明:a 可以表示成 a = kb + r,则 r = a mod b
假设 d 是 a,b 的一个公约数,则有
d|a, d|b,而 r = a - kb,因此 d|r
因此 d 是(b,a mod b)的公约数
假设 d 是(b,a mod b)的公约数,则
d | b , d |r ,但是 a = kb +r
因此 d 也是(a,b)的公约数
因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,
得证
欧几里德算法就是根据这个原理来做的,其算法用 C++语言描述为:
void swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}
int gcd(int a,int b)
{
if(0 == a )
{
return b;
}
if( 0 == b)
{
return a;
}
if(a > b)
{
swap(a,b);
}
int c;
for(c = a % b ; c > 0 ; c = a % b)
资源评论
老帽爬新坡
- 粉丝: 79
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功