[工學]第1章基本術(shù)語算法描述、c語言復(fù)習(編輯修改稿)
2024-11-12 18:43 本頁面
【文章內(nèi)容簡介】 面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。 解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。 數(shù)值算法和非數(shù)值算法并沒有嚴格的區(qū)別。 一般說來，在數(shù)值算法中主要進行算術(shù)運算，而在非數(shù)值算法中主要進行比較和邏輯運算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。 算法和算法的描述 算法 算法（ Algorithm）是對特定問題求解步驟的一種描述，它是指令的有限序列。是解決特定問題的一種方法和描述。算法是執(zhí)行特定計算的有窮過程。這個過程有 5個特點： ：當執(zhí)行一個算法時，不論是何種情況，在經(jīng)過了有限步驟后，這個算法一定要終止。 ：算法中的每條指令都必須是清楚的，指令無二義性。 ：具有 0個或 0個以上由外界提供的量。 ：產(chǎn)生 1個或多個結(jié)果。 ：每條指令都充分基本，原則上可由人僅用筆和紙在有限的時間內(nèi)也能完成。 注意： 算法和程序是有區(qū)別的，即程序未必能滿足動態(tài)有窮 。 在本書中，我們只討論滿足動態(tài)有窮的程序，因此 “ 算法 ” 和“ 程序 ” 是通用的。 設(shè)計算法的基本過程 ◎ 通過對問題進行詳細地分析，抽象出相應(yīng)的數(shù)學模型； ◎ 確定使用的數(shù)據(jù)結(jié)構(gòu)，并在此基礎(chǔ)上設(shè)計對此數(shù)據(jù)結(jié)構(gòu)實施各種操作的算法； ◎ 選用某種語言將算法轉(zhuǎn)換成程序； ◎ 調(diào)試并運行這些程序。 舉 例 問題：按從小到大的順序重新排列 x， y， z三個數(shù)值的內(nèi)容。 算法： （ 1）輸入 x， y， z三個數(shù)值； （ 2）從三個數(shù)值中挑選出最小者并換到 x中； （ 3）從 y， z中挑選出較小者并換到 y中； （ 4）輸出排序后的結(jié)果。 算法的描述 一個算法可以用自然語言 、 數(shù)字語言或約定的符號來描述 ， 也可以用計算機高級程序語言來描述 ， 如 Pascal語言 、 C語言或偽代碼等 。 本書選用 C語言作為描述算法的工具 。 算法有以下描述方法 框圖描述：直觀易懂，但描述復(fù)雜的算法就不夠方便。 非形式算法描述：用中文語言及程序設(shè)計語言的語句。 類 C語言算法描述：通過對 C語言進行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴展修改，從而，增強了語言的描述功能。不能運行，容易編寫、閱讀和統(tǒng)一格式。 C語言編寫的程序或函數(shù)：能運行，也稱為程序。 小 結(jié) 主要介紹了如下一些基本概念： 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計算機中的存儲表示 （ 即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu) ） ， 并對這種結(jié)構(gòu)定義相適應(yīng)的運算 ， 設(shè)計出相應(yīng)的算法 ， 而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型 。 數(shù)據(jù)：數(shù)據(jù)是人們利用文字符號 、 數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述 。 在計算機科學中 ， 數(shù)據(jù)的含義非常廣泛 ， 我們把一切能夠輸入到計算機中并被計算機程序處理的信息 ， 包括文字 、表格 、 圖象等 ， 都稱為數(shù)據(jù) 。 結(jié)點： 結(jié)點也叫數(shù)據(jù)元素 ， 它是組成數(shù)據(jù)的基本單位 。 邏輯結(jié)構(gòu)： 結(jié)點和結(jié)點之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu) 。 存儲結(jié)構(gòu)： 數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu) 。 數(shù)據(jù)處理： 數(shù)據(jù)處理是指對數(shù)據(jù)進行查找 、 插入 、 刪除 、 合并 、 排序 、 統(tǒng)計以及簡單計算等的操作過程 。 數(shù)據(jù)類型： 數(shù)據(jù)類型是指程序設(shè)計語言中各變量可取的數(shù)據(jù)種類 。 數(shù)據(jù)類型是高級程序設(shè)計語言中的一個基本概念 ， 它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān) 。 復(fù)習 數(shù)據(jù)結(jié)構(gòu)的基本概念 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)、結(jié)點、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)類型 算法的特性和描述方法 動態(tài)有窮、確定性、輸入、輸出、可行性 框圖描述、非形式算法描述、類 C語言算法描述、 C語言編寫的程序或函數(shù) 算法評價 設(shè)計一個好的算法應(yīng)考慮以下幾個方面： 正確性、運行時間、占用的存儲空間、簡單性。 新授 1．正確性 “ 正確 ” 的含義在通常的用法中有很大的差別，大體可分為以下四個層次： ① 程序不含語法錯誤； ② 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果； ③ 程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果； ④ 程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。 2． 運行時間 運行時間是指一個算法在計算機上運算所花費的時間 。 它大致等于計算機執(zhí)行一種簡單操作 （ 如賦值操作 、 計算操作 、 比較操作等等 ） 所需要的時間與算法中進行簡單操作次數(shù)的乘積 。 通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復(fù)雜性 ， 它是一個算法運行時間的相對量度 。 搞清“算法運行時間”和“程序運行時間”的區(qū)別 算法時間度量分析 算法時間復(fù)雜度分析：對解決問題的算法作時間上的度量分析，或?qū)鉀Q同一問題不同算法運行時間的比較。 決定因素： 規(guī)模大?。狠斎肓康臄?shù)目多少 基本操作的次數(shù)：在某個數(shù)據(jù)類型上的標準操作（如比較大小，計算等） 應(yīng)用舉例 查找 N元數(shù)組中最大元素的算法。 P8 Int large(int * a ,int n)
教學課件相關(guān)推薦
鄂ICP備17016276號-1