数学在程序设计中的应用（c++版）
5星 · 超过95%的资源 需积分: 9 67 浏览量
2014-05-06
20:50:30
上传
评论
收藏 71KB DOCX 举报 
数学是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几
乎在一切自然科学领域中都起着基础性的作用。数学的特点不仅在于概念的抽象性、逻辑
的严密性、结论的明确性，还在于它应用的广泛性。
数学方法在程序设计中的运用包括两个方面：化简题目和直接解决问题。
应用数学方法化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。
应用数学方法化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数
学模型提供依据。而用数学方法直接解题，其效率更是一般算法所不可及的。下面以具体
的问题为例，介绍有关的数学知识和数学方法，体会利用数学方法解决问题时的乐趣。
一．数论基础
1．欧几里德转辗相除法
两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数
利用 gcd(a,b)=gcd(b,a mod b)求 a，b 的最大公约数：
int gad(int a, int b) 这就是求最大公约数的欧几
里德算法，竟然如此高明！！！
{
return b ? gad(b, a&b) : a;
}
思考：如何把上述算法写成迭代形式？
int gad2(int a, int b)
{
while (b != 0)
{
int rex = b;
b = a%b;
a = rex;
}
return a;
}
2 ． 扩 展 的 欧 几 里 德 算 法 如 果 gcd(a,b)=d ， 一 定 存 在 整 数 x 和 y 满 足
gcd(a,b)=ax+by。求 d 及满足 gcd(a,b)=ax+by 的整数对（x，y）的算法如下：
int x, y, q;
void exgad(int a, int b)
{
if (b == 0)
{
x = 1;
y = 0;
q = a;
}
else
{
exgad(b, a%b);
第 1 页 共 34 页
剩余33页未读，继续阅读
评论1
最新资源