第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
论文研究-基于阶跃距离的快速直线绘制新算法 .pdf
http://www.paper.edu.cn
基于阶跃距离的快速直线绘制新算法
曾龙 1，苗兰芳 1，2
1（浙江大学 CAD&CG 国家重点实验室. 浙江 杭州 310027）
2（浙江师范大学 计算机信息与工程学院. 浙江 金华 321004）
摘要: 直线在光栅上生成速度的提高在图形学领域有着非常重要的实际意义。本文提出阶跃距离的概念，
可以消除Bresenham算法中的决策参数，并从新的角度探讨阶跃距离和直线斜率的关系，获得了直线的阶跃
距离公式，在此基础上，通过对阶跃距离的周期性和对称性的研究，提出一种基于阶跃距离的快速直线绘
制新算法。经理论分析和实验表明，该快速绘制算法的效率有很大提高。
关键词: 阶跃距离; 周期性; 对称性; 分段绘制; 直线
A Fast New Line Drawing Algorithm Based on Step-Distance
Zeng Long1, Miao Lan-fang2
1(State Key Laboratory of CAD&CG．Zhejiang University．Hangzhou 310027．China)；
2(College of Computer Science and Engineering，Zhejiang Normal University．Jinhua 32(004，China)
Abstract: Accelerating the line drawing process on raster has great significance in graphic field. In this paper,
step-distance is presented to avoid the decision-parameter used in Bresenham’s algorithm. A fast new line drawing
algorithm is proposed, which based on the formulas of step-distance and the periodicity and symmetry of
step-distance. Both analysis and experimental results shows the new algorithm can accelerate the line drawing
process.
Key words: step-distance; periodicity; symmetry; segment drawing; line
1 引言
直线绘制是绘图系统中最基本的，也是出现最多的元素，直线生成算法的效率直接影响
着绘图系统的效率。基于光栅扫描显示器的逐点直线绘制算法主要分成两类：第一类是单步
单点算法，即每次只生成一个像素点，如20世纪60年代中期出现的经典的直线绘制方法
Bresenham[1]算法，在Bresenham算法中，所有的运算都是整数运算，绘制一个点的运算量是
1次整数加法运算和1次符号判断。后来还有很多对Bresenham算法的改进算法 [2-3]，但是
Bresenham算法几乎是单步单点算法中最简练的形式了。第二类算法是单步多点算法，即如
何一次生成直线上的多个像素点，如二步法[4]，对于斜率小于1／2的直线，位移链码中1之
后必跟着0，后一步不用判断即可确定，因此，一次判断生成两个点，但是该算法对斜率接
近l/2的直线效果较好，对趋于平坦的直线效果不够显著；另外有基于对称的快速直线绘制
算法[5]，它基于直线以中点为界，其两边是对称的这一事实，对任意方向的直线都可以一次
绘制关于直线中点对称的两个点；还有最近Miao[6-7]提出的自适应多步算法，每次绘制的步
长可以自动调整，该算法将待绘制的直线直接表达成一串由0，1组成的位移码，根据位移码
的组成特点，自适应地确定一次生成的像素数目，并且对位移码的周期性进行了初步的分析
和讨论，并指出：如果能够精确确定位移码中相邻1之间0的个数或者相邻0之间1的个数，就
能获得更高的绘制效率。
本文从阶跃距离（详细定义见第二节）这一新的角度对任意给定直线进行了深入讨论和
研究，通过基本的数学推导获得给定直线的阶跃距离公式，因此，可以精确确定光栅上各接
1
近直线的光栅点的位置，解决了文献[6]中提到的相邻位移码中1之间0的个数或者相邻0之间
http://www.paper.edu.cn
1的个数，从而使算法能获得高一倍左右的绘制效率。
2 阶跃距离的定义
2.1 斜率范围的选取
由于在直角坐标系中，不同象限的直线具有对称性，求解方法可以相互转化，因此一
< 之间的直线为研
般选取斜率在[0,1]之间的直线进行研究。记直线斜率为 m ，则 0
究对象。
1m≤
依据本直线算法的特点，进一步把 0
直线进行讨论，在 0
节的定义)，但是在第3节中基于阶跃点概念的推导方法和所得结论是相似的。
范围内的
< 时的讨论方法类同，虽然阶跃点的定义方式稍有不同(见2.2
< 分成两部分，只选取 0.5
1m≤
<1m≤
m≤
0.5
2.2 点在光栅上的选择过程
在光栅显示器中，直线是由一系列与其偏离最小的光栅点组成的，每一次绘制过程的实
x= ， ky 是选择A点还
x
x
− ，
− ，
，结合直线方程的一般式可以推出
质是确定与其接近的光栅点，如图1，在绘制直线L上的第k各点时
p x y ,终点 (
p x y ，则
x
是B点。如给定直线的起点 (
e
e
s
e
， 2d
d
−
引入决策参数
,
)
s
, 1d
e
BC=
x d
(
1
AC=
= ∆ ⋅
y
∆ =
x
∆ =
kp
s
)
y
y
)
,
2
k
s
e
s
（详细过程参考文献[8]）决策变量的迭代公式(2.2.1)和坐标的选择公式(2.2.2)
其中k=0, 1,……
p
k
1
+
=
p
k
2
+ ∆ − ∆
2
y
x y
(
−
y
k
)
k
1
+
(2.2.1)
y
k
1
+
−
y
k
1
0
⎧
= ⎨
⎩
p
k
p
k
≥
<
0
0
(2.2.2)
p
其中， 0
= ∆ − ∆ ； 1k
+ − 取值为0或1，取决于参数 kp 的符号。
y
k
2
y
x
y
2.3 阶跃点、阶跃距离的定义
当 0
1m≤
< 时，相邻两个光栅点的关系只有两种情况：一种是对角关系；另一种是成
时，对角关系的
时，水平关系的点要少；而在0
<0.5m≤
<1m≤
水平关系。直线斜率在 0.5
点就要少。本文把这些占少数的点定义为阶跃点。
<1m≤
如图1所示，直线L1（0.5
0P ≥ ，
0P < 所对应的点定义为阶跃点，即此时的阶跃点与其前一点的关系为水平关系，而
时，如图1中直线L2，大多数的点所
0P ≥ 所对应的点定义为阶跃点，即此种情况下的阶跃点与
因此把
与后一点的关系为对角关系；当直线斜率在 0
对应的决策参数
）上大多数的点成对角关系，所对应的决策参数
0P < ，因此把
<0.5m≤
其前一点的关系为对角关系，而与后一点的关系为水平关系。
另外，由于直线的起点是单独绘制，这样就可以认为 0p 所对应的光栅点和终点分别没
有前点和后点，所以，本文直接把这两点分别定义为前端伪阶跃点和后端伪阶跃点，“伪”
是因为它们不具备阶跃点的性质，需要单独讨论。
而阶跃距离就是指两个阶跃点之间的光栅点数(包括后一个阶跃点)。
2
http://www.paper.edu.cn
图1 直线生成的逼近过程、阶跃点 表示选中的光栅点; 表示阶跃点
从定义中可以看出，本文的阶跃点其实就是靠近直线的一些特殊光栅点，如果求出每个
阶跃距离的大小就可以精确知道每两个阶跃点之间非阶跃点的数目，而非阶跃点有相同的关
系，不用判断就可以一次性绘制，这就是本文思想的核心所在。
3 阶跃距离公式
在求解阶跃距离之前，先要确定所给直线段内有多少个阶跃点，定理1给出其求解公式。
p x y 、终点 (
p x y ，则直线段
< ，直线段的起点 (
e
s
1m≤
)
)
,
,
e
e
s
s
定理1 已知直线的斜率 0.5
内的阶跃点数
k
y
∆−∆=
x
(3.1)
证明：斜率为
的直线与斜率为1的直线在一个网格内产生的偏差是
y ∆∆
x
y ∆∆−1
x
，
那么在 x∆ 个光栅网格内，产生的偏差为 (
生一个网格大小的偏差，在直线斜率 0.5
点称为阶跃点，故在 x∆ 个光栅网格内阶跃点的数目是
y
x
y
∆−∆=∆∆−⋅∆ 1
1m≤
；而一个水平关系点产
< 内，由2.3节的定义可以知道成水平关系的
x
x
)
k
y
∆−∆=
x
，证毕。
另外，在求解伪阶跃点和第一个、最后一个阶跃点之间的距离以及阶跃点之间的阶跃距
离时，会用到两个非常有用的结论，分别在引理1、引理2给出。
y
< ，则决策变量 kP 的最小值 2(
引理1 已知直线的斜率 0.5
∆ − ∆ .
1m≤
x
)
证明：假设 kp 是最小值，则肯定有
≤
kp − < ，则由公式（2.2.2）知 1
+ −
k
p
k
y
① 如果 1
p −
k
1
y
k
0
和假设条件矛盾；
，对于 1kp − 的取值分两种情况讨论：
p
= ，则肯定有
k
+ ∆ >
p
k
=
p
0
2
y
1
−
k
1
−
，
kp − ≥ ，则由公式（2.2.2）知 1
k
+ −
y
② 如果 1
0
因此肯定有
y
k
= ，又因为斜率 0.5
1
1m≤
< ，即 y
∆ < ∆ ，
x
符合假设条件，而其中 1
k
k
1
−
2
2
p
p
+ ∆ − ∆ <
y
=
kp − ≥ ，所以当 1
kp − = 时，有最小值
0
= ∆ − ∆ ，证毕。
< ，假设一阶跃点的决策变量 kP ，下一个阶跃点的决策变
1m≤
x
0
p
k
2(
kP
y
x
1
−
)
引理2 已知直线的斜率 0.5
量 k lP + ，其中l 为它们之间的阶跃距离，则有（式中的[]为取整运算）
l
＝
−
⎡
⎢
⎣
y
kp
2
+ ∆
y
x
2(
∆ − ∆
)
+
2
⎤
⎥
⎦
（3.2）
证明：由公式（2.2.2）得
p
=+
lk
p
k
−∆+
yl
2
l
(2
x
)1
∆−
（3.3）
由引理1知
3
2(
y
∆ − ∆ ≤
联立(3.3)和(3.4)求解得
p
y
2
+ ∆
k
y
x
2(
∆ − ∆
y
p
2
+ ∆
k
y
x
2(
∆ − ∆
)
y
p
2
+ ∆
k
y
x
2(
∆ − ∆
因为l 是整数，且
1,
+ −
−
−
)
⎡
⎢
⎣
1
+ < ≤ −
l
y
p
2
+ ∆
k
y
x
2(
∆ − ∆
⎤
⎥
⎦
2
+
)
http://www.paper.edu.cn
p +
k l
< （3.4）
0
x
)
+
2
)
内有且仅有一个整数，因此，
l
⎡
= −
⎢
⎣
kp
y
2
+ ∆
y
x
2(
∆ − ∆
)
+
2
⎤
⎥
⎦
证毕。
在Bresenham算法中决策参数的每次更新都需要一次加法和一次判断操作，本文尽量避
免引入决策参数等外部变量。引理1确定阶跃点决策参数的取值范围，引理2给出了阶跃距离
和决策参数的关系式，为最终消除决策参数提供了条件，详细消除过程见定理2和定理3。
< ，则 0P 对应前端伪阶跃点到第一个阶跃点的阶跃距离公
定理2 已知直线的斜率 0.5
1m≤
式是([]为取整运算)
0
l
⎡
= ⎢
⎣
x
∆
y
x
∆ − ∆
⎤
⎥
⎦
)
2
(
证明：前端伪阶跃点的决策变量为 0P ，即从 0P 开始后第 0l 个点处出现决策参数小于零
的情况 0
lP < ，那么由公式（2.2.1）可知，
0
lP
0
=
P
0
+
0
l
2
(
y
∆ − ∆ （3.5）
x
)
又由引理1可知阶跃点
2(
y
∆ − ∆ ≤
x
)
p
k
< （3.6）
0
把式（3.5）代入式（3.6）可以推出
1
− +
x
∆
x
∆ − ∆
y
)
2
(
<
0
l
≤
x
∆
x
y
∆ − ∆
)
2
(
因为n 是整数，且区间
整数，因此，
1
− +
⎛
⎜
⎜
⎝
x
∆
x
y
∆ − ∆
2
(
,
)
2
(
x
∆
x
∆ − ∆
y
)
⎤
⎥
⎦
长度为1，即区间内有且仅有一个
0
l
⎡
= ⎢
⎣
x
∆
y
x
∆ − ∆
⎤
⎥
⎦
)
2
(
证毕。
定理3 已知直线斜率满足 0.5
1m≤
< ，则阶跃点的阶跃距离递推公式(数学归纳法证明)
4
http://www.paper.edu.cn
j
l
+
(
⎡
⎣
2
N
+
)
1
M
⎤
⎦
N
=
1,2,
L
k
−
1
（3.7）
N
l
= −
N
1
−
∑
j
=
0
其中
M
=
x
∆
x
∆ − ∆
y
)
2
(
，式中的[]为取整运算；
证明：由定理2知第一个阶跃点处的决策变量为（该定理证明中用到的[]都为取整运算）
lP
0
=
P
0
+
0
l
2
(
)
y
∆ − ∆
x
iP i
另外使用符号 ,
=
0,1,
L
,
k
−
1
表示阶跃点处的决策变量，以示区别，第一个阶跃点
处的决策变量记为
0
P
=
P
n
=
P
0
+
2
n
(
)
y
∆ − ∆ =
x
P
0
+
0
l
2
(
y
∆ − ∆ （3.8）
x
)
由公式（3.3）得第二个阶跃点的决策变量是
P
1
=
p
1
n l
+
=
0
p
+
l
2
1
y
∆ −
1
l
2(
x
1)
− ∆
再使用引理2中的结论可知
1
l
⎡
= −
⎢
⎣
0
p
y
2
+ ∆
y
x
2(
∆ − ∆
)
+
2
⎤
⎥
⎦
（3.9）
联立（3.8）、（3.9）以及 0P 求得
1
l
=
(
n
3 2 1
−
−
(
m
2 1
−
m
)
)
⎡
⎢
⎣
⎤
⎥
⎦
= − +
l
0
(
)
2 1 1
× +
M
（3.10）
所以
1N = 时，结论式（3.7）成立；
（1）当
（2）假设当 N j= 时，结论式（3.7）也成立，则有
（3）那么当
(
j
⎡
⎣
2
+
= −
l
j
+
N j= + 时，则有
(
P
1
−
i
j
j
)
1
M
⎤
⎦
，
j
P
=
P
j
l
1 2
−
+
j
(
y
x
∆ − ∆ + ∆
2
x
)
2
j
1
−
j
j
i
−
l
∑
0
=
1
P
P
P
(
2
∑
l
j
2
0
j
i
=
0
+
=
=
=
=
=
+
+
2
+
l
2
(
2
(
l
l
j
j
l
j
+
1
−
+
j
1
−
1
−
)
x
2
y
∆ − ∆ + ∆
l
+
l
j
L
x
)(
L
+
l
)
x
x
y
4
∆ − ∆ + ∆
)(
(
)
l
j
y
x
2
1
∆ − ∆ +
)(
)
j x
y
2
0
∆ − ∆ +
∆ − ∆ + ∆
j x
2
∆ − ∆ + ∆
)
2
5
∆
x
−
+
2
2
5
x
x
x
y
l
1
y
i
l
(
)
y
∆ − ∆ +
x
5
http://www.paper.edu.cn
j
y
x
4
∆ − ∆ −
x
y
2(
∆ − ∆
p
)
⎤
⎥
⎦
2
⎤
⎥
⎦
j
∑
=
0
i
=
i
l
+
)
⎧
⎨
⎩
2
⎡
⎢
⎣
(
2(
x
y
)
∆ − ∆ +
x
y
∆ − ∆
)
2
j x
∆ − ∆ + ∆
5
2
x
y
⎫
⎬
⎭
⎤
⎥
⎥
⎥
⎥
⎦
j
+
1
l
= −
j
2
p
+ ∆
y
2(
∆ − ∆
y
x
2
∆ − ∆ −
4
y
x
2
⎡
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎣
⎡
⎢
⎢
⎢
⎢
⎣
=
=
(
2
j
+ ∆ −
1
x
)
j
l
2
∑
0
y
∆ − ∆
=
i
i
x
2(
y
∆ − ∆
x
)
(
)
⎤
⎥
⎥
⎥
⎥
⎦
= −
j
∑
=
0
i
i
l
+
(
⎡
⎣
2
j
+
1
)
M
⎤
⎦
因此，由上面的第（3）步可见结论对于
N j= + 同样成立。
1
因此，结论式（3.7）成立，证毕。
4 阶跃距离对称性研究
对称性是阶跃距离非常重要的特性，下面给出定理4进行详细的阐述。
定理4 已知直线斜率满足 0.5
1m≤
< ，则对于阶跃距离公式 ,
Nl N
=
1,2,
−L
k
1
，以及
l
l、 ，则平均计算量
0
k
N k=
2
次。( 0l 为前端伪阶跃点到第一个阶跃点的阶跃距离， kl 为
后端伪阶跃点到最后一个阶跃点的阶跃距离。)
证明：从定理1、定理2、定理3和引理1、引理2的证明当中可以发现，证明过程和所得
结 论 只 与 x∆ ， y∆ 有 关 ， 这 意 味 着 即 使 将 直 线 的 起 点 和 终 点 对 调 ，
x
∆ =
x
e
− ，
x
s
y
∆ =
y
e
− 不变，定理1、定理2、定理3和引理1、引理2的结论也不变，即直线以中点为
y
s
界，其两边是对称的；只是当 1T − 为奇数点时，中间两个阶跃距离
l
k
k
1
−
2
、 才有可能不
1
+
2
l
l
相等，当 k=1 时，无阶跃距离，此时有 0
1
l、 不相等，下面进行详细讨论：
在一个周期T 内， 0P 对应的点单独绘出，所以剩余的 1T − 点和阶跃距离具有如下的关
系式：
0
l
1
+ +
l
L
k
1
−
+
l
k
+
l
= −
T
1
（4.1）
其中，设 0l 为 0P 对应的点到第一个阶跃点的距离， kl 为终点到最后一个阶跃点的距离。
（1） 若 1T − 为奇数，则T 为偶数，由定理1可知T 和 k 必互素，k 必为奇数，所以 1k −
为 偶 数 ， 即 阶 跃 距 离 有 偶 数 个 ，
T
1 2
− −
0
l
⎛
⎜
⎝
1
+ +
l
k
1 2
− −
2
L
+
l
⎞
⎟
⎠
还 是 奇 数 ， 则
k
1
−
2
l
k
1
+
2
+
l
= − −
1 2
T
0
l
⎛
⎜
⎝
1
+ +
l
k
1 2
− −
2
L
+
l
⎞
⎟
⎠
，计算次数为
k
1 2
− −
2
+ =
2
k
1
+
2
；
6
（2） 若 1T − 为偶数
① 若
1k − 为 奇 数 ， 阶 跃 距 离 有 奇 数 个 ， 则 由 式 （ 2.3.13 ） 知
http://www.paper.edu.cn
k
1 1
− −
2
+
l
⎞
⎟
⎠
为偶数，则
k
2
l
= − −
1 2
T
0
l
⎛
⎜
⎝
1
+ +
l
k
1 1
− −
2
L
+
l
⎞
⎟
⎠
，计算
T
1 2
− −
k
次数为
L
1
0
l
l
+ +
⎛
⎜
⎝
1 1 1
− −
2
+ = ；
k
2
② 若 1k − 为偶数，阶跃距离有偶数个，
T
1 2
− −
0
l
⎛
⎜
⎝
1
+ +
l
k
1 2
− −
2
L
+
l
⎞
⎟
⎠
为偶数，则
k
1
−
2
l
k
1
+
2
=
l
=
1
2
⎛
⎜
⎜
⎝
T
1 2
− −
0
l
⎛
⎜
⎝
1
+ +
l
k
1 1
− −
2
L
+
l
⎞
⎟
⎠
⎞
⎟
⎟
⎠
，计算次数为
k
1 2
− −
2
1
+ =
k
1
−
2
；
综合（1）、（2）两种情况知，平均计算次数为 / 2k ，证毕。
5 快速直线绘制新算法及其分析
根据第3节中定理1、定理2、定理3的阶跃距离公式以及定理4，本文提出基于阶跃距离
的快速直线绘制新算法，基本步骤总结如下：
Step1: 据定理1求出阶跃点数 k 并进行初始化工作；
Step2: 为了程序绘制的方便，定义距离数组draw[k],据定理1、2、3、4求解距离数组；
Step3: 调用SetPixel()函数分段绘制，到了每段的末尾绘制一个水平点，其余的全是斜点；
完整的绘制算法伪代码算法1所示。
dx←xe-xs
dy←ye-ys
k←dx-dy
value←k<<1
M←dx/value
f←M+M
L←M
S←M
SolveDraw( )
SetPixel(xs, ys)
算法1 直线非周期绘制算法伪代码
x←xs+1
x←ys+1
SetPixel(x, y)
Draw( )
在算法1的伪代码中：首先进行初始化工作，有一次除法操作。然后调用SolveDraw()
函数获得距离数组draw[k],其伪代码由算法1.1给出，由定理4知需要对dx-1和k-1的奇偶性
进行判断，在代码中为了避免乘除，采取了和flag=1进行位与运算，因为一个数如果为奇数，
其二进制码的最末尾肯定为1，否则为偶数；在求解前k/2个阶跃距离时，每次要进行3次加
法和1次取整操作，后k/2个距离就可以由对称性获得，但是有个地方值得注意，即当dx-1
为奇数，且k-1为偶数时，有可能出现draw[0]不等于draw[k]，因此，伪代码中引入了变量
sum，从而增加了k/2次加法。得到距离数组以后，绘制工作就很简单了，调用函数Draw()
据距离数组绘图，其伪代码由算法1.2给出。
flag←1
judge1←dx-1
judge2←k-1
range1←k>>1
range2←(k+1)>>1
draw[0]←L
If (flag & judge1)&(flag & ~judge2) Then
sum←0
If 1= =range2 Then
7
draw[k]←judge1-draw[0]
Else
For i=1 To range2
S←S+f
L←L-draw[i]
End For
sum←-L
For j=range2+1 To k-1
draw[i]←L+[S]
sum←sum+draw[j]
draw[j]←draw[k-j]
End For
draw[k]←judge1-sum
End If
End If
If (flag & ~judge1)&(flag & judge2) Then
draw[i]←L+[S]
For i=1 To range1
S←S+f
L←L-draw[i]
End For
For j=range1+1 To k-1
draw[j]←draw[k-j]
http://www.paper.edu.cn
draw[k]←draw[0]
End For
End If
If (flag & ~judge1)&(flag & ~judge2) Then
draw[i]←L+[S]
For i=1 To range2
S←S+f
L←L-draw[i]
End For
For j=range2+1 To k-1
draw[j]←draw[k-j]
End For
End If
draw[k]←draw[0]
算法1.1 SolveDraw()的伪代码
For i=0 To k-1
For j=1 To Draw[i]-1
x←x+1
y←y+1
SetPixel(x, y)
End For
x←x+1
SetPixel(x, y)
End For
For j=1 To Draw[k]
x←x+1
y←y+1
SetPixel(x, y)
End For
图1.2 Draw()的伪代码
本文选择与miao在文献[6]中提出的自适应多步位移码直线绘制算法进行比较，详细对
比见表1(表中 h=dx-dy)。从表1的对比中可以看出本文非周期算法比自适应多步位移码直线
绘制效率提高约50%。
6 阶跃距离的周期性讨论
在定理1中，当
x
y
∆−∆∆ ,
x
不互素时，假设具有最大公约数 cx ，则每隔
cxx /∆
个光栅
点，产生的偏差和初始点的偏差值是一样的，即呈现出周期性，此时的周期和阶跃点数是
T
= ∆
。
(
= ∆ − ∆
x x
,c
k
x
y
)
x
c
算法1中基于阶跃距离的快速直线绘制新算法实质上可以看成是最大公约数
cx = 的周
cx > ，在算法1的伪代码基础上稍加改进，即可以得
1
期绘制，即T
到基于阶跃距离的快速周期绘制新算法，伪代码如算法2所示。
dx= 的周期绘制，如果
1
dx←xe-xs
dy←ye-ys
xc←ComDiv(dx, dx-dy)
k←(dx-dy)/ xc
T←dx/ xc
value←(dx-dy)<<1
M←dx/value
f←M+M
n←[M]
L←M
S←M
SolveDraw()
SetPixel(xs, ys)
x←xs
算法2 直线周期绘制代码
x←ys
While r<=xc Do
x←xs+1
x←ys+1
SetPixel(x, y)
Draw()
End While
但是周期绘制中要求解dx与dx-dy的最大公约数 cx ，这是项不可回避的工作，本文用经
过改进后“欧几里德辗转相除法”求解最大公约数，伪代码如图2.1所示，其最坏情况下的
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
