简便算法

2024-08-07

简便算法（共8篇）

简便算法篇1

摘要：为了方便地解决无环路的网络最大流问题, 本文给出了一种运用最小截原理来求解的图上作业法以及该算法的理论依据与证明, 并通过举例说明了该算法的简便性与有效性。该算法能直观地求出最大流和最小截, 比使用教材上所提到的其他方法节省大量计算时间, 大量实践表明此方法的确实用有效。

关键词：运筹学,运输网络,最大流,最小截

引言

Ford-Fulkerson算法[1]是一种传统的求最大流算法, 许多研究者试图在FordFulkerson算法的基础上提出更简便、操作也更直观的方法, 比如文献[2]就给出了一种建立在最小割原理上的求网络最大流的图解法, 其操作方法简单, 但是该方法存在原理上的问题。本文利用文献[3]中关于最小割原理的说明和文[4]中关于最小割集的严谨定义, 在文献[2]工作的基础上, 试图给出网络最大流问题的另一种算法流程, 以及证明这种算法的使用前提条件。下面简单地给出证明, 并以教材献[5]中提供的例题为例。

1、概念和依据

定义1给定运输网络N= (V, A, C) , 若顶点集V被剖分为两个非空集合V1和, 使s∈V1, t∈, 则把始点在V1汇点在中的所有弧构成的集合 (记为 (V1, ) ) 称为 (分离s和t的) 截集。给一截集 (V1, ) , 把截集 (V1, ) 中所有弧的容量之和称为这个截集的容量 (简称为截量) , 记为C (V1, ) 。把容量最小的截集称为最小截[4]。

结论1任何一个运输网络都可以改画成下面一种形式:将所有顶点从左至右排成一列直线后补全支流及流量, 让所有流以从顶点或顶点集流入或流出的形态来表示。

结论1的正确性是显而易见的。如图1[5]所示的运输网络即可改画为图2的形式。将图2暂称为第二类网络图。

结论2在无“逆流”的第二类网络图里, 在相邻两点间作一次切割, 所截得的容量的最小值即为系统网络的最大流值。

证明“逆流”即为流向与始点到汇点指向方向相反的流。图2中, 流 (v4, v3) 即为“逆流”。以下为证明。

此法原理为最大流量最小截定理。根据文献[3], 在有v个点的网络里, 若要进行完整的穷举求最小截量, 则需做2v-2次切割, 取所得截量的最小值。但我们可设想, 把系统网络视作由水管组成, 在始点处输入高压水流, 通过网络结构以后从汇点输出, 流量问题的根本原因则是系统某些地方结构的限制。那么将管道按图2所示方法“拉直”, 在相邻两点处切开, 则汩汩流出的水流量的最小值即为此网络的最大流量。

当出现“逆流”时, 这些管道中也有可能充满水流, 与另一支的正向水流汇合后流向终点 (如图2中v1→v4→v3→v6→v7) 。此时的“逆流”为“迂回的正流”, 换言之, 此时这根管道的容量也影响着网络最大流的流值;但在这种情况下, 进行切割时此管道却无法直观地在图上处理。所以在有逆向管道的情形下, 结论2不适用。

这样, 我们不妨直接通过某种构图方法, 将所有管道都画成“正流”形式, 如图3所示。这样就可以不出歧义地得出两顶点间容量的截值。

综上所述, 结论2得证。

关于结论2, 值得指出的是, 文献[2]的做法是在直接在图2上于相邻顶点处“切开”, 并将逆流管道的容量直接忽略不计, 仅计算所有正流容量的和值后取最小值。其依据是在于定义1中, 截集的容量指所有始点在V1汇点在的所有弧的集合[4];“逆流”在计算时不计, 只计算始点在V1汇点在的所有弧容量之和后取最小值即可。但根据文[3]的解释, 这么做的前提是进行2v-2次穷举。而上述图解法并没有穷举, 是不能直接使用最小截定理的。图3中只进行了v-1次切割, 是由于其为无“逆流”的特殊情形, 不存在上面所提到的“迂回的正流”, 所以省去了穷举这部分割集值的工作。事实上, 在图2中, 将“逆流”弧 (v4, v3) 的容量设为1时, 根据文献[2]的计算, 最大流值应不变;但将其转换成图3进行计算, 最大流值应为9, 比原来要小。这就是因为图2忽略了逆流的存在。

结论3对于无双向连通弧 (即两点之间有且只有存在一条具有方向性的弧) 的运输网络, 在没有弧首尾相接形成环路 (弧 (v1, v2) , (v2, v3) , (v3, v1) 构成一个环路) 的情况下, 都可以按固定的操作方式, 转换为无“逆流”的第二类网络图。

证明由上述叙述可知, 所谓的无“逆流”的第二类网络图, 实质上就是所有流都朝向同一方向 (始点到汇点) 的网络图;如果将从左至右依次排列的顶点进行分级, 则所有的流都必须是从低层级流向高层级, 而所谓的“逆流”, 就是从高层级流回低层级的流量。

只要网络中不存在环路或双向连通弧, 则一个点对另一个点流向的关系就是确定的, 两层级的相对高低就是唯一的。这样就可以确定所有点的相对层级关系, 将所有顶点位置依此关系排定后, 补全支流, 则一定不会出现倒流向始点的水流;而一旦存在了环路, 则某个点流出的流就能流回至这个点或流至更高的层级, 且无论如何排列环路上的点, 这种情况一定会出现。

接下来以实例操作进行证明。以图1中的网络图为例, 首先将其以动态规划的形式分为五个层次 (v1第一层次, v2、v4第二层次, v3第三层次, v5、v6第四层次, v7第五层次) , 将层次从低至高排列 (v1→v2、v4→v3→v5、v6→v7) , 再分别讨论层次内部新层级的划分。划分的原则是根据层次内部顶点间的流向关系, 若某顶点至另一顶点有流量, 则此顶点排序在前 (如v2至v4有流量, 则v2在第二类网络图内应在v4之前, 若没有则关系任意, 即排列为v1→v2→v4→v3→v5、v6→v7) 。将排列成一行的点补全各个支路及流量, 所构成的第二类的网络图由于是根据层次与层次之间, 层级内部的流向来确定顶点的排列顺序, 其必定不会出现“逆流”。

当网络流图中出现环路时, 由于有循环流向, 所以无法确定低层级与高层级, 故而无法画出第二类网络图。所以此方法仅适用于无环路的简单图。

综上所述, 命题得证。

2、解法与举例

通过上述结论, 我们可以得到这种解法的适用范围:原始图中没有出现环路, 没有双向连通弧。满足这个条件, 其一般操作如下:

1) 将网络流图改画为无“逆流”的第二类网络图;

2) 在所得图中每相邻两点作一次切割, 所截得容量的最小值即位系统网络的最大流值。

现以此法来求解教材[5]上的例题, 其全题如下:

某石油公司拥有一个管道网络, 使用这个网络可以把石油从采地运送到一些销售点。这个网络的一部分如图1所示, 由于管道的直径的变化, 它的各段管道 (Vi, Vj) 的流量 (容量) Ci j也不是一样的, 这在图中标出。Ci j的单位为万加仑小时。如果使用这个网络从采地V1向销地V7运送石油, 问每小时能运送多少加仑石油?

按照一般步骤, 首先确定此图中没有出现环路与双向连通弧;再将其改画为无逆流的第二类网络图 (图3) ;再将每相邻两点间划一竖线, 计算所划过支流容量之和标于线下, 比较所有线下的标值, 其中最小值即为网络的最大流值。

计算得最大值为10, 与教材[5]用线性规划法所得结果一样。这也佐证了此方法的正确性。

参考文献

[1]Wayne L Winston.Operation Research[M].1994

[2]李昕伟.关于求网络最大流问题的另一种图解法[J].中国科技信息.2008, 3:98

[3]焦永兰.网络最小割计算的一点注记[J].数学的实践与认识.2008, 38 (6) :370-371

[4]谢凡荣.求解网络最大流问题的一个算法[J].运筹与管理.2004, 13 (4) :37-40

[5]韩伯棠.管理运筹学[M].高等教育出版社.2000.

简便算法篇2

吴磊埝桥镇游斜小学乘法结合律和简便算法

教学目的：

1、使学生理解并掌握乘法结合律，能够应用乘法交换律和乘法结合律进行简便运算。

2、通过观察、比较，培养学生初步的逻辑思维能力。教学重点难点：乘法结合律的应用。授课类型：新授课

教学方法：讨论法、尝试教学法授课时间：一课时教具准备：多媒体教学过程：

一、导入新课

教师谈话：前面我们学习了乘法交换律，今天我们进一步学习乘法结合律。

板书课题：乘法结合律和简便算法

问：同学们，看到课题，你想知道什么？

二、教学新课

1、学习乘法结合律

出示例2，让学生默读题目，弄清题中的条件和问题，齐读后，用两种方法解答出来。（5×4）×2 5×（4×2）

=20×2 =5×8 =40（个）=40（个）让学生说说解答思路。

教师：这两种思路，都求出共有40个球，既然这两个算式的结果是相同的，我们就可以用等号把这两个算式连接起来。比较一下等号两边的算式，她们的相同点是什么？它们的不同点是什么？再出示两组算式：（15×4）×10（）15×（4×10）（125×8）×5（）125×（8×5）仔细观察一下，这两个算式相等说明了什么？多让几个学生说一说。

比较上面的三个等式，仔细分析一下这三个等式，并回答下面的问题。这三个等式中，等号的两边都是几个数相乘？这三个等式中，等号两边的三个数系统吗？等号两边的算式有什么共同点？多让几个同学发言。让学生打开教科书看例2后面的结语，先请一个同学读一遍，再让全体学生齐读。接着，教师指出这叫做“乘法结合律” 用字母表示：a× b×c=a×(b×c)做第28页前半页“做一做”

2、教学例3 出示例3 43×25×4 如果按照运算顺序计算，应该先算什么？

想一想，怎样计算可以使计算比较简便？根据是什么？在学生讨论的基础上，教师板书： 43×25×4 =43×（25×4）=43×100 =4300

3、教学例4 出示例4 25×43×4 让学生讨论，这道题怎样计算比较简便？让学生自己做，集体订正。

教师板书：254×43×43×4 =25× =100×43 =4300 比较例3和例4的共同点，使学生知道在计算连乘时，可以先把能凑成整百或整十的数先乘起来，使计算简便。

三、巩固练习。

1、做第28页最后“做一做”中的题目。

2、做练习五的第6—9题。

四、作业：练习五的第10、11、12题。

五、小结

什么叫乘法结合律？附板书：

乘法结合律和简便算法（5×4）×2 5×（4×2）

简便算法篇3

常规做法:

如图1, 将某一整数的个位、十位用较大空白间隔开来, 而且个位、十位等依次按照由下到上的次序依次排列.

如图2, 将另一整数的个位、十位用同样间隔隔开, 个位、十位依次按照由左至右的次序排列.

由图1、2重叠后, 就构成了如图3的矩阵图形.

注:在读解图3这样的基本图形时, 按照由左至右, 由下到上的次序读解.由于A*B等于B*A, 所以按照先由下到上再由左到右的次序也可.

读解 (常规) :形如图3, 已知其表示的意义为13*21, 将直线的交点近似看成四个区域 (如图4) , 把左上方的交点群和右下方的交点群看做一个整体, 那么就把整个矩阵图形大体分为三个部分, 用直线分割, 得到图5.有图5得知, 在右上方的交点数为积的个位数, 中间两交点群中焦点数之和为十位数, 最后的交点群中的交点数为百位数.如图5, 第一交点群的交点数为3, 则13*21的积的末尾数字为3, 第二交点群 (第一组合交点群) 的交点数为7 (两交点群中交点数之和) ;第三交点群的交点数为2.由此可以得出答案:13*21等于273.

注:已知第一组合交点群为十位数, 在辨别个位数和百位数时, 先计算原两整数的末位数字之积, 可得一自然数, 再用此自然数与第一、第二交点群的交点数对应, 就可以得出个位和百位数 (口算得出) .例如13*21 (图4) 末位数字之积为3, 则就可以和第一交点群对应 (图5) .

非常规做法:

1. 当遇到两位数与一位数相乘时, 例如12*3的非常规做法读解.

首先按照由左到右, 由下到上的顺序绘图 (图6) .近似分出两个交点群 (上方, 下方) , 用直线分割 (为避免混淆, 可采用加长或改为波浪线的方法) , 在辨别个位数和十位数时: (1) 再次按照原两整数的末位数字之积进行分辨, 得出结果; (2) 根据特定顺序 (绘图时的特殊顺序) 得出结果.

2. 当遇到三位数与两位数相乘时的非常规做法.例如132*12.

首先按照由左至右再由下到上的顺序绘图 (图7) .在划分交点群落时, 可将原矩形阵列近似看成两个矩形阵列的组合 (其中一边重合的两个矩形阵列) , 再进行划分.读解:

口算得出两整数末尾数字的积 (如大于9, 则再取末位数字) , 再与图中的第一、第四交点群对应, 再按照命名次序 (见注二) 依次计算十位、百位.以第一交点群为例, 若交点数大于9, 则保留末位数字后进到下一位, 以此类推, 得出结果.图7中, 第一交点群的交点数为4, 第二交点群的交点数为8, 第三交点群的交点数为5, 第四交点群的交点数为1.由此可得两整数的积为1584.

3. 当遇到三位数与三位数相乘时的非常规算法.例如132*231.

首先按照由左至右再由下到上的顺序绘图 (图8) , 因绘图的特殊顺序, 所有交点群排列顺序都是按照由右上方到左下方的特定规律 (非常规做法1除外) .在划分交点群时, 也是按照交点群的排列顺序进行的.读解:

图中第一交点群的交点数为2, 第二交点群的交点数为9 (3+6) , 第三交点群的交点数为14 (1+9+4) , 向高次进一位后余4, 第四交点群的交点数为9 (3+6) , 下一位进位后为10 (9+1) , 再向高次进一位后余0, 第五交点群的交点数为2, 下一位进位后为3 (2+1) , 最终结果为30492 (最终结果由交点顺序所对应的交点数的反向组合) .

运算定律与简便算法，混合运算篇4

教学内容：教科书第93―94页，练习二十的第；一10题。

教学目的：

1．使学生掌握加法和乘法的运算定律。能够比较熟练地运用这些运算定律进行简便计算。

2．使学生掌握四则运算的运算顺序．能正确计算四则混合运算。

教学过程（）：

一、运算定律

教师：“我们在学习四则运算时．学过哪些运算定律?”指名用自己的话说出运算定律，并举例说明。然后用字母表示出来：教师根据学生的回答，整理成教科书第93页的表。

如果学生只举整数的例子，教师可以引导学生想一想：运算定律除了对整数加法和乘法适用以外，对小数和分数的加法、乘法适用吗?让学生再举几个有关小数、分数加法和乘法的例子。

下面的式子有没有错误?把错的地方改正过来。

(4．3十2．5)×4＝4．3×4×2．5×4

(700十1)×68＝700×68十68

153×(220十57)＝153×220十57

63×8十37×8；(63十37)×(8十8)

还可以做练习二十的第8题。

教师：“在我们学过的知识里哪些地方应用丁运算定律?”可以多让几个学生说一说。如果学生掌握得比较好，还可以让学生用运算定律解释―下积、商的变化规律：如：在乘法里。如果一个因数扩大10倍，另一个因数不变，那么积就扩大10倍：可

以用下面的式子说明：

(a×10)×b＝a×10×b＝a×b×10＝(a×b)×10

这里应用了乘法的交换律和结合律。

二、简便算法

教师：“应用运算定律可以使―些计算简便。谁能举个例子?”

接着出示教科书第93页的例1、先让学生观察题目中的数有什么特点。然后让学生说一说应该用什么运算定律。说完后，让学生独立完成计算。

集体订正时．教师再提问：这道题是怎样应用运算定律的?应用了哪些运算定律?使学生明确：在计算时．不仅计算的开始有时可以用简便方法进行计算，在计算的过程中有时也可以用简便方法进行计算。

教师：“在计算时，要随时注意用简便方法进行计算、”

做教科书第93页“做一做”中的题目。

教师说明题目要求后。让学生独立计算。教师巡视，对学习有困难的学生进行个别辅导。集体订正时．让学生说一说每道题是怎样用简便方法计算的。特别是下面二道题，是怎样进行简便计算的?

567十98 1 ― ― 21 ÷7

教师要提醒学生：有的`算式可能存在几种不同的算法，所以。在运算前要认真审题．看清算式中各个数的特点、选用―种比较简便的算法，使计算又对又快。

三、四则混合运算

引导学生回忆四则混合运算的有关概念和运算顺序。

“什么叫做第一级运算?什么叫做第―级运算：”

“在一个算式中如果只含有同―级运算、运算顺序是怎样的：”

“在一个算式中如果含有第―级和第二级两级运算。应该先算什么?”

“在含有括号的算式中。应该先算什么?再算什么?”

出示教科书第94页中间的算式．让学生标明运算顺序。

教师：“在计算混合运算的式题时．首先要认真审题，看清题中有哪些运算符号．确定运算的顺序。”

出示教科书第94页的例2。先让学生认真审题。想一想运算顺序。然而让学生独立计算。教师巡视。了解学生掌握的情况、对个别学生进行辅导，集体订正时，指名说一说运算的顺序。同时，还要注意强调书写的格式。

做练习二十的第9题。学生独立计算。集体订正。

四、小结(略)

基于ISM的可达矩阵的简便算法篇5

本文阐述的由邻接矩阵求可达矩阵的新算法, 较之以前运用普遍的Warshall算法更简便, 计算量大大减小, 可以作为以后普遍适用的新算法。该新算法的推广将会使解释结构模型化技术的应用更简便易行。

1 解释结构模型 (ISM)

解释结构模型化技术是最基本、最具特色的系统结构模型化技术。其基本思想是:通过各种创造性技术, 提取问题的构成要素, 利用有向图、矩阵等工具和计算机技术, 对要素及其相互关系等信息进行处理, 最后用文字加以解释说明, 明确问题的层次和整体结构, 提高对问题的认识和理解程度。ISM的基本工作原理如图1所示。

2 常用的Warshall算法

2.1 邻接矩阵

邻接矩阵 (A) 是表示系统要素间基本二元关系或直接联系情况的方阵。若A= (aij) n×n, 则其定义式为:

2.2 邻接矩阵的特征

①“1”的个数与系统要素集合S上的二元关系集合Rb所包含的要素对数相等, 与有向图的弧的条数相等。

②每行中1的数量, 等于离开该节点的弧数, 每列中1的数量, 等于进入该节点的弧数。

如:根据有向图

得到的邻接矩阵为:

2.3 可达矩阵

可达矩阵 (M) 是表示系统要素之间任意次传递性二元关系或有向图上两个节点之间通过任意长的路径可以到达情况的方阵。

若可达矩阵M= (mij) n×n则其定义为:

如:根据有向图

得到的可达矩阵为:

2.4 求可达矩阵的Warshall算法

①Warshall算法步骤:可达矩阵与邻接矩阵存在必然的联系。可达矩阵M可用邻接矩阵A加上单位阵I, 经过演算后求得。

若:A1≠A2≠, …, ≠Ar=Ar+1 (r<n-1) =An= (A+I) n, 则:Ar=M为可达矩阵。

②可达矩阵的运算规则:矩阵运算规则和布尔代数运算规则。布尔代数的运算规则:矩阵A和M的元素均为“1”或“0”, 是n*n阶0-1矩阵。0-1矩阵运算时遵循布尔代数的运算规则:

③Warshall算法求可达矩阵举例:

同样是根据有向图

由邻接矩阵A求可达矩阵M的过程如下:

A1描述了各点间经长度不大于1的路径的可达情况。

A2描述了有向图中各点间经长度不大于2的路径的可达情况。

1→2→3→4, “1”经过长度为3的路径到达“4”, 即它描述了各点间经长度不大于3的路径的可达情况。

A4=A3计算结束。

Warshall算法适合于由计算机产生可达矩阵。

3 由邻接矩阵求可达矩阵的简便算法

3.1 原理

此简便方法中的邻接矩阵同Warshall算法中的邻接矩阵, 同样采用布尔代数运算规则。

原理:∵对邻接矩阵A, 如果有aij=1, 且ajk=1, 则一定有aik=1。∴对邻接矩阵A, 如果有aij=1, 且对于A的转置矩阵AT有akj=1, 则一定有aik=1。所以只要将A和AT对应列的1元素所在的行数列出, 并进行排列组合, 即可得出所有的aik=1。

3.2 简便算法的操作步骤

①建立邻接矩阵A及其转置矩阵AT;

②将A和AT中对应列逐一比较, 将其中为1元素的行提取出来列在表中, 分别作aij的i和j的排列组合, 形成新的aij=1。将得到的新的aij=1元素填入到A中;

③重复第②步, 直到A中的元素不再变化;

④将A的主对角线元素全部用1替换, 即得到M。

3.3 举例说明

(1) 仍以有向图为例,

邻接矩阵

②由表1可以看出, a13=1, a24=1, 将其加入到A中。

③重复第②步。将a13=1, a24=1加入到A中得到:

由表2可知, a13=1, a14=1, a24=1, 将a14=1加入到A中。

继续重复第②步, 将a14=1加入到A中得到:

由表3可得, a13=1, a14=1, a24=1, 没有形成新的aij=1, 所以不再迭代。

④最后, 将A的主对角线元素全部改成1, 即得到M。

此方法较Warshall算法操作更简便, 简单易懂, 运算量大大减小。

4 结语

本文基于ISM有向图, 以矩阵运算和布尔代数运算为原则, 探索出建立递阶结构模型中由邻接矩阵求可达矩阵的一种新算法。利用矩阵运算中转置矩阵AT中的元素aij等于原矩阵A中的元素aji, 结合可达矩阵中元素直接可达, 间接可达及自身可达的性质, 由邻接矩阵依次找出间接可达和自身可达的元素关系, 进而求得可达矩阵。该方法操作简单, 较传统的可达矩阵求法而言, 大大减少了计算量, 使建立递阶结构模型更简便易行, 对解释结构模型 (ISM) 的普遍应用将起到一定的推动作用。另外, 该算法完全可以实现计算机化, 这可以作为下一步的研究内容。

摘要：解释结构模型化技术是最基本、最具特色的系统结构模型化技术, 求可达矩阵又是建立递阶结构模型 (ISM) 中最重要的一步, 本文基于ISM有向图, 根据布尔代数运算规则, 阐述一种更简便的由邻接矩阵求可达矩阵的新算法。本文与Warshall算法作对比, 体现出该新算法的简便之处。该算法以后也可以实现计算机化。

关键词：解释结构模型,邻接矩阵,可达矩阵,新算法

参考文献

[1]杨伟丽.基于ISM有向图的求可达矩阵的简洁算法[D].厦门大学.

[2]汪应洛 (西安交通大学) 主编.系统工程[M].四版.机械工业出版社.

[3]王秋萍, 梁戈.求可达矩阵的Warshall算法[J].西安理工大学学报, 1996, 12 (1) :80-82.

超几何分布高阶矩的一种简便算法篇6

概率论与组合数学关系密切, 把组合数学的知识引用到概率论的问题中去有着重要的意义。在离散型随机变量的分布中, 超几何分布是常用的分布之一, 有必要对它的重要数字特征原点矩进行研究, 但使用定义计算其高阶原点矩比较复杂。下面讨论如何利用组合数学中的第二类Stirling数计算超几何分布的各阶原点矩[1,2], 并给出简单的计算式。

1 预备知识

一个坛子里有N个球, 其中M个白球, N-M个黑球, 随机地 (无放回) 从中取出大小为n的样本, 令X表示取出来的白球数, 那么

$Ρ {X = k} = \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})}, k = 0, 1, \dots, n (1)$

定义1[3] 一个随机变量X, 如果其概率分布由公式 (1) 给出, 那么X就称为超几何随机变量, 相应的分布叫做超几何分布, 记作X—H (M, N, n) 。

在这里需要说明的是, 虽然我们把超几何随机变量的取值从0写到了n, 但事实上P{X=k}等于0, 除非k满足n- (N-M) ≤k≤min (n, M) 。并且我们规定在k<0或r<k时, 等于0, 这样 (1) 式一般来说是成立的。

定义2[4,5] 设离散型随机变量X的分布律为

$Ρ {X = x_{i}} = p_{i}, i = 1, 2, \dots$

若E (Xm) , m=1, 2, …存在, 则称它为X的m阶原点矩, 即

$E (X^{m}) = \sum_{i = 1}^{\infty} x_{i}^{m} p_{i} 。$

2 主要结果

本文均假设随机变量X～H (M, N, n) , 那么按照原点矩的定义分别计算X的1, 2, 3, 4, …阶原点矩, 得到

$\begin{array}{l} E X = \sum_{k = 0}^{n} k \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{k = 1}^{n} \frac{\frac{Μ!}{(k - 1)! (Μ - k)!} (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} 。令 \end{array}$

$\begin{array}{l} k - 1 = l = \sum_{l = 0}^{n - 1} \frac{\frac{Μ!}{l! (Μ - 1 - l)!} (\begin{array}{l} Ν - Μ \\ n - 1 - l \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \frac{Μ n}{Ν} \sum_{l = 0}^{n - 1} \frac{\frac{(Μ - 1)!}{l! (Μ - 1 - l)!} (\begin{array}{l} Ν - 1 - (Μ - 1) \\ n - 1 - l \end{array})}{(\begin{array}{l} Ν - 1 \\ n - 1 \end{array})} = \\ \frac{Μ n}{Ν} \sum_{l = 0}^{n - 1} \frac{(\begin{array}{l} Μ - 1 \\ l \end{array}) (\begin{array}{l} Ν - Μ \\ n - 1 - l \end{array})}{(\begin{array}{l} Ν - 1 \\ n - 1 \end{array})} = \\ \frac{Μ n}{Ν} = \frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} ； \end{array}$

$\begin{array}{l} E X^{2} = \sum_{k = 0}^{n} k^{2} \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{k = 1}^{n} [k (k - 1) + k] \frac{\frac{Μ!}{k! (Μ - k)!} (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{k = 2}^{n} \frac{\frac{Μ!}{(k - 2)! (Μ - k)!} (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} + \\ \sum_{k = 1}^{n} k \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} \times \\ \sum_{k = 2}^{n} \frac{\frac{(Μ - 2)!}{(k - 2)! (Μ - k)!} (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν - 2 \\ n - 2 \end{array})} + \frac{Μ n}{Ν} = \\ \frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} + \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} ； \end{array}$

同样的方法可得

$\begin{array}{l} E X^{3} = \sum_{k = 0}^{n} k^{3} \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} + \\ 3 \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} + \frac{[Μ]_{3} [n]_{3}}{[Ν]_{3}} ； \\ E X^{4} = \sum_{k = 0}^{n} k^{4} \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} + \\ 7 \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} + 6 \frac{[Μ]_{3} [n]_{3}}{[Ν]_{3}} + \frac{[Μ]_{4} [n]_{4}}{[Ν]_{4}} ； \end{array}$

其中, [n]l为n的l下阶层,

$\begin{array}{l} [n]_{l} = \\ {\begin{matrix} 1, & l = 0, \\ (\begin{array}{l} n \\ l \end{array}) l! = n (n - 1) \dots (n - l + 1), & 1 \leq l \leq n, \\ 0, & l > n 或 l < 0 。 \end{matrix} \end{array}$

从计算结果可以看出, 超几何分布的各阶原点矩的结果形式有一些特点:X的m阶矩是 $\frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} ‚ \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} ‚ \dots ‚ \frac{[Μ]_{m} [n]_{m}}{[Ν]_{m}}$ 的一个线性组合, 且 $\frac{[Μ]_{1} [n]_{1}}{[Ν]_{1}} ‚ \frac{[Μ]_{2} [n]_{2}}{[Ν]_{2}} ‚ \dots ‚ \frac{[Μ]_{m} [n]_{m}}{[Ν]_{m}}$ 前面的系数 (记作A (m, l) ) 之间也有一定的关系。这些系数见表1。

观察表1中由数字构成的三角形可以看到:三角形中的每一项, 但不是三角形两条边上的那些项, 通过用l乘以该项的正上方元素, 并将结果加上该项的左上方的元素而得到, 例如7=2×3+1。

下面给出利用第二类Stirling数计算超几何分布的各阶原点矩的定理, 此定理可以对上述计算结果的规律性做出很好的阐述。

定理:若随机变量X～H (M, N, n) , 则X的m阶原点矩可由公式

$E X^{m} = \sum_{l = 0}^{m} S (m, l) \frac{[Μ]_{l} [n]_{l}}{[Ν]_{l}} (2)$

计算得出, 其中S (m, l) 为第二类Stirling数, [n]l为n的l下阶层。

在组合数学[6]中已知nm可以表示成下述形式

$\begin{array}{l} n^{m} = S (m, 0) [n]_{0} + S (m, 1) [n]_{1} + \dots + \\ S (m, m) [n]_{m} = \sum_{l = 0}^{m} S (m, l) [n]_{l} \end{array}$

S (m, l) 即为组合数学中的第二类Stirling数, 其初始值为:

$\begin{array}{l} S (m, 0) = {\begin{matrix} 1 & m = 0 \\ 0 & m \geq 1 \end{matrix} \\ S (m, m) = 1, (m \geq 0) 。 \end{array}$

下面证明此定理。

证明已知X的分布律为

$Ρ {X = k} = \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})}, k = 0, 1, \dots, n,$

且

则

$\begin{array}{l} E X^{m} = \sum_{k = 0}^{n} k^{m} \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{k = 0}^{n} \sum_{l = 0}^{m} S (m, l) [k]_{l} \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{l = 0}^{m} \sum_{k = 0}^{n} S (m, l) l! (\begin{array}{l} k \\ l \end{array}) \frac{(\begin{array}{l} Μ \\ k \end{array}) (\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \\ \sum_{l = 0}^{m} S (m, l) \sum_{k = l}^{n} l! \frac{k!}{l! (k - l)!} \frac{Μ!}{(Μ - k)! k!} \\ \frac{(\begin{array}{l} Ν - Μ \\ n - k \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \sum_{l = 0}^{m} S (m, l) \sum_{r = 0}^{n - l} \frac{Μ!}{r! (Μ - l - r)!} \times \\ \frac{(\begin{array}{l} Ν - Μ \\ n - l - r \end{array})}{(\begin{array}{l} Ν \\ n \end{array})} = \sum_{l = 0}^{m} S (m, l) \frac{[Μ]_{l} [n]_{l}}{[Ν]_{l}} \times \\ \sum_{r = 0}^{n - l} \frac{(\begin{array}{l} Μ - l \\ r \end{array}) (\begin{array}{l} Ν - Μ \\ n - l - r \end{array})}{(\begin{array}{l} Ν - l \\ n - l \end{array})} = \\ \sum_{l = 0}^{m} S (m, l) \frac{[Μ]_{l} [n]_{l}}{[Ν]_{l}} 。 \end{array}$

所以定理成立。

同时, 由第二类Stirling数的递推关系式

$S (m, l) = l S (m - 1, l) + S (m - 1, l - 1) (3)$

及其初始值, 可以计算出每一个S (m, l) 。实际上, 一开始提到的系数A (m, l) 就是S (m, l) , 而所给表格中三角形的每一项刚好由S (m, l) 的初始值及其递推关系式计算得到, 此表格记作S (m, l) 三角形表。

3 实例

例已知随机变量X服从参数为M=6, N=10, n=4的超几何分布, 计算X的8阶原点矩。

解利用定理中所给的计算公式 (2) , 有

$E X^{8} = \sum_{l = 0}^{8} S (8, l) \frac{[6]_{l} [4]_{l}}{[10]_{l}} 。$

由递推关系式 (2) 计算出S (8, 0) , S (8, 1) …, S (8, 7) , S (8, 8) 的值分别为:0, 1, 127, 966, 1 701, 1 050, 266, 28, 1, 将这些值代入上式得

$\begin{array}{l} E X^{8} = 1 \times \frac{[6]_{1} [4]_{1}}{[10]_{1}} + 127 \times \frac{[6]_{2} [4]_{2}}{[10]_{2}} + \\ 966 \times \frac{[6]_{3} [4]_{3}}{[10]_{3}} + 1 701 \times \frac{[6]_{4} [4]_{4}}{[10]_{4}} = \\ 7 290.4 \end{array}$

参考文献

[1]李金秋.二项分布高阶原点矩的一种简便算法.辽宁石油化工大学学报, 2008;28 (1) :89—91

[2]刘丹.关于几何分布高阶矩的计算问题的研究.吉林师范大学学报 (自然科学版) , 2009;2:129—131

[3][美]Ross S M.概率论基础教程.郑忠国, 詹从赞, 译.北京:人民邮电出版社, 2007:134—136, 173—185

[4]盛骤, 谢式千, 潘承毅.概率论与数理统计.北京:高等教育出版社, 2008:90—110

[5][美]威廉.费勒.概率论及其应用.胡迪鹤, 译.北京:人民邮电出版社, 2006:39—40

简便算法篇7

对流层散射通信过去多用于中、远距离, 通信距离通常都在100 km以上[1,2]。但在许多应用场合, 如在一些局域网中, 其通信区域在100 km的范围内, 节点之间的通信距离小于100 km。因此, 对于在50 ~100 km距离上的通信, 在这一通信距离上使用散射能很好地解决这一问题, 是应用领域的扩展。散射近距离通信具有相当大的优势: 散射一跳就能够达到这个距离, 无需接力, 这就给使用带来了很大的便利; 对于散射而言, 通信距离的缩短可以使得传输速率[3]提高, 设备的发射功率下降, 功耗减小, 成本降低。因此, 研究散射近距离通信是很有意义和广阔发展前景的。

1 实验系统

目前在快速预计散射近距离传输损耗方面, 国外在此范围内尚无测试数据。过去散射通信设备的设计是基于远距离传输条件, 工程中[4]经常采用的传输损耗的计算方法有ITU-R P.617-1建议的中国方法[5]、美国的NBS方法[6]和CCIR方法等[7]。但近距离条件下的电波传播模式及传输损耗与现有计算方法是否吻合, 需要通过实验验证。

国内外散射设备大多是C波段 ( 4 400 ~5 000 MHz) , 这里重点研究C波段对流层散射通信信号近距离传输特性[8]。试验系统主要包括: 天线、发射机、接收机和多功能测试终端, 如图1所示。系统由一面天线发射、两面天线接收, 天线口径为2. 4 m, 可测试信道电平衰落特性、频率相关特性、多径时延和空间相关特性等[9,10,11]。

2 实验线路

实验区域在华北地区, 选择较为平坦的地形环境, 无近距离遮挡。通信距离为5 ~183 km, 并选择一条183 km的远距离线路作为参考, 以便与近距离线路的测试数据进行比较。共有7条线路, 各线路基本处于一条直线上, 具体线路如表1所示。

典型线路剖面图如图2所示。

由图2路径剖面图可看出, 近距离散射通信典型应用环境是无近端遮挡, 基本上处于平坦地理环境。

典型的远距离对流层通信路径剖面图如图3所示, 此线路的测试结果可用来与近距离线路条件对比。

3 实验结果及数据分析

3. 1 传播损耗

在华北地区不同距离的线路上测试的中值对流层散射传播损耗如表2所示。

通过表2的测试数据, 可画出传输损耗与距离的关系如图4所示。图中实线为测试曲线, 虚线为拟合曲线。

根据图4可得到一种简便的散射传输损耗的工程预计方法:

式中, d为通信距离 ( km) 。

可以看出, 在70 km以内传播损耗L ( dB) 与距离d呈线性变化趋势, 大于75 km时传输损耗与距离的5次方成正比。

由于散射传输损耗与气候条件有关, 国际上通常分为7个气候区类型: 1—赤道, 2—大陆性亚热带, 3—海洋性亚热带, 4—沙漠, 6—大陆性温带, 7a—海洋性温带 ( 陆上) , 7b—海洋性温带 ( 海上) 。分别对应于不同的气候区损耗值M =[39. 60, 29.73, 19. 30, 38. 50, 29. 73, 33. 20, 26. 00]。上述测试结果是在大陆温带区, 因此, 上述方法用于其他气候区时应加上与大陆温带区损耗的差值。

目前常用的3种散射传输损耗算法与本文中简便算法的对比如表3所示, 可以看出其间的误差很小。

表3中气候区为: “6”—大陆性温带; 大气折射指数Ns取310。

3. 2 近距离散射线路传输损耗分析

由图4可知, 近距离对流层散射通信线路传输损耗随距离的变化规律与远距离线路有较大不同。近距离时有可能是绕射、对流层散射以及地面反射等信号分量共同的作用。

3. 2. 1 地波绕射损耗

光滑球面的绕射损耗 ( 相对于自由空间损耗) 可由式 ( 2) 近似计算[2]。

d为通信距离 ( km) ; ae为等效地球半径 ( km) ; f为工作频率 ( MHz) ; dt, dr为收发天线到无线地平线的距离 ( km) 。

3. 2. 2 树木遮挡损耗

绕射损耗的计算是在理想条件下进行的。实际上, 在C波段的微波频率地形地貌对绕射的影响很大, 实测线路中主要有树木的影响。

根据ITU-R P.833 -2建议, 穿入树林的附加损耗可以表为[12]:

式中, Am为穿入树林传播的最大衰减量 ( dB) ; γ为树林中的短程衰减率 ( dB/m) , 对于4 800 MHz的频率, γ1 dB/m; d为电波在树林中穿行的距离 ( m) 。

关于最大衰减量, 现在仅有900 ~1 800 MHz频率范围的测量统计结果 ( 热带林情况) :

式中, 频率f以MHz计。

若以此作为参考计算, 则50 m的树林附加损耗近40 dB。

3. 2. 3 绕射传播和散射传播损耗

在近距离通信时, 应是绕射传播和散射传播共同作用, 其结果使得传播损耗小于单纯的散射损耗。

光滑球面的绕射损耗计算值以及对流层散射传输损耗计算值与实测值的比较曲线如图5所示。绕射损耗曲线由式 ( 2) 得到, 对流层散射损耗的计算采用ITU-R P.617 -1算法。

从图5中可以看出, 70 km以上的传输损耗实测值与计算值十分吻合, 即在远距离条件下, 简便计算方法是适用的。在小于70 km距离范围内, 绕射传输损耗或对流层散射传输损耗的计算值均与测试值有较大偏差。总体来看, 在50 km以内的范围内, 绕射损耗小于散射损耗, 起主要作用。绕射损耗的计算值小于实测值主要是由于计算是基于比较理想的条件, 实际线路上存在树木和建筑物的遮挡, 会增加绕射传输损耗; 而在50 ~70 km范围内, 是绕射传播与散射传播共同起作用; 大于70 km时主要是对流层散射传播。图中在小于20 km时实测损耗较大, 是由于实际线路上由于通信前方树木的影响, 使得散射角增大, 会造成20 dB以上的损耗。

由上述实测数据与计算结果比较可知, 近距离条件下, 散射信道传输损耗与远距离相比有一定变化, 远距离散射下所建立的模型应用于近距离时应做修正。

4 结束语

近距离散射传播在一定的条件和距离下, 存在1种或几种传播模式, 主要是散射和地波绕射。其线路损耗主要是对流层散射损耗、地波绕射损耗以及由于树木遮挡造成的损耗。远距离则以散射为主。上述给出的散射传输损耗的简便算法适用于远距离线路, 为在工程设计和应用中快速预计散射损耗提供了便利的方法。而近距离线路上由于绕射传播与地形环境、树木或建筑物等的遮挡、地质结构以及地面植被等多种因素有关, 传输损耗模型的建立较为复杂, 需要大量数据的支持, 简便算法准确性需做进一步验证。

摘要：通信距离小于100 km的对流层散射线路关于信道特性的测量数据较少, 现有的算法不能快速预计传输损耗。为了解决这个问题, 试验通过对多条不同距离下散射信道的实测, 分析了电波传播的几种模式, 与现有算法进行了对比, 提出了对流层散射传输损耗的一种简便工程算法。试验结果表明, 提出的算法可以快速预计传输损耗。

关键词：近距离散射传输,散射损耗简便算法,快速预计,散射、绕射混合传播

参考文献

[1]中国人民解放军总参谋部通信部.对流层散射远距离通信[M].北京:中国人民解放军战士出版社, 1982:41-56, 186-195.

[2]刘圣民, 熊兆飞.对流层散射通信技术[M].北京:国防工业出版社, 1982:34-37, 51-67.

[3]周现国, 殷素杰.一种基于散射信道极低速率检测技术研究[J].无线电通信技术, 2012, 42 (4) :60-62.

[4]穆维新.现代通信工程设计[M].北京:人民邮电出版社, 2007:11-18.

[5]Rec.ITU-R P.617-1.Propagation Prediction Techniques and Data Equired for The Design of Trans-Horizon RadioRelay Systems[S], 1992.

[6]张明高.对流层散射传播[M].北京:电子工业出版社, 2004:36-64.

[7]Rec.ITU-R P.833-6.Attenation in Vegetation[S], 2007.

[8]甘国田.迅速发展的对流层散射通信[J].计算机与网络, 1997 (3) :15-20..

[9]刘丽哲.新型散射信道测试机的设计与实现[J].无线电工程, 2012, 42 (11) :48-50.

[10]甘启光, 李文明.基于USB接口的对流层散射信道测试设备[J].无线电工程, 2009, 39 (10) :58-61.

[11]徐松毅.散射信道测量方法研究[J].无线电通信技术, 2003, 29 (3) :5-7.

简便算法篇8

人教版小学数学第八册第三单元“加、减法的一些简便算法”的教学,是使学生初步认识“从一个数里连续减去两个数,等于从这个数里减去两个减数的和”的运算规律,学会运用这种规律进行简便计算。在教学这节课时,我围绕“教学目标”设计如下:

1. 从生活中寻找规律

数学是从现实世界中抽象出来的,生活中处处有数学。从学生们熟悉的生活情境和感兴趣的事物出发,创设如下情境:

(1)出示图并提问:

上衣:31元、48元、36元、43元

裤子:42元、30元、44元、49元

如果让你自己去选购一套衣服,你会怎么做?

(2)引导学生列出不同的算式。

提问:你付100元,则应找回多少元?

学生列式解答,老师板书出不同的算式:

这样从学生已有的知识和经验为基础,将数学问题生活化,使数学当作生活的必需来学习和研究,使学生感觉到数学就在我们的身边,就在我们的生活中。

2. 从讨论中发现规律

“讨论”是在教师引导下的学生自主学习行为,具有一定的民主性和自由探索性,可以更好地激发学生的学习兴趣,拓宽学生的参与面,调动学生学习的主动性和积极性。出示两组不同的列式:100-31-42=27100-(31+42)=27,设置这样一个讨论交流的空间让学生去发现规律:“仔细观察这两组算式,你发现了什么?”

交流发现:

“这两组算式中虽然列式不同,但计算结果相同。”

“左边的算式与右边的算式相等。”

“左边的算式先算买了一件衣服后还剩下多少钱,右边的算式先算一套衣服要多少钱。”

“从一个数里连续减去两个数,等于这个数减去两个数的和。”

讨论进入高潮,这条规律已被揭示出来。同时学生们通过互相讨论,互相启发,互相帮助,探讨知识之间的内在规律,充分发挥学生间的互补作用,培养学生的合作精神,促使学生更好地学习。

3. 从举例中验证规律

借助具体数据、事例,通过自主探索活动,将抽象的数学关系、事实、结论等具体化,从而巩固得出的规律性知识。所以在学生们发现规律后还需要进行必要的验证。

(1)学生举出:1200-560-300

学生计算后该规律仍能适用。

教师问:你们还能举出这样的两个算式吗?(你能举多少?)(无数个)

根据学生的回答引出这条规律对任何这样的两个算式都能成立。