欧几里德算法是什么
发表时间：2024-08-06 07:24:41
来源：网友投稿
欧几里德算法
欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数.其计算原理依赖于下面的定理：
定理：gcd(a,b)=gcd(b,amodb)
证明：a可以表示成a=kb+r,则r=amodb
假设d是a,b的一个公约数,则有
d|a,d|b,而r=a-kb,所以d|r
所以d是(b,amodb)的公约数
假设d是(b,amodb)的公约数,则
d|b,d|r,但是a=kb+r
所以d也是(a,b)的公约数
所以(a,b)和(b,amodb)的公约数是一样的,其最大公约数也必然相等,得证.
欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为：
voidswap(int&a,int&b)
{
intc=a;
a=b;
b=c;
}
intgcd(inta,intb)
{
if(0==a)
{
returnb;
}
if(0==b)
{
returna;
}
if(a>b)
{
swap(a,b);
}
intc;
for(c=a%b;c>0;c=a%b)
{
a=b;
b=c;
}
returnb;
}
参考资料：internet
免责声明：本站发布的教育资讯（图片、视频和文字）以本站原创、转载和分享为主，文章观点不代表本网站立场。
如果本文侵犯了您的权益，请联系底部站长邮箱进行举报反馈，一经查实，我们将在第一时间处理，感谢您对本站的关注！
相关资讯
汽修专业新疆怎么找工作
2025-04-06
机械专业专长怎么写简历
2025-04-06
专科怎么报审计专业的
2025-04-06
专业学科导师类别怎么填
2025-04-06
查报考专业网站怎么查
2025-04-06
水电专业规划怎么写简历
2025-04-06
表演专业怎么留学的好呢
2025-04-06
专业防雷检测怎么收费的
2025-04-06
怎么查询同等学力专业
2025-04-06
高考技能专业怎么选择的
2025-04-06
钢筋套筒专业名称怎么写
2025-04-06
中专怎么填高考志愿专业
2025-04-06
中专统招怎么报志愿专业
2025-04-06
师范专业自我评价怎么写
2025-04-06
景观建筑换专业怎么换好
2025-04-06
建筑专业学生简历怎么写
2025-04-06
推荐资讯
“老头”“老爸”用日语怎么说注上罗马音和中文谐音
2024-07-09 13:24:26
成人自考成绩什么时候公布？
2024-07-23 17:13:43
全国四大名洞地区排名
2024-07-30 23:09:32
英国为什么经常下雨
2024-08-01 08:57:51
广西农信手机银行怎么登录
2024-08-14 22:39:08
会计计算公式记忆口诀
2024-10-12 07:00:40
ecco产品有什么特点
2024-10-16 11:41:54
编导专业哪个就业好
2025-03-22 08:43:32
学习开火车报哪个专业
2025-03-23 09:31:09
徐州中医院哪个专业
2025-03-23 17:57:45
新励学网教育平台
海量全面 · 详细解读 · 快捷可靠
累积科普文章数：18,862,126篇
热门关注
首页
教育
考研
作文
公考
申论
留学
建造
会计
问答
冀ICP备2024091466号