3.排序

排序的算法很多，課本主要介紹里兩種排序方法：直接插入排序和冒泡排序

(1)直接插入排序

在日常生活中，經(jīng)常碰到這樣一類排序問題：把新的數(shù)據(jù)插入到已經(jīng)排好順序的數(shù)據(jù)列中。

例如：一組從小到大排好順序的數(shù)據(jù)列{1，3，5，7，9，11，13}，通常稱之為有序列，我們用序號(hào)1，2，3，……表示數(shù)據(jù)的位置，欲把一個(gè)新的數(shù)據(jù)8插入到上述序列中。

完成這個(gè)工作要考慮兩個(gè)問題：

(1)確定數(shù)據(jù)“8”在原有序列中應(yīng)該占有的位置序號(hào)。數(shù)據(jù)“8”所處的位置應(yīng)滿足小于或等于原有序列右邊所有的數(shù)據(jù)，大于其左邊位置上所有的數(shù)據(jù)。

(2)將這個(gè)位置空出來，將數(shù)據(jù)“8”插進(jìn)去。

對(duì)于一列無序的數(shù)據(jù)列，例如：{49，38，65，97，76，13，27，49}，如何使用這種方法進(jìn)行排序呢？基本思想很簡單，即反復(fù)使用上述方法排序，由序列的長度不斷增加，一直到完成整個(gè)無序列就有序了

首先，{49}是有序列，我們將38插入到有序列{49}中，得到兩個(gè)數(shù)據(jù)的有序列：

{38，49}，

然后，將第三個(gè)數(shù)據(jù)65插入到上述序列中，得到有序列：

{38，49，65}

…………

按照這種方法，直到將最后一個(gè)數(shù)據(jù)65插入到上述有序列中，得到

{13，27，38，49，49，65，76，97}

這樣，就完成了整個(gè)數(shù)據(jù)列的排序工作。注意到無序列“插入排序算法”成為了解決這類問題的平臺(tái)

(2)冒泡法排序

所謂冒泡法排序，形象地說，就是將一組數(shù)據(jù)按照從小到大的順序排列時(shí)，小的數(shù)據(jù)視為質(zhì)量輕的，大的數(shù)據(jù)視為質(zhì)量沉的。一個(gè)小的數(shù)據(jù)就好比水中的氣泡，往上移動(dòng)，一個(gè)較大的數(shù)據(jù)就好比石頭，往下移動(dòng)。顯然最終會(huì)沉到水底，最輕的會(huì)浮到頂，反復(fù)進(jìn)行，直到數(shù)據(jù)列排成為有序列。以上過程反映了這種排序方法的基本思路。

我們先對(duì)一組數(shù)據(jù)進(jìn)行分析。

設(shè)待排序的數(shù)據(jù)為：{49，38，65，97，76，13，27，49}

排序的具體操作步驟如下：

2．秦九韶算法

秦九韶算法的一般規(guī)則：

秦九韶算法適用一般的多項(xiàng)式f(x)=a_nxⁿ+a_n-1x^n-1+….+a₁x+a₀的求值問題。用秦九韶算法求一般多項(xiàng)式f(x)= a_nxⁿ+a_n-1x^n-1+….+a₁x+a₀當(dāng)x=x₀時(shí)的函數(shù)值，可把n次多項(xiàng)式的求值問題轉(zhuǎn)化成求n個(gè)一次多項(xiàng)式的值的問題，即求

v₀=a_n

v₁=a_nx+a_n－1

v₂=v₁x+a_n－2

v₃=v₂x+a_n－3

……..

v_n=v_n－1x+a₀

觀察秦九韶算法的數(shù)學(xué)模型，計(jì)算v_k時(shí)要用到v_k－1的值，若令v₀=a_n。

我們可以得到下面的遞推公式：

v₀=a_n

v_k=v_k－1+a_n－k(k=1,2,…n)

這是一個(gè)在秦九韶算法中反復(fù)執(zhí)行的步驟，可以用循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)

1．求最大公約數(shù)

(1)短除法

求兩個(gè)正整數(shù)的最大公約數(shù)的步驟：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是兩個(gè)互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來

(2)窮舉法(也叫枚舉法)

窮舉法求兩個(gè)正整數(shù)的最大公約數(shù)的解題步驟：從兩個(gè)數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)

(3)輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法求兩個(gè)數(shù)的最大公約數(shù)，其算法可以描述如下：

① 輸入兩個(gè)正整數(shù)m和n；

② 求余數(shù)r：計(jì)算m除以n，將所得余數(shù)存放到變量r中；

③更新被除數(shù)和余數(shù)：m=n，n=r；

④判斷余數(shù)r是否為0。若余數(shù)為0，則輸出結(jié)果；否則轉(zhuǎn)向第②步繼續(xù)循環(huán)執(zhí)行

如此循環(huán)，直到得到結(jié)果為止。

(4)更相減損術(shù)

我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術(shù)。在《九章算術(shù)》中記載了更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母•子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之

步驟：

Ⅰ．任意給出兩個(gè)正數(shù)；判斷它們是否都是偶數(shù)。若是，用2約簡；若不是，執(zhí)行第二步。

Ⅱ．以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)(等數(shù))就是所求的最大公約數(shù)。

算法是高中數(shù)學(xué)新課程中的新增內(nèi)容，本講的重點(diǎn)是幾種重要的算法案例思想，復(fù)習(xí)時(shí)重算法的思想輕算法和程序的構(gòu)造。

預(yù)測2010年高考隊(duì)本講的考察是：以選擇題或填空題的形式出現(xiàn)，分值在5分左右，考察的熱點(diǎn)是算法實(shí)例和傳統(tǒng)數(shù)學(xué)知識(shí)的結(jié)合題目

32．(湖北卷)某單位最近組織了一次健身活動(dòng)，活動(dòng)分為登山組和游泳組，且每個(gè)職工至多參加了其中一組。在參加活動(dòng)的職工中，青年人占42.5%，中年人占47.5%，老年人占10%。登山組的職工占參加活動(dòng)總?cè)藬?shù)的，且該組中，青年人占50%，中年人占40%，老年人占10%。為了了解各組不同的年齡層次的職工對(duì)本次活動(dòng)的滿意程度，現(xiàn)用分層抽樣的方法從參加活動(dòng)的全體職工中抽取一個(gè)容量為200的樣本。試確定

(1)游泳組中，青年人、中年人、老年人分別所占的比例；

(2)游泳組中，青年人、中年人、老年人分別應(yīng)抽取的人數(shù)

本小題主要考查分層抽樣的概念和運(yùn)算，以及運(yùn)用統(tǒng)計(jì)知識(shí)解決實(shí)際問題的能力.

解　 (1)設(shè)登山組人數(shù)為，游泳組中，青年人、中年人、老年人各占比例分別為a、b、c，則有，解得b=50%,c=10%.

故a=100%－50%－10%=40%,即游泳組中，青年人、中年人、老年人各占比例分別為40%、

50%、10%。

(2)游泳組中，抽取的青年人數(shù)為(人)；抽取的中年人數(shù)為

50%＝75(人)；抽取的老年人數(shù)為10%＝15(人)

0.7100+0.35=70.35

故耗能減少了90-70.35=19.65(噸)

30．(2007廣東理)下表提供了某廠節(jié)能降耗技術(shù)改造后生產(chǎn)甲產(chǎn)品過程中記錄的產(chǎn)量(噸)與相應(yīng)的生產(chǎn)能耗 (噸標(biāo)準(zhǔn)煤)的幾組對(duì)照數(shù)據(jù)

　　 (1)請(qǐng)畫出上表數(shù)據(jù)的散點(diǎn)圖；

　　 (2)請(qǐng)根據(jù)上表提供的數(shù)據(jù)，用最小二乘法求出關(guān)于的線性回歸方程；

　　 (3)已知該廠技改前100噸甲產(chǎn)品的生產(chǎn)能耗為90噸標(biāo)準(zhǔn)煤．試根據(jù)(2)求出的線性

回歸方程，預(yù)測生產(chǎn)100噸甲產(chǎn)品的生產(chǎn)能耗比技改前降低多少噸標(biāo)準(zhǔn)煤?

　 　(參考數(shù)值：)

　解 　(1)如下圖

(2)=32.5+43+54+64.5=66.5

==4.5

==3.5

=+++=86

故線性回歸方程為y=0.7x+0.35

(3)根據(jù)回歸方程的預(yù)測，現(xiàn)在生產(chǎn)100噸產(chǎn)品消耗的標(biāo)準(zhǔn)煤的數(shù)量為

28．(2007湖南文)(本小題滿分12分)在生產(chǎn)過程中，測得纖維產(chǎn)品的纖度(表示纖維粗細(xì)的一種量)共有100個(gè)數(shù)據(jù)，將數(shù)據(jù)分組如右表：

(1)在答題卡上完成頻率分布表，并在給定的坐標(biāo)系中畫出頻率分布直方圖；

(2)估計(jì)纖度落在中的概率及纖度小于的概率是多少？

(3)統(tǒng)計(jì)方法中，同一組數(shù)據(jù)常用該組區(qū)間的中點(diǎn)值(例如區(qū)間的中點(diǎn)值

是)作為代表．據(jù)此，估計(jì)纖度的期望．

分組	頻數(shù)
合計(jì)

解　 (Ⅰ)

分組	頻數(shù)	頻率
	4	0.04
	25	0.25
	30	0.30
	29	0.29
	10	0.10
	2	0.02
合計(jì)	100	1.00

(Ⅱ)纖度落在中的概率約為，纖度小于1.40的概率約為．

(Ⅲ)總體數(shù)據(jù)的期望約為

27．(2007湖南文)根據(jù)某水文觀測點(diǎn)的歷史統(tǒng)計(jì)數(shù)據(jù)，得到某條河流水位的頻率分布直方圖(如圖2)．從圖中可以看出，該水文觀測點(diǎn)平均至少一百年才遇到一次的洪水的最低水位是　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 (　　 )

A．48米　　　　 B．49米　　 C．50米 　　　　 D．51米

　　 答案　 C