高中信息技術(shù)必修一

數(shù)據(jù)與計算第二章算法與程序?qū)崿F(xiàn)第三節(jié)常用算法及其程序?qū)崿F(xiàn)當(dāng)今社會,人們可以借助計算機來解決的問題越來越多,但由于問題類型和復(fù)雜程度的不同,很難有解決所有問題的統(tǒng)一算法。因此,只能針對某個或某類問題,通過分析研究,尋找解決問題的適當(dāng)算法。課堂導(dǎo)入某些智能跑步機的配套移動應(yīng)用程序除了能記錄和顯示運動過程中人體的各項身體數(shù)據(jù),還可以提供豐富的跑步訓(xùn)練課程,讓用戶可以在科學(xué)的課程指導(dǎo)下,達到更好的鍛煉,如圖2.17所示。思考：

如果要在移動應(yīng)用程序上顯示用戶跑步訓(xùn)練課程的報表信息,例如顯示用戶在一周內(nèi)已經(jīng)完成的訓(xùn)練項目和未完成的訓(xùn)練項目等信息,應(yīng)該如何實現(xiàn)?如果時間跨度延長至一個月,又應(yīng)該如何實現(xiàn)?一、枚舉法在生活中,人們有時會遇到數(shù)字密碼鎖打不開的情況。遇到這種情況,大部分人會采用類似的解決方法,那就是逐個數(shù)字進行嘗試,直到打開為止,如圖2.18所示。這種逐一嘗試的方法在算法中被稱之為枚舉法,它是處理問題常用的算法思想之一。圖2.18數(shù)字密碼鎖問題所涉及的情況有哪些,情況的種數(shù)是否可以確定;確定范圍驗證條件這些情況需要滿足什么條件才能成為問題的解答。圖2.19使用枚舉法“挑選蘋果”的流程圖表2.21“求解最大公約數(shù)”的程序二、枚舉法的程序?qū)崿F(xiàn)一般,智能跑步機配套的移動應(yīng)用程序會通過統(tǒng)計報表的形式給用戶提供明確的跑步訓(xùn)練課程完成度信息,用戶也可以選擇日報表、周報表或月報表進行查看。假設(shè)用戶設(shè)定的某跑步訓(xùn)練課程需要持續(xù)一周,每天需要完成固定的訓(xùn)練內(nèi)容和時長,完成后的數(shù)據(jù)會上傳到遠程服務(wù)器上。1.請設(shè)計算法,顯示某用戶在訓(xùn)練課程中完成了哪幾項訓(xùn)練內(nèi)容,未完成哪幾項訓(xùn)練內(nèi)容。

2.選用適當(dāng)?shù)姆椒枋鏊惴?。輸?跑步課程中的每日訓(xùn)練內(nèi)容和對應(yīng)訓(xùn)練內(nèi)容消耗的卡路里數(shù),這些信息由程序自動

讀取數(shù)據(jù)庫中存儲的數(shù)據(jù),不需要用戶輸入;

輸出:完成的項目數(shù)和未完成的項目名稱;1.抽象與建模2.設(shè)計算法3.編寫程序4.調(diào)試運行在Python環(huán)境中調(diào)試運行以上程序,結(jié)果顯示如下:假設(shè)每項訓(xùn)練內(nèi)容都有要求的卡路里消耗最低值,請參考以上程序進行編程,實現(xiàn)統(tǒng)計“該用戶哪些訓(xùn)練項目未達標”,請將你的分析和程序填入表2.22中。

例如,每項訓(xùn)練內(nèi)容要求的卡路里消耗最低值存儲在mindata[380,580,380,450,380,650,380]中,從中可以看出“坡度練習(xí)”訓(xùn)練要求的卡路里消耗最低值為650千卡。

請同學(xué)們分析一下本題使用枚舉法實現(xiàn)的Python程序,從程序結(jié)構(gòu)的角度上總結(jié)枚舉法一般需要包含哪幾種基本控制結(jié)構(gòu)。項目實踐表2.22算法分析及程序?qū)崿F(xiàn)表排序和查找排序算法,就是如何使得記錄按照要求(升序或降序)排列的方法。與枚舉法一樣,排序算法早在計算機出現(xiàn)之前就已經(jīng)被人們在實際生活中使用了。人們可以通過“看一眼”“掃一遍”的方式對兩個數(shù)據(jù)快速分辨大小,因此可以在較短的時間內(nèi)對有限的數(shù)據(jù)快速地進行排序。而計算機只有通過比較才能夠分清兩個數(shù)(在計算機中不僅僅指數(shù)值數(shù)據(jù))的大小,從而在排序時要進行反復(fù)的比較和交換,但由于計算機具有高速運算的能力,因此面對大數(shù)據(jù)量時就比人顯得更有優(yōu)勢。

選擇排序的基本思想非常直接,每一次從序列的所有元素中先找到最小的,然后放到第一個位置。之后再看剩余元素中最小的,放到第二個位置……依此類推,就可以完成整個排序工作了。選擇排序的關(guān)鍵是幫助固定位置找到合適的元素。

例如,待排序數(shù)據(jù)為“456712783923”,使用選擇排序算法的排序過程如表2.23所示。表2.23選擇排序算法過程記錄表冒泡排序快速排序插入排序堆排序歸并排序選擇排序順序查找順序查找是一種最基本、最簡單的查找算法。例如,使用順序查找在手機通信錄里查找名字叫“孫老師”的聯(lián)系人信息,則需要從通信錄的第一個聯(lián)系人開始,逐個往下比較,直到找到名字叫“孫老師”的聯(lián)系人為止。如果所有聯(lián)系人都查找完了,仍舊找不到這個聯(lián)系人,則表示查找不成功。二分查找二分查找也稱為折半查找,其基本思想是當(dāng)待查找數(shù)據(jù)有序時,首先找到待查找數(shù)據(jù)中的中間元素,將其值與關(guān)鍵字進行比較,若不等,則根據(jù)該值與關(guān)鍵字的比較結(jié)果來決定繼續(xù)查找待查數(shù)據(jù)的前半部分或后半部分。查找算