数据结构与算法分析c++版课件_2.pdf
数据结构与算法分析数据结构与算法分析数据结构与算法分析数据结构与算法分析数据结构与算法分析数据结构与算法分析数据结构与算法分析数据结构与算法分析A Practical Introduction toData Structures and Algorithm Analysis2 Mathematical Preliminaries2 Mathematical PreliminariesSet concepts and notationLogarithmsLogarithmsSummations and RecurrencesRecursionM thtil Pf Th iMathematical Proof TechniquesEstimation2Sets and RelationsSets and Relations?Set:A collection of distinguishable members or elements.2,3,5 xP?Bag:A collection of elements with no order(like a set),but with duplicate-valued elements.3,4,5,4?Sequence:A collection of elements with an order,and which may contain duplicate-valued elements.3 4 5 4?A relation R over set S is a set of ordered pairs from S S.?Ex:if S is a,b,c,then,is a relation.Sets and RelationsSets and Relations?If tuple is in relation R,we may use the infix notation xRy.D fithtifl tif llith R?Define the properties of relations as follows,with R a binary relation over set S.?R is reflexive if aRa for all a S?R is reflexive if aRa for all a S.?R is symmetric if whenever aRb,then bRa,for all a,b S.?R is antisymmetric if whenever aRb and bRa,then a=b,for all a,b S.?R is transitive if whenever aRb and bRc,then aRc,for all a,b,c SS.antisymmetric 2Fib(1)=Fib(2)=1A Closed-Form SolutionA Closed Form Solution?The recurrence?T(n)=T(n 1)+1 for n 1?T(0)=T(1)=0?Replace the recurrence relation with a closed-?Replace the recurrence relation with a closedform solution?T(n)=T(n 1)+1?T(n)T(n 1)+1=(T(n 2)+1)+1=T(n 2)+2=T(n 2)+2?T(n)=T(n (n 1)+(n 1)=T(1)+n 1=T(1)+n 1=n-1RiRecursionAlithiiif itll itlf td?An algorithm is recursive if it calls itself to do part of its work.?the base case?the recursive partp?The factorial of n.long fact(int n)/Compute n!recursivelyg()py/To fit n!into a long variable,we require n=0)&(n=12),Input out of range);if(n 1return n fact(n-1);/Recursive call for n 1RecursionRecursionint Factorial(int n)参数0Factorial(0)1int Factorial(int n)参数11*Factorial(0)()1if(n=0)return 1;参数22*Factorial(1)参数11 Factorial(0)12return 1;elsereturn n*参数33*Factorial(2)参数()6return n Factorial(n-1);参数44*Fti l(3)参数33 Factorial(2)624主程序参数44*Factorial(3)24主程序汉诺塔问题ABCABC以C柱为中转，将盘从A柱移动到B柱上，一次以 柱为中转将盘从 柱移动到 柱次只能移动一个盘，而且大盘不能压在小盘上面汉诺塔问题ABC将 n 个盘子从 a 柱移动到b柱，用c柱做中转,可以分以下3步实现可以分以下3步实现：1)先将n-1个盘子，以b为中转，从a柱移动到c柱，2)将个盘子从 移动到b2)将一个盘子从a移动到b3)将c柱上的n-1个盘子，以a为中转，移动到b柱终止条件？终止条件？n=1时，直接移动盘子即可，不用递归#il dit汉诺塔问题#include using namespace std;/将 n 个盘子从 a 柱移动到b柱，用c柱做中转/将 n 个盘子从 a 柱移动到b柱，用c柱做中转void Hanoi(int n,char a,char b,char c)if(n=1)cout a b endl;treturn;/先将n-1个盘子，以b为中转，从a柱移动到c柱，/先将n 1个盘子，以b为中转，从a柱移动到c柱，Hanoi(n-1,a,c,b);/将一个盘子从a移动到bcout a b Q?Proof by Contradictiony?First assume that the theorem is false,then find a logical contradiction stemming from this assumption.?Proof by Mathematical InductionProof by ContradictionProof by ContradictionExample There is no largest integer.Proof:Proof by contradiction.yStep 1.Contrary assumption:Assume that there is a largest integer.Call it B(for“biggest”).largest integer.Call it B(for biggest).Step 2.Show this assumption leads to a contradiction:Consider C=B+1 C is an integercontradiction:Consider C B 1.C is an integer because it is the sum of two integers.Also,C B,which means that B is not the largest integer after ggall.Thus,we have reached a contradiction.Proof by Mathematical InductionProof by Mathematical Induction?Solving a problem by building up from simple subproblemssubproblems.?mathematical induction is a method to test a hypothesis.?seeking a closed-form solution for a summation or recurrence.?Thrm is true for any value of parameter n(for n c?Thrm is true for any value of parameter n(for n c,where c is some constant)if the following two conditions are true:?Base Case:Thrm holds for n=c,and?Base Case:Thrm holds for n c,and?Induction Step:If Thrm holds for n-1,then Thrm holds for n.Proof by Mathematical InductionProof by Mathematical Induction?Induction hypothesis:We can take advantage of the assumption that Thrm holds for all?We can take advantage of the assumption that Thrm holds for all values less than n as a tool to help us prove that Thrm holds for n.?Example:Call the sum of the first n positive integers S(n)=n(n+1)/2.ProofProof?Check the base case.For n=1,verify that S(1)=1(1+1)/2=1.The formula is correct for the base case.?State the induction hypothesis.The induction hypothesis iss(n 1)=(n 1)(n 1+1)/2=(n 1)n/2s(n-1)=(n-1)(n-1+1)/2=(n-1)n/2?Use the assumption from the induction hypothesis for n-1 toshow that the result is true for n.s(n)=s(n-1)+n=(n-1)n/2+n=n(n+1)/2Estimation TechniquesEstimation TechniquesK“bkf th?Known as“back of the envelope”or“back of the napkin”calculation?How many library bookcases does it take to store booksp?Determine the major parameters that effect the problemtake to store books totaling one million pages?problem.?Derive an equation that relates the parameters to Estimate:?Pages/inchthe problem.?Select values for the parameters,and apply?Pages/inch?Feet/shelf?Shelves/bookcaseparameters,and apply the equation to yield and estimated solution.262 Mathematical Preliminaries2 Mathematical PreliminariesSet concepts and notationLogarithmsLogarithmsSummations and RecurrencesRecursionM thtil Pf Th iMathematical Proof TechniquesEstimation27
