第二章测量程序基本算法

1、第二章第二章 测量程序基本算法测量程序基本算法本章重点本章重点 算法的概念及特性，数据文件的建立、读写、显示 ，矩阵运算，排序算法，坐标方位角的计算2.1 算法（Algorithm）及其表示2.1.1 概念广义地讲：广义地讲：算法是为完成一项任务所应尊循的一步一步的、规则的、精确的、无歧异的描述，它的总步数是有限的。狭义地讲：算法是解决一个问题采取的方法和步骤的描述。例1：找出三个数中的最大的数。 假如三个数已存放在数组a(2)中了，用Max存储最大的数。 算法设计如下：算法设计如下： 1）比较a(0)与a(1)，将大的数放到Max中； 2）比较Max与a(2)，若Max小于a(2)，将a(2

2、)赋值给Max。 例2：输入10个数，输出其中最大的数。 算法设计如下：算法设计如下： 1）输入一个数，存入变量A中，将记录数据个数的变量N赋值为1，即N=1； 2）将A存入表示最大值的变量Max中，即Max=A； 3）再输入一个值给A，如果AMax 则 Max=A, 否则Max不变； 4）让记录数据个数的变量增加1，即N=N+1； 5）判断N是否小于等于10，若成立则转到第（3）步执行，否则转到第（6）步； 6）输出max。2.1.2 算法的特性v有穷性有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每一步骤都能在有限时间内完成。v确定性确定性 对于每种情况下所应执

3、行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明白其含义及如何执行。v可行性可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现它；v有输入有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已经被嵌入算法中；v有输出有输出 它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。2.1.3算法设计的原则算法设计的原则设计算法时，通常应考虑达到以下目标：1 1、正确性、正确性对算法是否“正确”的理解可以有以下四个层次：a.程序中不含

4、语法错误；b.程序对于几组输入数据能够得到出满足要求的结果；c.程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；d.程序对于一切合法的输入数据都能得出满足要求的结果；2 2、可读性、可读性 算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难度的程序易于隐藏较多错误而难以调试；3 3、健壮性、健壮性 当输入的数据非法时，算法应当恰当地作出反应或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4 4、高效率与低存储量

5、需求、高效率与低存储量需求 通常，算法的效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。2.1.4 算法的表示1）用自然语言及伪代码来表示 自然语言：自然语言：是指人们日常使用的语言，可以是汉语、英语或其它语言。 伪代码：伪代码：是用介于自然语言和计算机语言之间的文字和符号（包括数学符号）来描述算法。 例例1 1用伪代码表示用伪代码表示 Begin Begin 算法开始算法开始 If a(0)a(1) If a(0)a(1) 则则 a(0)-Max a(0)-Max 否则否则 a(1)-Maxa(1)-Max If a(2)Max If a(2)M

6、ax 则则 a(2)-Maxa(2)-Max End End 算法结束算法结束2）用传统流程图来表示 1、传统流程中的基本符号起止框I/O框流程线处理框判断框 2、三种基本结构的表示 顺序结构选择结构语句1语句2条件语句1语句2YN循环结构当循环 直道循环条件( a )YN语句组条件语句组YN( b )三种基本结构的特点：三种基本结构的特点：v只有一个入口v只有一个出口v不存在死语句v不存在死循环从10个数中选出最大的数的算法流程图NMaxMax =A输入A再输入给AN=N+1结束YNNY开始打印Max3）用NS流程图表示 将全部算法写在一个矩形框内，在矩形内还可包含其它从属于它的框。三种基本

7、结构的三种基本结构的NS图表示：图表示： 语句A语句B循序结构选择结构语句A语句B条件YN循环结构循环结构当循环直道循环语句组当条件成立语句组直到当条件成立例例4 画出从画出从10个数中选出最大的数的个数中选出最大的数的NS 流程图流程图传统流程图NMaxMax =A输入A开始再输入给AN=N+1输出Max结束YNNY输入A当NMaxYN输入A2.2 测量程序中几种算法2.2.1 数据文件操作（读写文件）数据文件操作（读写文件） 数据在计算机里的存储格式五花八门。如Image，它可以以Bmp、Jpeg、Tif等格式来存储；又如对于GPS数据文件，不同的仪器型号，它的数据记录格式一般是不一样的。

8、 测量程序处理的对象主要为野外采集原始数据。（外业观测数据、已知数据以及网形数（外业观测数据、已知数据以及网形数据）。据）。计算的开始、结束以及计算过程中，会涉及数据的读取、存储（中间计算结果）以及输出（成果）。那么我们进行程序设计时以那种形式的文件来记载数据呢？数据在存储到文件中又怎样来组织呢?在VB6.0中读取该格式的文本数据要到:CommonDialog外部控件、For循环、Whileloop以及lineInput语句开 始是 否 为 * .tx t逐 行 读取 文 本是 否 位 于 文件 尾 了打 开 * .tx t结 束文本操作算法流程文本操作算法流程NYYN2.2.2 矩阵运算矩阵

9、运算 编程对矩阵运算进行实现时，一般需在内存中申请一块连续的空间来存储矩阵中各个元素。在C+语言中，可以定义一个指针来指向内存中所申请的地址；在VB中，可利用数组（可以用一维数组，也可以用二维数组）存储矩阵中的各个元素。A(0)A(1)A(2)A(n). 一维数组在内存中存放的顺序一维数组在内存中存放的顺序1）两矩阵相加）两矩阵相加 矩阵A、B相加就是矩阵对应的元素相加即可实现。 for i=0 to m-1 for j=0 to n-1 c(i, j)=a(i,j)+b(i, j) next nextN矩阵相加流程2）两矩阵相减）两矩阵相减 矩阵A、B相加就是矩阵对应的元素相加即可实现。 f

10、or i=0 to m-1 for j=0 to n-1 c(i, j)=a(i,j)-b(i, j) next nextN矩阵相减流程3）矩阵转置）矩阵转置 通过将a(i,j)元素放到b(j1,i1)即可实现矩阵转置。在VB实现时先定义一个存储a(i,j)转置后的矩阵b(j,i)。 for i=0 to m-1 for j=0 to n-1 b(i,j)=a(j,i) next next4）矩阵相乘）矩阵相乘 矩阵A有m*l个元素，矩阵B有l*n个元素，则矩阵C=A*B有m*n个元素,矩阵C中任一元素 lkjkbkiajic1),(), (), ( (i=1,2,m; j=1,2,n) 开始

11、A矩阵的列与B行是否相等a(i, k) * b(k, j)结束两矩阵相乘流程 for i=1 to m for k=1 to n c(i, j) = 0 for j=1 to l c(i, k) = c(i, j) + a(i, j) * b(j, k) next j:next k:Next i 定义四个变量b,c,d , M分别存储度、分、秒以及最终结果。2.2.3 不同单位角度的转化不同单位角度的转化度分秒转度度分秒转度 M=a+c/60+d/3600度分秒转弧度度分秒转弧度 定义四个变量b,c,d,M分别用来存储度、分、秒及最终结果。M=a+c/60+d/3600M=M*3.1415/1

12、802.2.4 排序算法排序算法1） 选择法排序（升序）选择法排序（升序） 基本思想：基本思想：（1）对有n个数的序列（存放在数组a(n)中），从中选出最小的数，与第1个数交换位置；753468 91排序开始排序开始前前a(n)：第第1遍交换后：遍交换后：753468 91 71（2）第二遍时，除第1 个数外，其余n-1个数中选最小的数，与第2个数交换位置；735468 91 71第第2遍交换后：遍交换后：（3）依次类推，选择了n-1遍后，这个数列已按升序排列。 选择法排序算法的流程图选择法排序算法的流程图选择法排序（升序）的VB程序：for i1=1 to n-1 n-1趟遍历 P=i1 f

13、or i2=i1+1 to n 1次遍历 if a(P)a(i2) then P=i2 end if next i2 temp=a(i1):a(i1)=a(P):a(P)=temp next i1思考：选择排序降序算法怎样？思考：选择排序降序算法怎样？2 2） 冒泡排序（升序冒泡排序（升序）基本思想：基本思想：(将相邻两个数比较，小的调到前头)（1）有n个数（存放在数组a(n)中），第一趟将每相邻两个数比较，小的放到前头，经n-1次两两相邻比较后，最大的数已“沉底”，放在最后一个位置，小数上升“浮起”；（2）第二趟对余下的n-1个数（最大的数已“沉底”）按上法比较，经n-2次两两相邻比较后得次

14、大的数；（3）依次类推，n个数共进行n-1趟比较，在第j趟中要进行n-j次两两比较。 冒泡排序（升序)VB程序： for i=1 to n-1 n-1趟遍历 for j=1 to n-i 1次遍历 if a(j)a(j+1) then temp=a(j+1) a(j+1)=a(j) a(j)=temp end if next j next i3） 合并法排序（将两个有序数合并法排序（将两个有序数组组A、B合并成另一个有序的数组合并成另一个有序的数组C，升序），升序）基本思想：基本思想：（1）先在A、B数组中各取第一个元素进行比较，将小的元素放入C数组；（2）取小的元素所在数组的下一个元素与另一

15、数组中上次比较后较大的元素比较，重复上述比较过程，直到某个数组被先排完；（3）将另一个数组剩余元素抄入C数组，合并排序完成。 两个有序数组A、B合并成一个有序数组C，VB实现的程序： Do While ia = UBound(A) And ib = UBound(B) 当A和B数组均未比较完 If A(ia) B(ib) Then C(ic) = A(ia)： ia = ia + 1 Else C(ic) = B(ib)： ib = ib + 1 End If ic = ic + 1 Loop Do While ia = UBound(A) A数组中的剩余元素抄入C数组 C(ic) = A(ia) ia = ia + 1 ic = ic + 1 Loop Do While ib 0 Then gn = 2 ElseIf r1 - r2 0 Then gn = 1 End If End Function