算法分析與設(shè)計PPT學(xué)習(xí)教案

1、會計學(xué)1 算法分析與設(shè)計算法分析與設(shè)計 南京郵電大學(xué)計算機學(xué)院 7/20/2021 教材： 陳慧南.算法設(shè)計與分析-C+語言描述 先修課： 面向?qū)ο蟪绦蛟O(shè)計語言C+，數(shù)據(jù)結(jié)構(gòu) 性質(zhì)： 計算機科學(xué)與技術(shù)中處于核心地位的一 門專業(yè)基礎(chǔ)課。 第1頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 目的：通過學(xué)習(xí)掌握算法設(shè)計的主要方法，并對算法的時、空復(fù)雜性有正確分析的能力，能夠針對具體的應(yīng)用問題選擇合適的數(shù)據(jù)結(jié)構(gòu)和設(shè)計結(jié)構(gòu)清晰、正確有效的算法，為獨立設(shè)計算法和對算法進行復(fù)雜性分析奠定堅實的理論基礎(chǔ)。 基本任務(wù): 介紹算法的基本概念、算法設(shè)計的基本策略和方法，同時介紹算法復(fù)雜性的概念、性能分析的

2、具體方法和技巧。 教學(xué)重點: 算法設(shè)計的基本思想和策略，以及算法性能分析的方法等。 第2頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第3頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 基本要求： 本章概述算法問題、求解方法等重要 概念和方法。掌握算法的基本概念，了解 使用計算機求解問題的過程和方法。 第4頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第5頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第6頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 算法Algorithm 第7頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 算

3、法+數(shù)據(jù)結(jié)構(gòu)=程序 第8頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第9頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 input)：算法有零個或多個輸入量； (output)：算法至少產(chǎn)生一個輸出量； (definiteness)：算法的每一條指令都有確切的定義，沒有二義性； (effectiveness)：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)； (finiteness)：算法必須總能在執(zhí)行有限步之后終止。 算法的五個特征: 第10頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第11頁/共48頁 南京郵電大學(xué)計算機學(xué)

4、院 7/20/2021 第12頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 gcd(24, 60) =gcd(60 mod 24, 24) =gcd(24 mod 12, 12)=12 反復(fù)執(zhí)行：gcd(m, n)=gcd(n mod m, m) 直到：n mod m=0 時的n =gcd(12, 24) =gcd(0, 12) 第13頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 歐幾里德遞歸算法 int RGcd(int m, int n) if(m=0) return n; return RGcd(n%m, m); int Gcd(int m, int n) if

5、(mn) Swap(m, n); / 保證mn return RGcd(m, n); 第14頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 歐幾里德迭代算法 int Gcd(int m, int n) if(m=0) return n; if(n=0) return m; if(mn) Swap(m, n); while(m0) int c=n%m; n=m; m=c; return n; gcd(m, n)=gcd(n mod m, m) 第15頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 gcd的連續(xù)整數(shù)檢測算法 最大公約數(shù)不會超過兩數(shù)中的較小者， 即不會超過t=mi

6、nm,n(確定初值) 執(zhí)行 while (m%t | n%t) t-; gcd(9, 27) , gcd(4, 6) 如t=4, (4%4|6%4)0 , t- t=3，(4%3|6%3)0 , t- t=2, (4%2|6%2)=0 , 故最大公約數(shù)為2 第16頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 Gcd的連續(xù)整數(shù)檢測算法 1、一個問題可以設(shè)計不同的算法； 如歐幾里德，連續(xù)整數(shù)檢測。 2、一個算法可以采用不同的形式； 如遞歸，迭代。 int Gcd(int m, int n) if (m=0) return n; if (n=0) return m; int t=mn?n

7、:m; / t=minm,n while (m%t | n%t) t-; return t; 第17頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第18頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 假設(shè)某一負(fù)責(zé)人交給你一個很難的任務(wù)，幾天后詢問你問題 解決了沒有？可能會發(fā)生如下圖這樣的情況： 問：“交給你的問題，解決方案設(shè)計出來了嗎？” 答：“我找不到一個有效的算法來解決它，沒能完成任務(wù)。 ” 第19頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 問：“交給你的問題，解決方案設(shè)計出來了嗎？” 答： “我找不到一個有效的算法來解決它，因為這樣的算 法是不存在的。

8、” 不過，要證明一個問題不 存在有效算法，往往跟尋 找有效算法一樣難。 第20頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 問：“交給你的問題，解決方案設(shè)計出來了嗎？” 答： “我找不到一個有效的算法來解決它，但不是我不行， 因為所有這些名人也都找不到解決它的有效算法。” 如果是你的話，你 愿意是哪種結(jié)果？ 第21頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第22頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第23頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第24頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第25頁/共48頁 南

9、京郵電大學(xué)計算機學(xué)院 7/20/2021 第26頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第27頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 理解問題 選擇求解方法 確定數(shù)據(jù)結(jié)構(gòu) 設(shè)計算法 正確性證明 分析算法 編寫代碼 第28頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第29頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 對于最優(yōu)化問題，一個算法如果致力于 尋找近似解而不是最優(yōu)解，被稱為 （approximation algorithm）。 如果在算法中需做出某些隨機選擇，則 稱為（randomized algorithm）。 第30頁/共

10、48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第31頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第32頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第33頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第34頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第35頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第36頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 斐波那契數(shù)列 1 nFFF 1, F0F 2n1nn 10 第37頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 當(dāng)一個算法采用遞歸方式定義時便成為。一個

11、遞歸算法是指直接或間接調(diào)用自身的算法。 求Fn long Fib( long n) if(n=1) return n; else return Fib(n-2)+Fib(n-1); 第38頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第39頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第40頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第41頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第42頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 第43頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 漢諾塔問題 enum tower

12、A=X, B=Y, C=Z; void Move(int n,tower x,tower y) /將第n個圓盤從塔座x移到塔座y的頂部 cout The disk n is moved from char(x) to top of tower char(y) endl; 第44頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/2021 void Hanoi(int n, tower x, tower y, tower z) /將x上部的n個圓盤移到y(tǒng)上，順序不變。 if (n) Hanoi(n-1, x, z, y); Move(n,x,y); Hanoi(n-1, z, y, x); 第45頁/共48頁 南京郵電大學(xué)計算機學(xué)院 7/20/