算法設計與分析：緒論

算法設計與分析什么是算法什么是算法什么是算法算法與程序輸入：有零個或多個外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。算法是解決問題的方法或過程，嚴格地講是滿足下述性質(zhì)的指令序列。程序是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的性質(zhì)(4)即有限性。

算法初體驗—

計數(shù)判斷一個byte里面有多少個bit的值為1？intCal(intiValue){while(iValue!=0){iReminder=iValue%2;if(iReminder==1)iCount++;iValue=iValue/2;

}returniCount;}如果這個子函數(shù)需要調(diào)用很多次，內(nèi)存空間足夠，怎樣提高性能？如果既想省時間，又想省空間，怎樣改進？intiTables[256]={…};iCount=iTables[iValue];HashMapMaps;If(Maps.containsKey(Value)){Count=Maps.get(Value)}else{Maps.put(Value,newInteger(Cal(iValue)))}時間和空間-算法的標桿！算法初體驗—

最大和連續(xù)子數(shù)列問題描述:

給定一個整數(shù)數(shù)列{A1,A2,…,An}，求Ai+Ai+1+…+Aj-1+Aj的最大值，并確定對應的子序列。如果所有的整數(shù)都是負數(shù)，那么最大連續(xù)子數(shù)列和為0。例如:{1,

-3,4,5}的最大子數(shù)列為{4,5}，因為4+5最大；{3,4,-5,8,-4}的最大子數(shù)列為{3,4,-5,8}，因為3+4-5+8最大為10；{4,3,-1,2}的最大子數(shù)列為{4,3,-1,2}，因為4+3-1+2最大為8。算法-1intmaxSubSum1(constvector<int>&a){intmaxSum=0;

for(inti=0;i<a.size();i++)

for(intj=i;j<a.size();j++){intthisSum=0;

for(intk=i;k<=j;k++)thisSum+=a[k];

if(thisSum>maxSum)maxSum=thisSum;} returnmaxSum;}算法-2intmaxSubSum2(constvector<int>&a){intmaxSum=0;

for(inti=0;i<a.size();i++){intthisSum=0;

for(intj=i;j<a.size();j++){thisSum+=a[j];

if(thisSum>maxSum)maxSum=thisSum;}}

returnmaxSum;}算法-3intmaxSubSum4(constvector<int>&a){intmaxSum=0,thisSum=0;

for(intj=0;j<a.size();j++){thisSum+=a[j];if(thisSum>maxSum)maxSum=thisSum;elseif(thisSum<0)thisSum=0;}returnmaxSum;}算法-4intmaxSumRec(constvector<int>&a,intleft,intright){if(left==right)//Basecaseif(a[left]>0)returna[left];elsereturn0;

intcenter=(left+right)/2;

intmaxLeftSum=maxSumRec(a,left,center); intmaxRightSum=maxSumRec(a,center+1,right);

intmaxLeftBorderSum=0,leftBorderSum=0; for(inti=center;i>=left;i--) { leftBorderSum+=a[i]; if(leftBorderSum>maxLeftBorderSum) maxLeftBorderSum=leftBorderSum; }

intmaxRightBorderSum=0,rightBorderSum=0; for(intj=center+1;j<=right;j++) { rightBorderSum+=a[j]; if(rightBorderSum>maxRightBorderSum) maxRightBorderSum=rightBorderSum; }

return__max(__max(maxLeftSum,maxRightSum), maxLeftBorderSum+maxRightBorderSum);//3者最大}演示程序??！算法并不神奇─枚舉算法并不神奇─遞歸小孩子大都知道并復述過著名的“老和尚講故事”：“從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的故事是：從前有個廟，廟里有個老和尚，老和尚給小和尚講故事,講的什么故事呢？故事是……”Void

Story()

{

printf(“從前有個廟，廟里有個老和尚，老和尚給小和尚講故事，\r\n”)；

printf(“講的什么故事呢？故事是：\r\n”)；

Story();

}算法并不神奇─遞歸算法并不神奇─分治策略算法并不神奇─貪心策略從西直門到所有站的最快乘車路線找零錢策略算法并不神奇─回溯技巧國際象棋大師卡斯帕羅夫與電腦的人機大戰(zhàn)迷宮游戲為什么要學算法算法是軟件的靈魂，是計算機科學各個研究領(lǐng)域的核心算法+數(shù)據(jù)結(jié)構(gòu)=軟件計算機視覺：人臉識別、圖像壓縮數(shù)據(jù)挖掘：商品推薦、web搜索信息安全：RSA加密算法、入侵檢測計算機圖形學：動畫生成、3D渲染數(shù)據(jù)庫：索引、排序……為什么要學算法算法是軟件的靈魂，是計算機科學各個研究領(lǐng)域的核心算法是諸多前沿信息技術(shù)的核心角色，計算思維是信息時代的最重要思維方式之一"EveryoneknowsMoore'sLaw-apredictionmadein1965byIntelco-founderGordonMoorethatthedensityoftransistorsinintegratedcircuitswouldcontinuetodoubleevery1to2years...inmanyareas,performancegainsduetoimprovementsinalgorithmshavevastlyexceededeventhedramaticperformancegainsduetoincreasedprocessorspeed.“—ExcerptfromReprottothePresidentandCongress:DesigningaDigitalFuture,December2010(page71).為什么要學算法算法是軟件的靈魂，是計算機科學各個研究領(lǐng)域的核心算法是諸多前沿信息技術(shù)的核心角色，計算思維是信息時代的最重要思維方式之一“Apersonwell-trainedincomputerscienceknowshowtodealwithalgorithms:howtoconstruct

them,manipulatethem,understandthem,analyzethem.Thisknowledgeispreparationformuchmorethanwritinggoodcomputerprograms:itisageneral-purposementaltoolthatwillbeadefiniteaidtotheunderstandingofothersubjects,whethertheybechemistry,linguistics,ormusic,etc.Thereasonforthismaybeunderstoodinthefollowingway:Ithasoftenbeensaidthatapersondoesnotreallyunderstandsomethinguntilafterteachingittosomeoneelse.Actually,apersondoesnotreallyunderstandsomethinguntilafterteachingittoacomputer,i.e.,expressingitasanalgorithm...Anattempttoformalizethingsasalgorithmsleadstoamuchdeeperunderstandingthanifwesimplytrytocomprehendthingsinthetraditionalway.”

—

DonaldKnuth“Algorithms:acommonlanguagefornature,human,andcomputer.”

—AviWigderson為什么要學算法算法是軟件的靈魂，是計算機科學各個研究領(lǐng)域的核心算法是諸多前沿信息技術(shù)的核心角色，計算思維是信息時代的最重要思維方式之一

薛定諤方程：傅立葉變換：20世紀之前科學研究：基于數(shù)學公式21世紀的科學研究：基于計算機算法為什么要學算法算法是軟件的靈魂，是計算機科學各個研究領(lǐng)域的核心內(nèi)容算法是諸多前沿信息技術(shù)的核心角色，計算思維是信息時代的最重要思維方式之一算法是IT頂級公司面試考核的重要內(nèi)容題目1：今有30根火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取一根或兩根，最后取完者為勝。假設對手先取，你是否有必勝的策略？如果有，請告知獲勝策略；否則，請說明理由。題目2：有15瓶藥水，其中一瓶有毒。一只小白鼠喝下藥水以后是否中毒的癥狀在1個小時的時候才能被檢測出來。如果你有4只小白鼠，是否有辦法用一個小時的時間檢測出有毒的藥水？課程安排緒論算法復雜性枚舉策略遞歸與分治動態(tài)規(guī)劃貪心算法搜索技術(shù)考試安排形式：開卷分數(shù)構(gòu)成：出勤（10）課堂作業(yè)(30)期末考試成績(60)學習資源MOOCs資源Stanford“DesignandAnalysisofAlgorithms”Part1&2onCourseraPrinceton“Algorithms”Part1&2onCoursera(Opening)MIT“IntroductionofAlgorithms”臺灣師范大