第二章 測(cè)量程序基本算法.ppt

第二章測(cè)量程序基本算法 本章重點(diǎn)算法的概念及特性 數(shù)據(jù)文件的建立 讀寫(xiě) 矩陣運(yùn)算 排序算法 坐標(biāo)方位角的計(jì)算 2 1算法 Algorithm 及其表示 2 1 1概念廣義地講 算法是為完成一項(xiàng)任務(wù)所應(yīng)尊循的一步一步的 規(guī)則的 精確的 無(wú)歧異的描述 它的總步數(shù)是有限的 狹義地講 算法是解決一個(gè)問(wèn)題采取的方法和步驟的描述 例1 找出三個(gè)數(shù)中的最大的數(shù) 假如三個(gè)數(shù)已存放在數(shù)組a 2 中了 用Max存儲(chǔ)最大的數(shù) 算法設(shè)計(jì)如下 1 比較a 0 與a 1 將大的數(shù)放到Max中 2 比較Max與a 2 若Max小于a 2 將a 2 賦值給Max 例2 輸入10個(gè)數(shù) 輸出其中最大的數(shù) 算法設(shè)計(jì)如下 1 輸入一個(gè)數(shù) 存入變量A中 將記錄數(shù)據(jù)個(gè)數(shù)的變量N賦值為1 即N 1 2 將A存入表示最大值的變量Max中 即Max A 3 再輸入一個(gè)值給A 如果A Max則Max A 否則Max不變 4 讓記錄數(shù)據(jù)個(gè)數(shù)的變量增加1 即N N 1 5 判斷N是否小于等于10 若成立則轉(zhuǎn)到第 3 步執(zhí)行 否則轉(zhuǎn)到第 6 步 6 輸出max 2 1 2算法的特性 有窮性對(duì)于任意一組合法輸入值 在執(zhí)行有窮步驟之后一定能結(jié)束 即 算法中的每一步驟都能在有限時(shí)間內(nèi)完成 確定性對(duì)于每種情況下所應(yīng)執(zhí)行的操作 在算法中都有確切的規(guī)定 使算法的執(zhí)行者或閱讀者都能明白其含義以及如何執(zhí)行 可行性算法中的所有操作都必須足夠基本 都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)它 有輸入作為算法加工對(duì)象的量值 通常體現(xiàn)為算法中的一組變量 有些輸入量需要在算法執(zhí)行過(guò)程中輸入 而有的算法表面上可以沒(méi)有輸入 實(shí)際上已經(jīng)被嵌入算法中 有輸出它是一組與 輸入 有確定關(guān)系的量值 是算法進(jìn)行信息加工后得到的結(jié)果 這種確定關(guān)系即為算法的功能 2 1 3算法設(shè)計(jì)的原則 設(shè)計(jì)算法時(shí) 通常應(yīng)考慮達(dá)到以下目標(biāo) 1 正確性對(duì)算法是否 正確 的理解可以有以下四個(gè)層次 a 程序中不含語(yǔ)法錯(cuò)誤 b 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得到出滿足要求的結(jié)果 c 程序?qū)τ诰倪x擇的 典型 苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果 d 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果 2 可讀性算法主要是為了人的閱讀與交流 其次才是為計(jì)算機(jī)執(zhí)行 因此算法應(yīng)該易于人的理解 另一方面 晦澀難度的程序易于隱藏較多錯(cuò)誤而難以調(diào)試 3 健壯性當(dāng)輸入的數(shù)據(jù)非法時(shí) 算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理 而不是產(chǎn)生莫名其妙的輸出結(jié)果 并且 處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行 而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值 以便在更高的抽象層次上進(jìn)行處理 4 高效率與低存儲(chǔ)量需求通常 算法的效率指的是算法執(zhí)行時(shí)間 存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ)空間 兩者都與問(wèn)題的規(guī)模有關(guān) 2 1 4算法的表示 1 用自然語(yǔ)言及偽代碼來(lái)表示自然語(yǔ)言 是指人們?nèi)粘Ｊ褂玫恼Z(yǔ)言 可以是漢語(yǔ) 英語(yǔ)或其它語(yǔ)言 偽代碼 是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào) 包括數(shù)學(xué)符號(hào) 來(lái)描述算法 例1用偽代碼表示Begin算法開(kāi)始Ifa 0 a 1 則a 0 Max否則a 1 MaxIfa 2 Max則a 2 MaxEnd算法結(jié)束 2 用傳統(tǒng)流程圖來(lái)表示1 傳統(tǒng)流程中的基本符號(hào) 起止框 I O框 流程線 處理框 判斷框 2 三種基本結(jié)構(gòu)的表示 順序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 當(dāng)循環(huán) 直道循環(huán) 三種基本結(jié)構(gòu)的特點(diǎn) 只有一個(gè)入口只有一個(gè)出口不存在死語(yǔ)句不存在死循環(huán) 從10個(gè)數(shù)中選出最大的數(shù)的算法流程圖 N 10 Max AN 1 A Max Max A 輸入A 再輸入給A N N 1 結(jié)束 Y N N Y 開(kāi)始 打印Max 3 用N S流程圖表示 將全部算法寫(xiě)在一個(gè)矩形框內(nèi) 在矩形內(nèi)還可包含其它從屬于它的框 三種基本結(jié)構(gòu)的N S圖表示 循序結(jié)構(gòu) 選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu) 當(dāng)循環(huán) 直道循環(huán) 例4畫(huà)出從10個(gè)數(shù)中選出最大的數(shù)的N S流程圖 傳統(tǒng)流程圖 N 10 Max AN 1 A Max Max A 輸入A 開(kāi)始 再輸入給A N N 1 輸出Max 結(jié)束 Y N N Y 輸入A 當(dāng)N 10 Max A N N 1 打印Max Max A N 1 N S流程圖 A Max Y N 輸入A 2 2測(cè)量程序中幾種常用算法 2 2 1數(shù)據(jù)文件操作 讀寫(xiě)文件 數(shù)據(jù)在計(jì)算機(jī)里的存儲(chǔ)格式五花八門(mén) 如Image 它可以以Bmp Jpeg Tif等格式來(lái)存儲(chǔ) 又如對(duì)于GPS數(shù)據(jù)文件 不同的儀器型號(hào) 它的數(shù)據(jù)記錄格式一般是不一樣的 測(cè)量程序處理的對(duì)象主要為野外采集原始數(shù)據(jù) 外業(yè)觀測(cè)數(shù)據(jù) 已知數(shù)據(jù)以及網(wǎng)形數(shù)據(jù) 計(jì)算的開(kāi)始 結(jié)束以及計(jì)算過(guò)程中 會(huì)涉及數(shù)據(jù)的讀取 存儲(chǔ) 中間計(jì)算結(jié)果 以及輸出 成果 那么我們進(jìn)行程序設(shè)計(jì)時(shí)以哪種形式的文件來(lái)存儲(chǔ)數(shù)據(jù)呢 數(shù)據(jù)在存儲(chǔ)到文件中又怎樣來(lái)組織呢 在VB6 0中讀取該格式的文本數(shù)據(jù)要到 CommonDialog外部控件 For循環(huán) While loop以及l(fā)ineInput語(yǔ)句 文本操作算法流程 N Y Y N 2 2 2矩陣運(yùn)算 對(duì)矩陣運(yùn)算進(jìn)行編程實(shí)現(xiàn)時(shí) 一般需在內(nèi)存中申請(qǐng)一塊連續(xù)的空間來(lái)存儲(chǔ)矩陣中各個(gè)元素 在C 語(yǔ)言中 可以定義一個(gè)指針來(lái)指向內(nèi)存中所申請(qǐng)的地址 在VB中 可利用數(shù)組 可以用一維數(shù)組 也可以用二維數(shù)組 存儲(chǔ)矩陣中的各個(gè)元素 1 兩矩陣相加 矩陣A B相加就是矩陣對(duì)應(yīng)的元素相加即可實(shí)現(xiàn) fori 0tom 1forj 0ton 1c i j a i j b i j nextnext N 矩陣相加流程 2 兩矩陣相減 矩陣A B相加就是矩陣對(duì)應(yīng)的元素相加即可實(shí)現(xiàn) fori 0tom 1forj 0ton 1c i j a i j b i j nextnext N 矩陣相減流程 3 矩陣轉(zhuǎn)置 通過(guò)將a i j 元素放到b j1 i1 即可實(shí)現(xiàn)矩陣轉(zhuǎn)置 在VB實(shí)現(xiàn)時(shí)先定義一個(gè)存儲(chǔ)a i j 轉(zhuǎn)置后的矩陣b j i fori 0tom 1forj 0ton 1b i j a j i nextnext 4 矩陣相乘 矩陣A有m l個(gè)元素 矩陣B有l(wèi) n個(gè)元素 則矩陣C A B有m n個(gè)元素 矩陣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 定義四個(gè)變量b c d M分別存儲(chǔ)度 分 秒以及最終結(jié)果 2 2 3不同單位角度的轉(zhuǎn)化 度分秒轉(zhuǎn)度 M a c 60 d 3600 度分秒轉(zhuǎn)弧度 定義四個(gè)變量b c d M分別用來(lái)存儲(chǔ)度 分 秒及最終結(jié)果 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中字符串操作函數(shù) Left Mid Split Right 類(lèi)型轉(zhuǎn)換函數(shù) 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 對(duì)有n個(gè)數(shù)的序列 存放在數(shù)組a n 中 從中選出最小的數(shù) 與第1個(gè)數(shù)交換位置 排序開(kāi)始前a n 第1遍交換后 2 第二遍時(shí) 除第1個(gè)數(shù)外 其余n 1個(gè)數(shù)中選最小的數(shù) 與第2個(gè)數(shù)交換位置 第2遍交換后 3 依次類(lèi)推 選擇了n 1遍后 這個(gè)數(shù)列已按升序排列 選擇法排序算法的流程圖 選擇法排序 升序 的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 冒泡排序 升序 基本思想 將相鄰兩個(gè)數(shù)比較 小的調(diào)到前頭 1 有n個(gè)數(shù) 存放在數(shù)組a n 中 第一趟將每相鄰兩個(gè)數(shù)比較 小的放到前頭 經(jīng)n 1次兩兩相鄰比較后 最大的數(shù)已 沉底 放在最后一個(gè)位置 小的數(shù)上升 浮起 2 第二趟對(duì)余下的n 1個(gè)數(shù) 最大的數(shù)已 沉底 按上法比較 經(jīng)n 2次兩兩相鄰比較后得次大的數(shù) 3 依次類(lèi)推 n個(gè)數(shù)共進(jìn)行n 1趟比較 在第j趟中要進(jìn)行n j次兩兩比較 冒泡排序 升序 VB程序 fori 1ton 1 n 1趟遍歷forj 1ton i 每1次遍歷過(guò)程ifa j a j 1 thentemp a j 1 a j 1 a j a j tempendifnextjnexti 3 合并法排序 將兩個(gè)有序數(shù)組A B合并成另一個(gè)有序的數(shù)組C 升序 基本思想 1 先在A B數(shù)組中各取第一個(gè)元素進(jìn)行比較 將小的元素放入C數(shù)組 2 取小的元素所在數(shù)組的下一個(gè)元素與另一數(shù)組中上次比較后較大的元素比較 重復(fù)上述比較過(guò)程 直到某個(gè)數(shù)組被先排完 3 將另一個(gè)數(shù)組剩余元素抄入C數(shù)組 合并排序完成 兩個(gè)有序數(shù)組A B合并成一個(gè)有序數(shù)組C VB實(shí)現(xiàn)的程序 DoWhileia UBound A Andib UBound B 當(dāng)A和B數(shù)組均未比較完IfA ia B ib ThenC ic A ia ia ia 1ElseC ic B ib ib ib 1EndIfic ic 1Loop DoWhileia UBound A A數(shù)組中的剩余元素抄入C數(shù)組C ic A ia ia ia 1ic ic 1LoopDoWhileib UBound B B數(shù)組中的剩余元素抄入C數(shù)組C ic B ib ib ib 1 ic ic 1Loop 2 2 5坐標(biāo)方位角計(jì)算 坐標(biāo)方位角MN 是指坐標(biāo)北到某一向量的角度 范圍為0 360o 假若存在兩點(diǎn)M xm ym 與N xn yn 求取方位角 1 2 3 4 其中 從 2 3 4 式計(jì)算求得的方位角都有一定的局限性 就是計(jì)算的結(jié)果不一定是真正的坐標(biāo)方位角 都要進(jìn)行象限判斷后加上一定的數(shù)值后 才能變成真正的坐標(biāo)方位角 改進(jìn)后的計(jì)算公式 式中 sgn 為取符號(hào)函數(shù) 即 通過(guò)以上分析 應(yīng)用式 5 計(jì)算時(shí) 除第1象限結(jié)果大于360度外 其它象限 計(jì)算出的方位角都是真方位角 即使在大于360時(shí) 360也為第一象限真方位角 5 a Atan YN YM XN XM 180 2 1 sgn xn xm 2 注意 當(dāng)xn xm不相等時(shí) 可采此算法 當(dāng)xn與xm相等時(shí) 在編程時(shí)需單獨(dú)考慮 若方位角采用改進(jìn)后的式 5 來(lái)計(jì)算 VB程序?yàn)?FunctionQfangweijiao xnAsDouble ynAsDouble xmAsDouble ymAsDouble AsDoubleDimcAsDoublec gn xn xm Qfangweijiao Atn yn ym xn xm 180 cEndFunctionFunctiongn r1AsDouble r2AsDouble Ifr1 r2 0Thengn 2ElseIfr1 r2 0The