acm程序设计教材教学稿件.ppt

ACM 程序设计;今天，;（1466）计算直线的交点数;初步分析:;思考2分钟:如何解决?;容易列举出N=1,2,3的情况： 0 0，1 0，2，3 如果已知N的情况，我们来分析加入第N条直线的情况(这里N=4)： 1、第四条与其余直线全部平行 = 无交点； 2、第四条与其中两条平行，交点数为(n-1)*1+0=3; 3、第四条与其中一条平行，这两条平行直线和另外两点直线的交点数为(n-2)*2=4,而另外两条直线既可能平行也可能相交，因此可能交点数为： （n-2）*2+0=4 或者 (n-2)*2+1=5 4、 第四条直线不与任何一条直线平行，交点数为： (n-3)*3+0=3 或者 (n-3)*3+2=5 或者 (n-3)*3+3=6 即n=4时，有0个，3个，4个，5个，6个不同交点数。;从上述n=4的分析过程中，我们发现： m条直线的交点方案数 =（m-r）条平行线与r条直线交叉的交点数 + r条直线本身的交点方案 =（m-r）*r+r条之间本身的交点方案数（1=r=m） ;一、数塔问题 ;用暴力的方法，可以吗？;Understand?;二、思考题：最长有序子序列;解决方案：;三、HDOJ_1160 FatMouses Speed ;题目分析：;Qestion:;思考（期末考试题）：;解题思路？;四、HDOJ_1159 Common Subsequence;请先计算暴力算法的时间复杂度：（当然是指最坏情况！）;;子结构特征： f(i,j)= { 由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有关, 而在计算f(i,j)时, 只要选择一个合适的顺序, 就可以保证这三项都已经计算出来了, 这样就可以计算出f(i,j). 这样一直推到f(len(a),len(b))就得到所要求的解了.;理论总结; 如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。 ;二、动态规划的基本步骤 ;（1）找出最优解的性质，并刻画其结构特征。 （2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。 其中（1）——（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。;三、动态规划问题的特征;思考：免费馅饼 ;如何解决？;Any Question?;附：课后作业;ACM, 天天见！