第十七課：數(shù)據(jù)結(jié)構(gòu)上-wenkub.com
2024-09-24 13:04 本頁(yè)面
【正文】 獨(dú)立實(shí)踐 ?實(shí)踐 1 對(duì)一個(gè) 15個(gè)元素的隨機(jī)整數(shù)(0=n=100)數(shù)組中查找元素 83的下標(biāo) . (提示，先用冒泡法排序，然后 2分法查找 ) ?實(shí)踐 2 編寫(xiě)遞歸實(shí)現(xiàn) 5! ?實(shí)踐 3 用遞歸實(shí)現(xiàn) 10個(gè)數(shù)的菲波拉契數(shù)列 ?實(shí)踐 4 用遞歸法求任意 2個(gè)整數(shù)的最大公約數(shù)(GCD)。首先，我們來(lái)了解下計(jì)算機(jī)的方法調(diào)用機(jī)制： 1．程序執(zhí)行前，計(jì)算機(jī)會(huì)在內(nèi)存中創(chuàng)建一個(gè)調(diào)用棧 ，一般會(huì)比較大 2．當(dāng)調(diào)用某個(gè)方法時(shí)，會(huì)有一個(gè)和該被調(diào)用方法相關(guān)的記錄信息被推入到棧中 3．被推入到棧中的記錄信息包括內(nèi)容：傳遞到被調(diào)用方法中的參數(shù)值、該方法的局部變量、該方法的返回值。 } } ?實(shí)現(xiàn)遞歸必須滿足兩個(gè)條件 ? 基本條件 (base case)的成立 實(shí)際上就是定義遞歸應(yīng)該什么時(shí)候終止 ? 遞歸步驟 對(duì)于所有的 n值，函數(shù)都是以其自身通過(guò) n值較小的函數(shù)來(lái)定義，也就是說(shuō)，所有 n值函數(shù)通過(guò)許多步驟來(lái)達(dá)到最終用 n值較小的函數(shù) (基本條件 )來(lái)定義。 } static int sum(int i){ int count = 0。但是，在最佳情況下 (即數(shù)組中的元素順序是完全正確的 )，插入排序的性能是線性的。 } array[k + 1] = insert_item。 int k = i。在內(nèi)循環(huán)中，將第 i個(gè)元素和該元素之前的所有元素一一對(duì)比，并將元素插入到合適的位置，如果第 i個(gè)元素的位置是正確的，那么就跳出內(nèi)循環(huán)，重新開(kāi)始外循環(huán)。 arr[j + 1] = tmp。 j n 1。amp。 這個(gè)過(guò)程會(huì)使數(shù)組中的最大 (最小 )元素逐漸冒到數(shù)組的最后 (最前 ). static int[] bubbleSort(int[] arr){ int flag = 1, tmp。 ?我們可以分析得知，當(dāng)數(shù)組非常大時(shí)，用于元素交換的開(kāi)銷也相當(dāng)大。 arr[small] = tmp。 j 。 for(int i = 0。 以二分法查找 4的下標(biāo)。 else front = middle + 1。 int tail = 1。 return false。 注意：要求被查找的數(shù)組中的元素是無(wú)序的、隨機(jī)的。 條件 2： 當(dāng) n增大時(shí)， f(n)/g(n)趨向于 0 當(dāng)滿足此條件 2時(shí)，則該兩個(gè)增長(zhǎng)函數(shù)有不同的增長(zhǎng)率。 i = test_data。一般，我們主要測(cè)試后一種指令。第十七課：數(shù)據(jù)結(jié)構(gòu) (上 ) 周甫 學(xué)習(xí)目標(biāo) 各種常用算法、排序算法的掌握 1 遞歸算法 2 快速排序算法 3 1 算法 (algorithm) ?什么是算法 ? 對(duì)一個(gè)現(xiàn)有的問(wèn)題我們采取的解決過(guò)程及方法 ,即為算法 . 一個(gè)用算法實(shí)現(xiàn)的程序會(huì)耗費(fèi)兩種資源：處理時(shí)間和內(nèi)存。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1