(2024年)算法與程序設(shè)計(jì)課件

算法與程序設(shè)計(jì)課件12024/3/26CATALOGUE目錄課程介紹與教學(xué)目標(biāo)算法基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)程序設(shè)計(jì)方法學(xué)基本控制結(jié)構(gòu)與應(yīng)用舉例函數(shù)、數(shù)組和指針在程序設(shè)計(jì)中的應(yīng)用文件操作與數(shù)據(jù)處理技術(shù)綜合案例分析與實(shí)戰(zhàn)演練22024/3/2601課程介紹與教學(xué)目標(biāo)32024/3/26計(jì)算機(jī)科學(xué)與技術(shù)發(fā)展的重要組成部分算法與程序設(shè)計(jì)是計(jì)算機(jī)科學(xué)的核心內(nèi)容，對(duì)于培養(yǎng)計(jì)算思維、提高問(wèn)題解決能力具有重要意義。適應(yīng)信息化時(shí)代的需求當(dāng)前社會(huì)正處于信息化時(shí)代，掌握算法與程序設(shè)計(jì)技能對(duì)于應(yīng)對(duì)未來(lái)挑戰(zhàn)具有重要意義。推動(dòng)相關(guān)領(lǐng)域的發(fā)展算法與程序設(shè)計(jì)不僅應(yīng)用于計(jì)算機(jī)科學(xué)領(lǐng)域，還廣泛涉及數(shù)學(xué)、物理、化學(xué)、生物等多個(gè)學(xué)科領(lǐng)域，對(duì)于推動(dòng)這些領(lǐng)域的發(fā)展具有重要作用。課程背景與意義42024/3/26掌握算法與程序設(shè)計(jì)的基本概念、原理和方法，了解常用算法和數(shù)據(jù)結(jié)構(gòu)。知識(shí)目標(biāo)能夠運(yùn)用所學(xué)知識(shí)分析和解決實(shí)際問(wèn)題，具備設(shè)計(jì)和實(shí)現(xiàn)算法的能力。能力目標(biāo)培養(yǎng)學(xué)生的計(jì)算思維、創(chuàng)新精神和團(tuán)隊(duì)協(xié)作能力。素質(zhì)目標(biāo)教學(xué)目標(biāo)與要求52024/3/26教材結(jié)構(gòu)本課程教材共分為導(dǎo)論、基礎(chǔ)知識(shí)、算法設(shè)計(jì)策略、數(shù)據(jù)結(jié)構(gòu)、算法分析與優(yōu)化、程序設(shè)計(jì)與實(shí)現(xiàn)等六個(gè)部分。內(nèi)容概述導(dǎo)論部分介紹算法與程序設(shè)計(jì)的概念、歷史和發(fā)展趨勢(shì)；基礎(chǔ)知識(shí)部分包括數(shù)學(xué)基礎(chǔ)、編程基礎(chǔ)等；算法設(shè)計(jì)策略部分講解分治策略、動(dòng)態(tài)規(guī)劃、貪心算法等常用算法設(shè)計(jì)策略；數(shù)據(jù)結(jié)構(gòu)部分介紹線性表、樹、圖等常用數(shù)據(jù)結(jié)構(gòu)；算法分析與優(yōu)化部分講解時(shí)間復(fù)雜度分析、空間復(fù)雜度分析以及算法優(yōu)化方法；程序設(shè)計(jì)與實(shí)現(xiàn)部分則以實(shí)際案例為例，講解程序設(shè)計(jì)的流程、方法和技巧。教材結(jié)構(gòu)與內(nèi)容概述62024/3/2602算法基礎(chǔ)72024/3/26算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算步驟。算法定義確定性、有窮性、可行性、輸入項(xiàng)、輸出項(xiàng)。算法特性算法概念及特性82024/3/26使用自然語(yǔ)言描述算法步驟，易于理解但不夠精確。自然語(yǔ)言描述流程圖描述偽代碼描述使用圖形符號(hào)表示算法步驟，直觀形象但不易于計(jì)算機(jī)執(zhí)行。使用類似于編程語(yǔ)言的語(yǔ)法描述算法，精確且易于理解。030201算法表示方法92024/3/26123評(píng)估算法執(zhí)行時(shí)間隨問(wèn)題規(guī)模增長(zhǎng)的變化情況，常用大O表示法。時(shí)間復(fù)雜度評(píng)估算法執(zhí)行過(guò)程中所需額外空間的數(shù)量級(jí)，也常用大O表示法表示?？臻g復(fù)雜度對(duì)算法在不同情況下的性能進(jìn)行評(píng)估和比較。最好、最壞和平均情況分析算法復(fù)雜度分析102024/3/2603數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)112024/3/26線性表是一種具有n個(gè)元素的有限序列，具有順序性、元素唯一性、元素可重復(fù)性等性質(zhì)。線性表的定義和性質(zhì)包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種，其中順序存儲(chǔ)結(jié)構(gòu)使用一維數(shù)組表示線性表，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)使用指針表示元素之間的邏輯關(guān)系。線性表的存儲(chǔ)結(jié)構(gòu)包括初始化、插入、刪除、查找等基本操作，以及這些操作的時(shí)間復(fù)雜度和空間復(fù)雜度分析。線性表的基本操作線性表及其操作實(shí)現(xiàn)122024/3/26棧的基本概念及操作01棧是一種后進(jìn)先出（LIFO）的線性表，只允許在一端（稱為棧頂）進(jìn)行插入和刪除操作?；静僮靼ǔ跏蓟?、入棧、出棧、取棧頂元素等。隊(duì)列的基本概念及操作02隊(duì)列是一種先進(jìn)先出（FIFO）的線性表，只允許在一端（稱為隊(duì)尾）進(jìn)行插入操作，在另一端（稱為隊(duì)頭）進(jìn)行刪除操作?；静僮靼ǔ跏蓟⑷腙?duì)、出隊(duì)、取隊(duì)頭元素等。棧和隊(duì)列的應(yīng)用03棧和隊(duì)列在計(jì)算機(jī)科學(xué)中具有廣泛的應(yīng)用，如函數(shù)調(diào)用棧、表達(dá)式求值、緩沖區(qū)處理等。棧和隊(duì)列及其應(yīng)用132024/3/26樹是一種具有層次結(jié)構(gòu)的非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)和邊組成，具有唯一的根節(jié)點(diǎn)和若干個(gè)子節(jié)點(diǎn)。樹的基本術(shù)語(yǔ)包括節(jié)點(diǎn)、邊、路徑、度、葉子節(jié)點(diǎn)等。樹的基本概念二叉樹是一種特殊的樹，每個(gè)節(jié)點(diǎn)最多只有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。二叉樹的基本性質(zhì)包括二叉樹的形態(tài)、完全二叉樹、滿二叉樹等。二叉樹的基本概念包括初始化、插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)、遍歷等操作。其中遍歷操作是樹和二叉樹的核心操作之一，包括前序遍歷、中序遍歷、后序遍歷和層次遍歷等。樹和二叉樹的基本操作樹和二叉樹基本概念及操作142024/3/2604程序設(shè)計(jì)方法學(xué)152024/3/26從高層次開始設(shè)計(jì)，逐步細(xì)化到具體的實(shí)現(xiàn)細(xì)節(jié)。自頂向下設(shè)計(jì)將程序劃分為若干個(gè)獨(dú)立的、可重用的模塊，每個(gè)模塊具有特定的功能。模塊化設(shè)計(jì)使用順序、選擇和循環(huán)三種基本控制結(jié)構(gòu)來(lái)構(gòu)建程序。結(jié)構(gòu)化控制結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)方法162024/3/2603繼承與多態(tài)通過(guò)繼承實(shí)現(xiàn)代碼重用和擴(kuò)展，通過(guò)多態(tài)實(shí)現(xiàn)同一接口的不同實(shí)現(xiàn)方式。01對(duì)象與類對(duì)象是現(xiàn)實(shí)世界事物的抽象，類是具有相同屬性和方法的對(duì)象的集合。02封裝與隱藏將數(shù)據(jù)和操作封裝在對(duì)象內(nèi)部，隱藏內(nèi)部實(shí)現(xiàn)細(xì)節(jié)，只對(duì)外提供必要的接口。面向?qū)ο蟪绦蛟O(shè)計(jì)方法172024/3/26簡(jiǎn)潔明了代碼應(yīng)簡(jiǎn)潔、清晰、易于理解，避免冗余和復(fù)雜的邏輯結(jié)構(gòu)。命名規(guī)范變量、函數(shù)、類等命名應(yīng)符合規(guī)范，易于理解和記憶。注釋規(guī)范在關(guān)鍵部分添加注釋，解釋代碼的功能和實(shí)現(xiàn)原理，方便他人閱讀和理解。代碼格式化統(tǒng)一代碼格式和縮進(jìn)風(fēng)格，提高代碼的可讀性和美觀度。程序設(shè)計(jì)風(fēng)格與規(guī)范182024/3/2605基本控制結(jié)構(gòu)與應(yīng)用舉例192024/3/26示例1計(jì)算兩個(gè)數(shù)的和并輸出結(jié)果示例2輸入一個(gè)數(shù)，求其絕對(duì)值并輸出結(jié)果示例3輸入兩個(gè)數(shù)，交換它們的值并輸出結(jié)果順序結(jié)構(gòu)程序設(shè)計(jì)舉例202024/3/26示例2判斷一個(gè)數(shù)是否為素?cái)?shù)示例3根據(jù)輸入的年份和月份，判斷該月有多少天示例1根據(jù)輸入的成績(jī)等級(jí)，輸出對(duì)應(yīng)的分?jǐn)?shù)段選擇結(jié)構(gòu)程序設(shè)計(jì)舉例212024/3/26示例2輸出斐波那契數(shù)列的前n項(xiàng)示例3輸入一個(gè)正整數(shù)n，輸出n的階乘示例1求1到100之間所有整數(shù)的和循環(huán)結(jié)構(gòu)程序設(shè)計(jì)舉例222024/3/2606函數(shù)、數(shù)組和指針在程序設(shè)計(jì)中的應(yīng)用232024/3/26要點(diǎn)三函數(shù)定義函數(shù)是一段可重用的代碼塊，用于執(zhí)行特定任務(wù)。定義函數(shù)時(shí)，需要指定函數(shù)名、參數(shù)列表和返回類型。要點(diǎn)一要點(diǎn)二函數(shù)調(diào)用通過(guò)函數(shù)名及所需參數(shù)來(lái)調(diào)用函數(shù)，執(zhí)行函數(shù)體內(nèi)的代碼。調(diào)用函數(shù)時(shí)，需要遵循函數(shù)定義的參數(shù)類型和順序。參數(shù)傳遞機(jī)制參數(shù)傳遞是函數(shù)調(diào)用過(guò)程中的重要環(huán)節(jié)，包括值傳遞和引用傳遞兩種方式。值傳遞是將參數(shù)值復(fù)制給函數(shù)內(nèi)部變量，而引用傳遞則是將參數(shù)的地址傳遞給函數(shù)，函數(shù)內(nèi)對(duì)參數(shù)的修改將影響原始數(shù)據(jù)。要點(diǎn)三函數(shù)定義、調(diào)用和參數(shù)傳遞機(jī)制242024/3/26數(shù)組定義數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)相同類型的元素。定義數(shù)組時(shí)，需要指定數(shù)組名、元素類型和數(shù)組大小。數(shù)組初始化在定義數(shù)組時(shí)，可以直接對(duì)數(shù)組元素進(jìn)行初始化。也可以通過(guò)循環(huán)或數(shù)組操作函數(shù)對(duì)數(shù)組進(jìn)行賦值。數(shù)組操作技巧包括數(shù)組的遍歷、查找、排序等操作。遍歷數(shù)組可以使用循環(huán)結(jié)構(gòu)；查找元素可以使用線性查找或二分查找等算法；排序可以使用冒泡排序、選擇排序、插入排序等算法。數(shù)組定義、初始化及操作技巧252024/3/26指針概念指針是一種特殊類型的變量，用于存儲(chǔ)內(nèi)存地址。通過(guò)指針可以間接訪問(wèn)和操作內(nèi)存中的數(shù)據(jù)。指針操作包括指針的聲明、賦值、解引用等操作。聲明指針時(shí)需要指定指針類型和變量名；賦值操作可以將變量的地址賦給指針；解引用操作可以通過(guò)指針訪問(wèn)內(nèi)存中的數(shù)據(jù)。指針在程序設(shè)計(jì)中應(yīng)用指針在程序設(shè)計(jì)中具有廣泛的應(yīng)用，如動(dòng)態(tài)內(nèi)存分配、數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)、函數(shù)調(diào)用參數(shù)傳遞等。使用指針可以提高程序的靈活性和效率，但同時(shí)也需要注意內(nèi)存泄漏和野指針等問(wèn)題。指針概念、操作及其在程序設(shè)計(jì)中應(yīng)用262024/3/2607文件操作與數(shù)據(jù)處理技術(shù)272024/3/26文件是存儲(chǔ)在外部介質(zhì)上的數(shù)據(jù)集合，通常以特定的格式進(jìn)行組織和存儲(chǔ)。根據(jù)文件的性質(zhì)和用途，可分為文本文件、二進(jìn)制文件、圖像文件、音頻文件、視頻文件等。文件概念及分類文件分類文件概念282024/3/26在使用文件前，需要先打開文件，使用完畢后要關(guān)閉文件，以釋放系統(tǒng)資源。文件打開與關(guān)閉從文件中讀取數(shù)據(jù)，可以使用不同的讀取方式，如逐行讀取、按塊讀取等。文件讀取向文件中寫入數(shù)據(jù)，可以使用不同的寫入方式，如追加寫入、覆蓋寫入等。文件寫入在文件中進(jìn)行定位，可以使用文件指針或文件位置標(biāo)記來(lái)實(shí)現(xiàn)。文件定位文件讀寫操作實(shí)現(xiàn)方法292024/3/26排序是將一組數(shù)據(jù)按照某種規(guī)則進(jìn)行排列的過(guò)程，常見的排序算法有冒泡排序、選擇排序、插入排序、歸并排序等。排序技術(shù)查找是在數(shù)據(jù)集合中查找指定元素的過(guò)程，常見的查找算法有線性查找、二分查找、哈希查找等。查找技術(shù)數(shù)據(jù)壓縮是減少數(shù)據(jù)存儲(chǔ)空間的過(guò)程，而數(shù)據(jù)加密是保護(hù)數(shù)據(jù)安全的過(guò)程，常見的壓縮算法和加密算法有多種。數(shù)據(jù)壓縮與加密除了排序、查找、壓縮和加密外，還有數(shù)據(jù)清洗、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘等其他數(shù)據(jù)處理技術(shù)。數(shù)據(jù)處理其他技術(shù)數(shù)據(jù)處理技術(shù)簡(jiǎn)介（如排序、查找等）302024/3/2608綜合案例分析與實(shí)戰(zhàn)演練312024/3/26問(wèn)題描述采用輾轉(zhuǎn)相除法求最大公約數(shù)，利用最大公約數(shù)求最小公倍數(shù)。算法設(shè)計(jì)代碼實(shí)現(xiàn)復(fù)雜度分析01020403分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并給出優(yōu)化建議。給定兩個(gè)正整數(shù)，求解它們的最大公約數(shù)和最小公倍數(shù)。使用Python語(yǔ)言實(shí)現(xiàn)算法，并給出詳細(xì)注釋和測(cè)試用例。案例一：求解最大公約數(shù)和最小公倍數(shù)問(wèn)題322024/3/26設(shè)計(jì)一個(gè)簡(jiǎn)單計(jì)算器，支持加、減、乘、除四種基本運(yùn)算。問(wèn)題描述算法設(shè)計(jì)代碼實(shí)現(xiàn)復(fù)雜度分析采用棧數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)表達(dá)式求值，處理運(yùn)算符優(yōu)先級(jí)和括號(hào)問(wèn)題。使用Python語(yǔ)言實(shí)現(xiàn)計(jì)算器功能，包括輸入處理、表達(dá)式解析和求值等部分。分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并給出優(yōu)化建議。案例二：實(shí)現(xiàn)簡(jiǎn)單計(jì)算器功能332024/3/26案例三：求解背包問(wèn)題優(yōu)化算法設(shè)計(jì)