【正文】 模板的實例化： ?根據(jù)實際參數(shù)確定模板參數(shù)的值 ?將模板參數(shù)的值代入函數(shù)模板，形成一個真正的函數(shù) 《 程序設計 》 程序設計 44 第 6章 過程封裝－－函數(shù) ? 函數(shù) ? 自己編寫函數(shù) ? 函數(shù)的使用 ? 數(shù)組作為參數(shù) ? 帶默認值的函數(shù) ? 內(nèi)聯(lián)函數(shù) ? 重載函數(shù) ? 函數(shù)模版 ? 變量的作用域 ? 變量的存儲類別 ? 遞歸函數(shù) ? 基于遞歸的算法 《 程序設計 》 程序設計 45 標識符的作用域 ? 一個標識符能被存取的程序部分，稱為標識符的作用域 ? 標識符的作用域與程序塊有關。 cout a b。 ? 在一個函數(shù)中，我們不能存取主調(diào)程序的變量，即使知道該變量的名字。如在作用范圍外的函數(shù)要使用此變量，用關鍵詞 extern在函數(shù)內(nèi)說明此全局變量。 cout ―f1: p,q,r=― p q r。 r = 2*r。 cout ―after f3: p,q,r=‖ p q r。 cout ―after f2: p,q,r=‖ p q r。當退出塊時，系統(tǒng)釋放分配給自動變量的值。 ? 如無合適的寄存器可用，則編譯器把它設為自動變量。 ? 用途： ? 在某函數(shù)中引用了一個聲明在本函數(shù)后的全局變量時，需要在函數(shù)內(nèi)用 extern聲明此全局變量。 extern int x。 } // include iostream using namespace std。 ? 兩類靜態(tài)變量： ?靜態(tài)的局部變量 ?靜態(tài)的外部變量 《 程序設計 》 程序設計 57 靜態(tài)的局部變量 ? 允許局部變量保存它的原有值，以便在次進入塊時還可以使用此值。 c=c+1。 i3。 《 程序設計 》 程序設計 59 靜態(tài)變量的使用 ? 未被程序員初始化的靜態(tài)變量都由系統(tǒng)初始化為 0。 《 程序設計 》 程序設計 60 void a()。 main() { int x=6。 c()。 b()。} void a() {int x=25。} void c() { extern int x。 void d(int x) { cout ―x in d is ‖ ++x endl。 else return (遞歸調(diào)用同一函數(shù) )； 基本情況 《 程序設計 》 程序設計 65 典型的遞歸函數(shù) —階乘函數(shù) n!=1*2*3*4*…*(n 1)*n (n1)! 遞歸形式： ??????其他)!1(*01!nnnn遞歸終止條件 long p(int n) {if (n == 0) return 1。 } } 《 程序設計 》 程序設計 67 Fibonacci函數(shù) 0 0 1 1 2 1 3 2 4 3 5 5 6 8 ???????????其他)2()1(1100)(nFnFnnnFint f(int n) {if (n==0) return 0。 這種方法容易理解 ， 也容易實現(xiàn) ?由于 n! = n (n1)! 數(shù)學里定義 0！ ＝ 1，從而 n!可以用下面的遞歸公式表示： )1()!1()1,0(1{!?????nnnnn《 程序設計 》 程序設計 69 遞歸函數(shù)設計 int p(int n) { if(n= = 0) return (1)。 ? 迭代程序復雜，但效率高。 else return (f(n1)+f(n2))。 for ( i = 2。 fn_1 = fn。 《 程序設計 》 程序設計 75 遞歸過程 數(shù)字旋轉(zhuǎn)方陣（蛇陣） ? 數(shù)字旋轉(zhuǎn)方陣如右圖所示。 ? 根據(jù)上述思想，可以設計一個遞歸函數(shù) fill。 int main() { int row, col, size。 for (row = 0。 col size。 } 《 程序設計 》 程序設計 78 Fill函數(shù)的設計 ? 自上而下填最左列 ? 自左而右填最下行 ? 自下而上填最右列 ? 自右而左填最上行 ? 遞歸調(diào)用 fill，規(guī)模減 2，起始位置為原來的下一行下一列，填入的起始數(shù)字為填入一圈后的第一個數(shù)字。 return。 isize1。 } for (i=0。 ++number。 p[row][col] = number。 ++i) { col。 } 《 程序設計 》 程序設計 80 遞歸過程 —Hanoi塔問題 目標： 將 A上的盤子全部移到 B上 規(guī)則： 每次只能移動一個盤子 不允許大盤子放在小盤子上 A B C 《 程序設計 》 程序設計 81 Hannoi塔 ? n＝ 4（最開始的情況） n＝ 4（完成情況） 《 程序設計 》 程序設計 82 Hannoi塔 ? 第 1步：從開始的桿到輔助桿（ src到 aux） ? 第 2步：從開始桿到目的桿（ src到 dst） 《 程序設計 》 程序設計 83 Hannoi塔 ? 第 3步：從輔助桿到目的桿（ aux到 dst） ? 第 4步：從開始的桿到輔助桿（ src到 aux） 《 程序設計 》 程序設計 84 Hannoi塔 ? 第 5步：從目的桿到開始桿（ dst 到 src） ? 第 6步：從目的桿到輔助桿（ dst到 aux） 《 程序設計 》 程序設計 85 Hannoi塔 ? 第 7步：從開始桿到目的桿（ src 到 dst ） ? 第 8步：從開始桿到目的桿（ src到 dst） 《 程序設計 》 程序設計 86 Hannoi塔 ? 第 9步：從輔助桿到目的桿（ aux 到 dst ） ? 第 10步：從輔助桿到開始的桿（ aux到 src ） 《 程序設計 》 程序設計 87 Hannoi塔 ? 第 11步：從目的桿到開始桿（ dst 到 src） ? 第 12步：從輔助桿到目的桿（ aux 到 dst ） 《 程序設計 》 程序設計 88 Hannoi塔 ? 第 13步：從開始的桿到輔助桿（ src到 aux） ? 第 14步：從開始桿到目的桿（ src到 dst） 《 程序設計 》 程序設計 89 Hannoi塔 ? 第 15步：從輔助桿到目的桿（ aux 到 dst ） 《 程序設計 》 程序設計 90 解題思路 ? 最簡單的情況，只有一個盤子：將盤子直接從 A移到 B ? 大于一個盤子的情況： ?將除了最下面一個盤子外的所有盤子從 A移到 C ?將最下面的盤子從 A移到 B ?將 C上的盤子移回 B 《 程序設計 》 程序設計 91 Hanoi 塔函數(shù) void Hanoi(int n, char start, char finish, char temp) { if (n==1) cout start finish 39。\t39。 ? 對 n個字符的排列來講，第一個元素有 n 種選擇，對每種選擇，排列后面 n1個元素。 《 程序設計 》 程序設計 96 排列函數(shù) Void PermuteWithFixedPrefix (char str[ ], int k) { int i。 ++i) { swap(str, k, i)。 } 《 程序設計 》 程序設計 98 第 6章 過程封裝－－函數(shù) ? 函數(shù) ? 自己編寫函數(shù) ? 函數(shù)的使用 ? 數(shù)組作為參數(shù) ? 帶默認值的函數(shù) ? 內(nèi)聯(lián)函數(shù) ? 重載函數(shù) ? 函數(shù)模版 ? 變量的作用域 ? 變量的存儲類別 ? 遞歸函數(shù) ? 基于遞歸的算法 《 程序設計 》 程序設計 99 基于遞歸的算法 ? 回溯法 ? 分治法 ? 動態(tài)規(guī)劃 《 程序設計 》 程序設計 100 回溯法 ? 首先暫時放棄問題規(guī)模大小的限制 ， 并將問題的候選解按某種順序逐一枚舉和檢驗 。 ? 尋找下一候選解的過程成為回朔 。 開始時配置在第一行 ， 以后改變時 ， 順序選擇第二行 、 第三行 、 。 i =8。 ? 因為在每一列上恰好放一個皇后 ， 所以引入一個一維數(shù)組(設為 col（ 9） )， 值 col[j]表示在棋盤第 j列上的皇后位置 。 《 程序設計 》 程序設計 105 候選解的合理性檢查 ? 引入以下三個工作數(shù)組 ?數(shù)組 a[9]， a[A]=true表示第 A行上還沒有皇后； ?數(shù)組 b[16]， b[A]=true表示第 A條右高左低斜線上沒有皇后；從左上角依次編到右下角 (115)。 char awn。amp。 a[i] = b[k+i1] = c[8+ki] = false。\t39。 if (awn==39。) exit(0)。 bool a[9], b[17],c[17]。 j++) a[j] = true。 queen_a11(1)。 ? 例如，假設輸入是 {2, 11, 4, 13, 5, 2}，那么答案是 20，它表示連續(xù)子序列包含了第 2項到第 4項（如粗體字部分）。這樣最大連續(xù)子序列的和可能出現(xiàn)在下面三種情況中。 《 程序設計 》 程序設計 112 情況 3的解決方法 ? 從兩半部分的邊界開始，通過從右到左的掃描來找到左半段的最長序列?？偤褪莾蓚€子序列的和，即 4+7=11. 《 程序設計 》 程序設計 113 算法總結(jié) ? 遞歸地計算整個位于前半部的最大連續(xù)子序列。 《 程序設計 》 程序設計 114 Int maxSum(int a[ ], int left, int right ) { int maxLeft, maxRight, center。 if ( left == right ) return a[left] 0 ? a[left] : 0。 i = left。 i = right。 } 《 程序設計 》 程序設計 116 快速排序 ? 思路： ?將待排序的數(shù)據(jù)放入數(shù)組 a中，數(shù)據(jù)為a[low], … , a[high] ?從待排序的數(shù)據(jù)中任意選擇一個，如 a[low]，將它放入變量 k ?將待排序的數(shù)據(jù)分成兩組，一組比 k小，放入數(shù)組的前一半；一組比 k大，放入數(shù)組的后一半；將 k放入中間位置。 mid = divide(a, low, high)。如果 high的值大于 k， high減 1，繼續(xù)往前檢查，直到遇到一個小于 k的值。將 k放入此位置。 a[high]=k) high。amp。 a[low] = k。如Finonacci數(shù)列的計算，第 i個 Fibonacci數(shù)是前兩個Fibonacci數(shù)之和。 《 程序設計 》 程序設計 126 貪婪法解法 ? 我們不斷使用可能的最大面值的硬幣 ? 如：美元的硬幣有 10和 25分的面值 (忽略流通頻率很低的 50分硬幣 )。 ? 否則，對于每個可能的值 i，我們可以獨立計算找 i分錢零錢和 Ki分錢需要的最小硬幣數(shù)。 ? 找出 2分錢和 61分錢分別需要 2和 4個硬幣，一共是六個硬幣。我們可以用兩個硬幣找出 31分零錢，用三個硬幣找出 32分零錢，一共是五個硬幣。 for (i=1。 } 《 程序設計 》 程序設計 130 上述解法分析 ? 此算法的效率很低 ? 事實上 63分錢找零的問題是不會在一個合理的時間內(nèi)解決的。因此，可把已有子問題的答案存放起來，當再次遇到此子問題時就不用重復計算了。 《 程序設計 》 程序設計 134 函數(shù)原型 ? Vo