Algorithms Chapter 1 绪论.pptVIP

? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * * * * * * [英] [?s?d??ku:] [美] [?s?do?ku:] 生词本 * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * * 它首先拿A的中间分量A[m/2]与c比较，如果A[m/2]=c则解已找到。如果A[m/2]c，则c只可能在A[1],A[2],..,A[m/2-1]之中，因而下一步只要在A[1], A[2], .. ，A[m/2-1]中继续查找；如果A[m/2]c，则c只可能在A[m/2+1],A[m/2+2],..,A[m]之中，因而下一步只要在A[m/2+1],A[m/2+2],..,A[m]中继续查找。不管哪一种情形，都把下一步需要继续查找的范围缩小了一半。再拿这一半的子数组的中间分量与c比较，重复上述步骤。照此重复下去，总有一个时候，或者找到一个i使得A[i]=c，或者子数组为空（即子数组下界大于上界）。前一种情况找到了等于c的分量，后一种情况则找不到。 这个新算法因为有反复把供查找的数组分成两半，然后在其中一半继续查找的特征，我们称为二分查找算法。 ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * 1736年，数学家莱昂哈德·欧拉以柯尼斯堡的桥和岛屿为基础解决了柯尼斯堡七桥问题，并由此产生了新的数学分支——拓扑学和图论。 证明这种方法并不存在，也顺带解决了一笔画问题。 欧拉把实际的抽象问题简化为平面上的点与线组合，每一座桥视为一条线，桥所连接的地区视为点。这样若从某点出发后最后再回到这点，则这一点的线数必须是偶数。 第一次世界大战前的柯尼斯堡城堡 1857年， 哈密尔顿发明了一个游戏(Icosian Game).它是由一个木制的正十二面体构成，在它的每个棱角处标有当时很有名的城市。游戏目的是“环球旅行”。为了容易记住被旅游过的城市 ，在每个棱角上放上一个钉子，再用一根线绕在那些旅游过的城市上(钉子),由此可以获得旅程的直观表示。 ? School of Computer Science and Technology, SWUST * ? School of Computer Science and Technology, SWUST * * 算法的几个要点 算法的每一个步骤都必须清晰、明确。 算法所处理的输入的值域必须仔细定义。 同样的一个算法可以用几种不同的形式来描述。 可能存在几种解决相同问题的算法。 针对同一个问题的算法可能会基于完全不同的解题思路，而且解题的速度也会有明显区别。 * 算法问题求解基础 算法是问题的程序化解决方案。 * 理解问题 决定：计算方法； 精确和近似的解法； 数据结构； 算法设计技术； 设计算法 正确性证明 分析算法 根据算法写代码 算法问题求解基础 理解问题 设计算法前做的第一件事情 仔细阅读问题的描述 提出疑问 手工处理一些实例 考虑特殊情