【導(dǎo)讀】函數(shù)是程序設(shè)計(jì)語言中最重要的部分，是模。塊化設(shè)計(jì)的主要工具。即使你自己不定義新的函數(shù),在每一個(gè)完整的。C++程序中都必須有一個(gè)main()函數(shù)。在C++語言中，字符處理、字符串處理和數(shù)學(xué)。計(jì)算都是用函數(shù)的方式提供的。表示一個(gè)函數(shù)沒有返回值，類型標(biāo)識(shí)符用void。return返回值；或return（返回值）；函數(shù)名是一個(gè)標(biāo)識(shí)符，符合標(biāo)識(shí)符命名。打印一個(gè)由五行組成的三角形。從終端獲取一個(gè)1–10之間的整型數(shù)。判斷某一年是否為潤年的函數(shù)。所有函數(shù)在使用前必須被聲明，以便讓編譯器知道。用戶的用法是否正確。函數(shù)聲明包括下列內(nèi)容：。庫函數(shù)在調(diào)用前需要＃include相應(yīng)的頭文件。函數(shù)原型說明與函數(shù)首部寫法上需要保持一致，了函數(shù)聲明，則在主調(diào)函數(shù)中無須再作聲明。形式參數(shù)和實(shí)際參數(shù)的個(gè)數(shù)、排列次序、類型要。實(shí)際參數(shù)可以是常量、變量、表達(dá)式，甚至是另

　　

【正文】 程序設(shè)計(jì) 107 主程序 int col[9]。 bool a[9], b[17],c[17]。 int main() { int j。 for(j = 0。 j =8。 j++) a[j] = true。 for(j = 0。 j = 16。 j++) b[j] = c[j] = true。 queen_a11(1)。 return 0。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 108 基于遞歸的算法 ? 回溯法 ? 分治法 ? 動(dòng)態(tài)規(guī)劃 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 109 遞歸與分而治之法 ? 分而治之法 ?分：分成較小的可以遞歸解決的問題 ?治：從子問題的解形成原始問題的解 ? 分而治之算法通常都是高效的遞歸算法 ? 在分而治之法中，遞歸是“分”，額外的開銷是“治” 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 110 最大連續(xù)子序列問題 ? 給定 (可能是負(fù)的 )整數(shù)序列 ，尋找 (并標(biāo)識(shí) ) 的值為最大的序列。如果所有的整數(shù)都是負(fù)的，那么最大連續(xù)子序列的和是零。 ? 例如，假設(shè)輸入是 {2, 11, 4, 13, 5, 2}，那么答案是 20，它表示連續(xù)子序列包含了第 2項(xiàng)到第 4項(xiàng)（如粗體字部分）。又如第二個(gè)例子，對(duì)于輸入{1, 3, 4, 2, 1, 6},答案是 7，這個(gè)子序列包含最后四項(xiàng)。 NAAA ,. .., 2112, ,..., NA A A? ?j ik kA《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 111 分而治之法的解題思路 ? 假設(shè)輸入是 {4，－ 3， 5，－ 2，－ 1， 2， 6，－ 2}。我們把這個(gè)輸入劃分成兩部分，前四個(gè)和后四個(gè)。這樣最大連續(xù)子序列的和可能出現(xiàn)在下面三種情況中。 ?情況 1：整個(gè)位于前半部，可遞歸計(jì)算。 ?情況 2：整個(gè)位于后半部，可遞歸計(jì)算。 ?情況 3：從前半部開始但在后半部結(jié)束。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 112 情況 3的解決方法 ? 從兩半部分的邊界開始，通過從右到左的掃描來找到左半段的最長序列。類似地，從左到右的掃描找到右半段的最長序列。把這兩個(gè)子序列組合起來，形成跨越分割邊界的最大連續(xù)子序列。 ? 在這個(gè)實(shí)例中，結(jié)果序列是從第一部分的第一個(gè)元素到第二部分的其余元素。總和是兩個(gè)子序列的和，即 4+7=11. 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 113 算法總結(jié) ? 遞歸地計(jì)算整個(gè)位于前半部的最大連續(xù)子序列。 ? 遞歸地計(jì)算整個(gè)位于后半部的最大連續(xù)子序列。 ? 通過兩個(gè)連續(xù)循環(huán)，計(jì)算從前半部開始但在后半部結(jié)束的最大連續(xù)子序列的和。 ? 選擇三個(gè)和中的最大值。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 114 Int maxSum(int a[ ], int left, int right ) { int maxLeft, maxRight, center。 int leftSum = 0, rightSum = 0。 int maxLeftTmp = NEGMAX, maxRightTmp = NEGMAX。 center = ( left + right ) / 2。 if ( left == right ) return a[left] 0 ? a[left] : 0。 maxLeft = maxSum(a, left, center)。 maxRight = maxSum(a, center + 1, right)。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 115 for (int i = center。 i = left。 i) { leftSum += a[i]。 if (leftSum maxLeftTmp) maxLeftTmp = leftSum。 } for (int i = center + 1。 i = right。 ++i) { rightSum += a[i]。 if (rightSum maxRightTmp) maxRightTmp = rightSum。 } return max3(maxLeft, maxRight, maxLeftTmp + maxRightTmp)。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 116 快速排序 ? 思路： ?將待排序的數(shù)據(jù)放入數(shù)組 a中，數(shù)據(jù)為a[low], … , a[high] ?從待排序的數(shù)據(jù)中任意選擇一個(gè)，如 a[low]，將它放入變量 k ?將待排序的數(shù)據(jù)分成兩組，一組比 k小，放入數(shù)組的前一半；一組比 k大，放入數(shù)組的后一半；將 k放入中間位置。 ?對(duì)前一半和后一半分別重復(fù)上述方法。 ? 最好時(shí)間效率： O(nlogn) 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 117 5 7 3 0 4 2 1 9 6 8 1 2 3 0 4 5 7 6 8 9 low high 1 2 3 0 4 5 7 6 8 9 0 1 3 2 4 5 7 6 8 9 0 1 2 3 4 5 7 6 8 9 0 1 2 3 4 5 6 7 8 9 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 118 快速排序要解決的問題 ? 如何選擇作為分段基準(zhǔn)的元素？ ?采用第一個(gè)元素 ?選取第一個(gè)、中間一個(gè)和最后一個(gè)中的中間元素 ? 如何分段？考慮空間問題 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 119 快速排序函數(shù) Void quicksort(int a[], int low, int high) { int mid。 if (low = high) return。 mid = divide(a, low, high)。 quicksort( a, low, mid1)。 quicksort( a, mid+1, high)。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 120 劃分過程 ? 從右向左開始檢查。如果 high的值大于 k， high減 1，繼續(xù)往前檢查，直到遇到一個(gè)小于 k的值。 ? 將大于 k的這個(gè)值放入 low的位置。然后從 low位置開始從左向右檢查，直到遇到一個(gè)大于 k的值。 ? 將 low位置的值放入 high位置，重復(fù)第一步，直到 low和 high重疊。將 k放入此位置。 5 7 3 0 4 2 1 9 6 8 low high K=5 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 121 7 3 0 4 2 1 9 6 8 low high K=5 7 3 0 4 2 1 9 6 8 low high 1 7 3 0 4 2 9 6 8 low high 1 3 0 4 2 7 9 6 8 low high 1 2 3 0 4 7 9 6 8 low high 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 122 Divide函數(shù) Int divide( int a[], int low, int high) { int k = a[low]。 do { while (lowhigh amp。amp。 a[high]=k) high。 if (low high) { a[low] = a[high]。 ++low。} while (low high amp。amp。 a[low] =k) ++low。 if (low high) a[high] = a[low]。 } while (low != high)。 a[low] = k。 return low。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 123 基于遞歸的算法 ? 回溯法 ? 分治法 ? 動(dòng)態(tài)規(guī)劃 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 124 動(dòng)態(tài)規(guī)劃的思想 ? 在實(shí)際中經(jīng)常會(huì)遇到一個(gè)復(fù)雜的問題不能簡單地分成幾個(gè)子問題，而是會(huì)分解出一系列的子問題。如果用分治法的話會(huì)使得遞歸調(diào)用的次數(shù)呈指數(shù)增長。如Finonacci數(shù)列的計(jì)算，第 i個(gè) Fibonacci數(shù)是前兩個(gè)Fibonacci數(shù)之和。 ? 它是基于分而治之算法。在每一階段都將當(dāng)前問題分解為多個(gè)已解決的子問題 ? 為解決遞歸爆炸問題，通常先找出小問題的解，記錄在一個(gè)表中，在解決大問題時(shí)不需要遞歸，只需要從表中取出小問題的解。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 125 找零問題 ? 對(duì)于一種貨幣，有面值為 C1, C2, …, CN(分 )的硬幣，最少需要多少個(gè)硬幣來找出 K分錢的零錢。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 126 貪婪法解法 ? 我們不斷使用可能的最大面值的硬幣 ? 如：美元的硬幣有 10和 25分的面值 (忽略流通頻率很低的 50分硬幣 )。我們可以通過使用 2個(gè)25分、一個(gè) 10分的硬幣以及三個(gè) 1分來找出 63分錢，一共是 6個(gè)硬幣。 ? 如果美元中包含一個(gè) 21分硬幣時(shí)，貪心算法仍然給出一個(gè)用六個(gè)硬幣的解，但是最佳的解是用三個(gè)硬幣 (三個(gè)都是 21分的硬幣。 ) 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 127 解法 1 －－分治法 ? 如果我們可以用一個(gè)硬幣找零，這就是最小的。 ? 否則，對(duì)于每個(gè)可能的值 i，我們可以獨(dú)立計(jì)算找 i分錢零錢和 Ki分錢需要的最小硬幣數(shù)。然后選擇這個(gè)和最小的 i。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 128 怎樣找出 63分錢零錢 ? 找出 1分錢零錢和 62分錢零錢分別需要的硬幣數(shù)是 1和 4。因此， 63分錢需要使用五個(gè)硬幣。 ? 找出 2分錢和 61分錢分別需要 2和 4個(gè)硬幣，一共是六個(gè)硬幣。 ? 我們繼續(xù)嘗試所有的可能性。我們看到一個(gè) 21分和 42分的分解，它可以分別用一個(gè)和兩個(gè)硬幣來找開，因此，這個(gè)找零問題就可以用三個(gè)硬幣解決。 ? 我們需要嘗試的最后一種分解是 31分和 32分。我們可以用兩個(gè)硬幣找出 31分零錢，用三個(gè)硬幣找出 32分零錢，一共是五個(gè)硬幣。 ? 因此最小值是三個(gè)硬幣。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 129 int coin(int k) { int i, tmp, int coinNum = k。 if （能用一個(gè)硬幣找零） return 1。 for (i=1。 ik。 ++i) if ((tmp = coin(i) + coin(ki)) coinNum) coinNum = tmp。 return coinNum。 } 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 130 上述解法分析 ? 此算法的效率很低 ? 事實(shí)上 63分錢找零的問題是不會(huì)在一個(gè)合理的時(shí)間內(nèi)解決的。就如 Finbonacci 函數(shù)一樣 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 131 解法 2 ? 通過指定其中的一個(gè)硬幣來遞歸地簡化問題。 ? 例如，對(duì)于 63分錢，我們可以給出以下找零的辦法。 ? 一個(gè) 1分的硬幣加上遞歸地分派 62分錢 ? 一個(gè) 5分的硬幣加上遞歸地分派 58分錢 ? 一個(gè) 10分的硬幣加上遞歸地分派 53分錢 ? 一個(gè) 21分的硬幣加上遞歸地分派 42分錢 ? 一個(gè) 25分的硬幣加上遞歸地分派 38分錢 ? 該算法的問題仍然是效率問題 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 132 動(dòng)態(tài)規(guī)劃解 ? 效率低下主要是由于重復(fù)計(jì)算造成的。因此，可把已有子問題的答案存放起來，當(dāng)再次遇到此子問題時(shí)就不用重復(fù)計(jì)算了。 ? 在本例中，我們用 coinsUsed[i]代表了找i分零錢所需的最小硬幣數(shù)。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 133 算法思想 ? 先找出一分錢的找零方法，把最小硬幣數(shù)存入 coinUsed[1] ? 依次找出 2分錢、 3分錢 … 的找零方法，知道到達(dá)要找零的錢為止： ?對(duì)每個(gè)要找的零錢 i，可以把 i分解成某個(gè)coins[j]和 i coins[j]， ?所需硬幣數(shù)為 coinUsed[icoins[j]]+1。對(duì)所有的 j，取最小的 coinUsed[icoins[j]]+1作為 i元錢找零的的答案。 《 程序設(shè)計(jì) 》 程序設(shè)計(jì) 134 函數(shù)原型 ?