第二章测量程序基本算法

第二章测量程序基本算法 本章重点算法的概念及特性 数据文件的建立 读写 矩阵运算 排序算法 坐标方位角的计算 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 赋值给Max 例2 输入10个数 输出其中最大的数 算法设计如下 1 输入一个数 存入变量A中 将记录数据个数的变量N赋值为1 即N 1 2 将A存入表示最大值的变量Max中 即Max A 3 再输入一个值给A 如果A Max则Max A 否则Max不变 4 让记录数据个数的变量增加1 即N N 1 5 判断N是否小于等于10 若成立则转到第 3 步执行 否则转到第 6 步 6 输出max 2 1 2算法的特性 有穷性对于任意一组合法输入值 在执行有穷步骤之后一定能结束 即 算法中的每一步骤都能在有限时间内完成 确定性对于每种情况下所应执行的操作 在算法中都有确切的规定 使算法的执行者或阅读者都能明白其含义以及如何执行 可行性算法中的所有操作都必须足够基本 都可以通过已经实现的基本操作运算有限次实现它 有输入作为算法加工对象的量值 通常体现为算法中的一组变量 有些输入量需要在算法执行过程中输入 而有的算法表面上可以没有输入 实际上已经被嵌入算法中 有输出它是一组与 输入 有确定关系的量值 是算法进行信息加工后得到的结果 这种确定关系即为算法的功能 2 1 3算法设计的原则 设计算法时 通常应考虑达到以下目标 1 正确性对算法是否 正确 的理解可以有以下四个层次 a 程序中不含语法错误 b 程序对于几组输入数据能够得到出满足要求的结果 c 程序对于精心选择的 典型 苛刻且带有刁难性的几组输入数据能够得出满足要求的结果 d 程序对于一切合法的输入数据都能得出满足要求的结果 2 可读性算法主要是为了人的阅读与交流 其次才是为计算机执行 因此算法应该易于人的理解 另一方面 晦涩难度的程序易于隐藏较多错误而难以调试 3 健壮性当输入的数据非法时 算法应当恰当地作出反应或进行相应处理 而不是产生莫名其妙的输出结果 并且 处理出错的方法不应是中断程序的执行 而应是返回一个表示错误或错误性质的值 以便在更高的抽象层次上进行处理 4 高效率与低存储量需求通常 算法的效率指的是算法执行时间 存储量指的是算法执行过程中所需的最大存储空间 两者都与问题的规模有关 2 1 4算法的表示 1 用自然语言及伪代码来表示自然语言 是指人们日常使用的语言 可以是汉语 英语或其它语言 伪代码 是用介于自然语言和计算机语言之间的文字和符号 包括数学符号 来描述算法 例1用伪代码表示Begin算法开始Ifa 0 a 1 则a 0 Max否则a 1 MaxIfa 2 Max则a 2 MaxEnd算法结束 2 用传统流程图来表示1 传统流程中的基本符号 起止框 I O框 流程线 处理框 判断框 2 三种基本结构的表示 顺序结构 选择结构 循环结构 当循环 直道循环 三种基本结构的特点 只有一个入口只有一个出口不存在死语句不存在死循环 从10个数中选出最大的数的算法流程图 N 10 Max AN 1 A Max Max A 输入A 再输入给A N N 1 结束 Y N N Y 开始 打印Max 3 用N S流程图表示 将全部算法写在一个矩形框内 在矩形内还可包含其它从属于它的框 三种基本结构的N S图表示 循序结构 选择结构 循环结构 当循环 直道循环 例4画出从10个数中选出最大的数的N S流程图 传统流程图 N 10 Max AN 1 A Max Max A 输入A 开始 再输入给A N N 1 输出Max 结束 Y N N Y 输入A 当N 10 Max A N N 1 打印Max Max A N 1 N S流程图 A Max Y N 输入A 2 2测量程序中几种常用算法 2 2 1数据文件操作 读写文件 数据在计算机里的存储格式五花八门 如Image 它可以以Bmp Jpeg Tif等格式来存储 又如对于GPS数据文件 不同的仪器型号 它的数据记录格式一般是不一样的 测量程序处理的对象主要为野外采集原始数据 外业观测数据 已知数据以及网形数据 计算的开始 结束以及计算过程中 会涉及数据的读取 存储 中间计算结果 以及输出 成果 那么我们进行程序设计时以哪种形式的文件来存储数据呢 数据在存储到文件中又怎样来组织呢 在VB6 0中读取该格式的文本数据要到 CommonDialog外部控件 For循环 While loop以及lineInput语句 文本操作算法流程 N Y Y N 2 2 2矩阵运算 对矩阵运算进行编程实现时 一般需在内存中申请一块连续的空间来存储矩阵中各个元素 在C 语言中 可以定义一个指针来指向内存中所申请的地址 在VB中 可利用数组 可以用一维数组 也可以用二维数组 存储矩阵中的各个元素 1 两矩阵相加 矩阵A B相加就是矩阵对应的元素相加即可实现 fori 0tom 1forj 0ton 1c i j a i j b i j nextnext N 矩阵相加流程 2 两矩阵相减 矩阵A B相加就是矩阵对应的元素相加即可实现 fori 0tom 1forj 0ton 1c i j a i j b i j nextnext N 矩阵相减流程 3 矩阵转置 通过将a i j 元素放到b j1 i1 即可实现矩阵转置 在VB实现时先定义一个存储a i j 转置后的矩阵b j i fori 0tom 1forj 0ton 1b i j a j i nextnext 4 矩阵相乘 矩阵A有m l个元素 矩阵B有l n个元素 则矩阵C A B有m n个元素 矩阵C中任一元素 i 1 2 m j 1 2 n 两矩阵相乘流程 fori 1tomforj 1tonc i j 0fork 1tolc i k c i j a i k b k j nextk nextj Nexti 定义四个变量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 180 DimAnyString MyStrAnyString HelloWorld Definestring MyStr Left AnyString 1 Returns H MyStr Left AnyString 7 Returns HelloW MyStr Left AnyString 20 Returns HelloWorld DimAnyString MyStrAnyString HelloWorld Definestring MyStr Right AnyString 1 Returns d MyStr Right AnyString 6 Returns World MyStr Right AnyString 20 Returns HelloWorld VB中字符串操作函数 Left Mid Split Right 类型转换函数 CDbl expression CInt expression CLng expression CStr expression Str number Mid string start length DimMyString FirstWord LastWord MidWordsMyString MidFunctionDemo Createtextstring FirstWord Mid MyString 1 3 Returns Mid LastWord Mid MyString 14 4 Returns Demo MidWords Mid MyString 5 Returns FunctionDemo 2 2 4排序算法 1 选择法排序 升序 基本思想 1 对有n个数的序列 存放在数组a n 中 从中选出最小的数 与第1个数交换位置 排序开始前a n 第1遍交换后 2 第二遍时 除第1个数外 其余n 1个数中选最小的数 与第2个数交换位置 第2遍交换后 3 依次类推 选择了n 1遍后 这个数列已按升序排列 选择法排序算法的流程图 选择法排序 升序 的VB程序 fori1 1ton 1 n 1趟遍历P i1fori2 i1 1ton 1次遍历ifa P a i2 thenP i2endifnexti2temp a i1 a i1 a P a P tempnexti1 思考 选择排序降序算法怎样 2 冒泡排序 升序 基本思想 将相邻两个数比较 小的调到前头 1 有n个数 存放在数组a n 中 第一趟将每相邻两个数比较 小的放到前头 经n 1次两两相邻比较后 最大的数已 沉底 放在最后一个位置 小的数上升 浮起 2 第二趟对余下的n 1个数 最大的数已 沉底 按上法比较 经n 2次两两相邻比较后得次大的数 3 依次类推 n个数共进行n 1趟比较 在第j趟中要进行n j次两两比较 冒泡排序 升序 VB程序 fori 1ton 1 n 1趟遍历forj 1ton i 每1次遍历过程ifa j a j 1 thentemp a j 1 a j 1 a j a j tempendifnextjnexti 3 合并法排序 将两个有序数组A B合并成另一个有序的数组C 升序 基本思想 1 先在A B数组中各取第一个元素进行比较 将小的元素放入C数组 2 取小的元素所在数组的下一个元素与另一数组中上次比较后较大的元素比较 重复上述比较过程 直到某个数组被先排完 3 将另一个数组剩余元素抄入C数组 合并排序完成 两个有序数组A B合并成一个有序数组C VB实现的程序 DoWhileia UBound A Andib UBound B 当A和B数组均未比较完IfA ia B ib ThenC ic A ia ia ia 1ElseC ic B ib ib ib 1EndIfic ic 1Loop DoWhileia UBound A A数组中的剩余元素抄入C数组C ic A ia ia ia 1ic ic 1LoopDoWhileib UBound B B数组中的剩余元素抄入C数组C ic B ib ib ib 1 ic ic 1Loop 2 2 5坐标方位角计算 坐标方位角MN 是指坐标北到某一向量的角度 范围为0 360o 假若存在两点M xm ym 与N xn yn 求取方位角 1 2 3 4 其中 从 2 3 4 式计算求得的方位角都有一定的局限性 就是计算的结果不一定是真正的坐标方位角 都要进行象限判断后加上一定的数值后 才能变成真正的坐标方位角 改进后的计算公式 式中 sgn 为取符号函数 即 通过以上分析 应用式 5 计算时 除第1象限结果大于360度外 其它象限 计算出的方位角都是真方位角 即使在大于360时 360也为第一象限真方位角 5 a Atan YN YM XN XM 180 2 1 sgn xn xm 2 注意 当xn xm不相等时 可采此算法 当xn与xm相等时 在编程时需单独考虑 若方位角采用改进后的式 5 来计算 VB程序为 FunctionQfangweijiao xnAsDouble ynAsDouble xmAsDouble ymAsDouble AsDoubleDimcAsDoublec gn xn xm Qfangweijiao Atn yn ym xn xm 180 cEndFunctionFunctiongn r1AsDouble r2AsDouble Ifr1 r2 0Thengn 2ElseIfr1 r2 0Th