当前位置：文档之家 › 算法分析与设计

算法分析与设计

  • 格式：ppt
  • 大小：801.00 KB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

算法分析与设计教案

算法分析与设计教案

算法分析与设计课程教案课程编号：50c24037-01总学时：51 周学时：4适用年级专业（学科类）：2007级计科专业开课时间：2010－2011 学年第1 学期使用教材：王晓东编著计算机算法设计与分析第3版章节第1章1.1~ 1.2 第2 章2.1 课时 2教学目的理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；理解递归的概念。

教学重点及突出方法重点：程序与算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。

通过讲解、举例方法。

教学难点及突破方法难点：算法复杂性与递归通过讲解、举例、提问与引导方法。

相关内容此部分内容基础知识可参考清华大学出版社出版严蔚敏编著的《数据结构》教学过程（教师授课思路、设问及讲解要点）回顾数据结构课程中的算法概念、排序算法等知识，从而引出本课程内容。

提问算法与程序的区别、联系以及算法具有的特性。

讲解算法的复杂性，主要包括时间复杂性与空间复杂性。

讲解最坏情况、最好情况与平均情况的时间复杂性。

讲解算法复杂性在渐近意义下的阶，主要包括O、Ω、θ与o，并通过具体例子说明。

通过具体例子说明递归技术。

主要包括阶乘函数、Fibonacci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题等。

第页章节第2 章2.2~2.5 课时 2 教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，掌握计算算法复杂性方法。

教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。

通过讲解、举例方法。

教学难点及突破方法难点：计算算法复杂性。

通过讲解、举例、提问与引导方法。

相关内容素材教（教师授课思路、设问及讲解要点）学过程通过生活中解决复杂问题的分解方法，引出分治方法。

讲解分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。

通过具体例子采用分治思想来设计有效算法。

算法分析与设计

算法分析与设计
他把1,2,3,...16 这16个数字填写在4 x 4的方格中。 16 ? ? 13 ? ? 11 ? 9??* ? 15 ? 1
表中有些数字已经显露出来，还有些用?和*代替。 请你计算出? 和 * 所代表的数字。并把 * 所代表的数字作为本题答 案提交。
素数环问题
素数环是一个计算机程序问题，指的是将从1到n这n个整数围成一 个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环 就成为素数环。现在要求输入一个n，求n个数围成一圈有多少种素数 环，规定第一个数字是1。 143256 165234
例如当n=5，m=4时，面值为1，3，11，15，32的5种邮票可以贴 出邮资的最大连续区间是1到70。
➢ 通用的解题法 ➢ 核心在于构造解空间树：
➢ 子集树 ➢ 排列树 ➢ 回溯法是优化的暴力搜索： ➢ 不满足限制条件； ➢ 当前解与最优解进行预计算； ➢ 学习回溯法：心中有树
回溯法
总结
➢ 动态规划适合两个连续步骤之间有联系的问题； ➢ 回溯法几乎适用于所有的问题，但问题之间最好有明确的层次。
总结
➢ 构造心中的解空间树是关键； ➢ 回溯法与函数的局部变量； ➢ 访问解空间树的优化处理；
迷宫问题中的回溯法
➢ 四邻域 ➢ 八邻域
图论问题
无向图： ➢ 连通 ➢ 不连通
有向图： ➢ 弱连通 ➢ 单向连通 ➢ 强连通
最大团问题
连通子图（分支）
最大团问题
给定无向图G=(V,E)，如果UV，且对任意的u,vU， 都有(u,v)E，则称U是G的完全子图。G的完全子图U是G 的一个团当且仅当U不包含在G的更大的完全子图中。G中 的最大团是指G中所含顶点数最多的团。
yes no yes
➢ 通用的解题法 ➢ 核心在于构造解空间树：

算法分析与设计教案

算法分析与设计教案

算法分析与设计教案教案一：算法复杂度与算法分析一、教学目标：1.理解算法复杂度的概念2.掌握算法复杂度的计算方法3.能够通过算法复杂度分析算法的效率4.学会如何选择适合的算法二、教学内容：1.算法复杂度概述a.时间复杂度和空间复杂度的概念b.算法的执行时间和占用空间的计算方法c.算法的最好情况、平均情况和最坏情况的概念和关系2.算法复杂度分析a.常见的算法复杂度i.常数阶ii. 对数阶iii. 线性阶iv. 线性对数阶v.平方阶b.算法复杂度的表示方法和计算示例3.算法效率的比较与选择a.算法效率的评价标准b.如何选择适合的算法c.通过实际例子对比算法效率三、教学方法：1.讲授理论知识，介绍算法复杂度的概念和计算方法2.针对具体算法实例，进行算法复杂度的分析和计算3.进行实际例子的比较，分析不同算法的效率四、教学过程：教师活动学生活动教学方法时间引入介绍本节课的内容和目标倾听并记录讲授 5分钟讲解介绍算法复杂度概念和分类倾听并记录讲授 15分钟示例分析通过具体例子分析和计算算法复杂度思考并记录讲授和讨论20分钟案例分析分析不同算法的效率，并选择合适的算法思考并讨论讲授和讨论20分钟总结总结本节课的内容和要点倾听并记录讲授 5分钟五、教学资源：1.PPT课件2.计算器3.教材和参考书籍六、教学评估：通过学生的课堂参与情况、小组讨论和问题回答情况来评估学生对算法复杂度与算法分析的掌握情况。

七、教学延伸：1.可邀请相关行业的专业人士进行讲座，分享在实际工程中使用算法复杂度和算法分析的经验2.给学生布置一些算法的分析和设计任务，让学生通过实际动手操作来深入理解算法复杂度与算法分析的概念和方法。

教案二：动态规划的基本原理与应用一、教学目标：1.理解动态规划的基本原理和思想2.掌握动态规划的基本步骤和方法3.能够使用动态规划解决实际问题4.学会如何设计动态规划的算法二、教学内容：1.动态规划概述a.动态规划的定义和基本思想c.动态规划的基本步骤和方法2.动态规划的应用a.最优子结构的性质b.重叠子问题的性质c.通过子问题的解计算原问题的解d.动态规划的算法设计与实现3.动态规划的经典问题a.背包问题b.最长公共子序列问题c.最短路径问题d.斐波那契数列问题三、教学方法：1.讲授理论知识，介绍动态规划的基本原理和方法2.运用具体问题进行示例分析，演示动态规划的应用和算法设计3.进行实际问题的解决，让学生亲自动手设计动态规划算法四、教学过程：教师活动学生活动教学方法时间引入介绍本节课的内容和目标倾听并记录讲授 5分钟讲解介绍动态规划的概念和基本原理倾听并记录讲授 15分钟示例分析通过具体问题示例进行动态规划的分析和解决思考并记录讲授和演示 20分钟算法设计学生自主设计动态规划算法并进行实际问题的解决思考并动手实践讨论和指导25分钟总结总结本节课的内容和要点倾听并记录讲授 5分钟五、教学资源：1.PPT课件2.教材和参考书籍3.计算器六、教学评估：通过学生的课堂参与情况、小组讨论和问题回答情况来评估学生对动态规划的理解和应用掌握情况。

算法分析与设计概论

算法分析与设计概论

9
How to Study Algorithm？
“Sometimes we have experiences, and sometimes not. Therefore, the better way is to learn more."
10
1.1 算法与程序
算法：是满足下述性质的指令序列。
输 入：有零个或多个外部量作为算法的输入。 输 出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令清晰、无歧义。 有限性：算法中每条指令的执行次数有限，执行 每条指令的时间也有限。
1） 第一种解法：
输入：所购买的三种鸡的总数目n 输出：满足问题的解的数目k,公鸡,母鸡,小鸡的只数g[ ],m[ ],s[ ] 1. void chicken_question(int n,int &k,int g[ ],int m[ ],int s[ ]) 2. { int a,b,c; 4. k = 0; 5. for (a=0;a<=n;a++) 6. for (b=0;b<=n;b++) 7. for (c=0;c<=n;c++) { 8. if ((a+b+c==n)&&(5*a+3*b+c/3==n)&&(c%3==0)) { 9. g[k] = a; 10. m[k] = b; 11. s[k] = c; 12. k++; 13. }}}
矩阵。
数组 T：表示售货员的路线，依次存放旅行路线中的城 市编号。
售货员的每一条路线，对应于城市编号的一个排列。
n 个城市共有 n! 个排列，采用穷举法逐一计算每一条路线的费 用，从中找出费用最小的路线，便可求出问题的解。

电大计算机本科_算法设计与分析

电大计算机本科_算法设计与分析

电大计算机本科_算法设计与分析
算法设计与分析是计算机科学和数学领域的重要课程。

它涉及到一系
列算法设计、分析和实现的方面，涉及到算法流程、语法、数据结构等多
方面。

在算法设计与分析这门课程中，学生首先要学习怎么设计一个算法，
怎么从实际问题中提取算法，怎么分析算法复杂度，怎么评价算法效率。

接下来要学习算法，基本排序算法和选择算法，分治算法，贪婪算法，动
态规划，回溯算法，朴素贝叶斯，马尔科夫链等等各种算法。

学生还要熟
悉现代算法建模工具（如Matlab、SAS、C++），熟悉算法的优化技巧，
掌握算法的编码实现方法，并研究其实际应用。

本课程可以使学生充分发挥自己的能力，培养学生的算法设计能力，
提高实践能力，掌握算法的基本原理及运用，把握算法分析及其优化技术。

它不仅帮助学生提高数学思维能力，同时也有助于他们在计算机编程方面
的能力。

学习算法设计与分析有助于学生全面掌握算法设计这一重要组成
部分，也可以拓展学生的应用领域，使学生更具有竞争力。

学习算法设计与分析也有其困难之处，首先是算法编程比较抽象，学
生需要有较强的理论功底和数学能力。

《算法分析与设计》说课

《算法分析与设计》说课

8
8
8
10
S4
贪心算法
6
6
S5
回溯法
6
8
S6
分支限界
6
8
S7
随机化算法 总学时数
4 40
6 48
说课程教学大纲
5、课外学习内容 分支 限界 算法 设计 分治 分治 最强大脑—数独 阶乘 递归 兔子问题 会场安排问题 国王分财产
银行最优服务次序
回溯 法 贪心 贪心 算法 算法
矩阵连乘 租用游艇 排序问题
•难点模块
分治策略
动态规划 贪心算法
•难点内容
分治策略的应用
分解最优解结构 构造递归关系
回溯法
分支限界法
判断是否满足贪心性质
回溯法--剪枝函数 解空间树
说课导航
说课程教学大纲
说教学资源 说教学方法与手段 说学情与学法指导 说教学过程设计
说考核评价
说教学资源
1、教材选用原则
国家级规划教材 原则
具有先进性、适用性、时效性
汽车加油行驶 网球循环赛比赛日程
动态 规划
充分体现案例驱动、实践导向的设计思想
说课程教学大纲
6、课程重点
•重点模块
递归与分治策略
动态规划算法 贪心算法
•重点内容
二分搜索与排序
矩阵连乘 最长公共子序列
回溯法
分支限界法
最大字段和
0-
说课程教学大纲
7、课程难点
经典教材
说教学资源
王晓东教授编著的 《计算机算法设计与分析》 （C++描述）
说教学资源
2、网络资源
课外学习网站：
/JudgeOnline/problemtypelist.php

算法分析与设计.pdf

单选题1.若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是()。

A.快速排序B.堆排序C.归并排序D.直接插入排序答案:C2.下面命名规则中，哪项不是现在比较常用的命名规则()。

A.匈牙利命名法B.骆驼命名法C.下划线命名法D.图灵命名法答案:D3.十进制的123，1的位权是（）。

A.1B.2C.10D.100答案:D4.一个良好算法的基本单元是：顺序结构、循环结构和()。

A.线性结构B.离散结构C.数据结构D.选择结构答案:D5.遗传算法用于解决()。

A.排序问题B.规划问题C.最优化问题D.决策问题答案:C6.下列叙述中正确的是（）A.数据的逻辑结构与存储结构必定是一一对应的B.由于计算机在存储空间上是向量式的存储结构，因此，利用数组只能处理线性结构C.程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构D.以上说法都不对答案:D7.按F5开始调试，程序便会直接运行到断点处。

接下来可以逐行来运行程序，查看各个变量的值，也可以直接运行到下一个断点或程序结束，这样过程被称作()。

A.设置断点B.单步调试C.程序编译D.程序调试答案:B8.下列说法错误的是()A.使用高级计算机语言，如C、C++、Java，编写的程序，都需要经过编译器编译或解释，才能转化成机器能够识别并能执行的二进制代码。

B.如何一步步的跟踪代码，找到问题，搞明白为何程序不能正常运行，这个过程称为调试程序。

C.自动化的工具同样也能够帮助你跟踪程序，尤其当程序很复杂时效果更加明显，这种工具叫做调试器。

D.调试器并能解决程序中出现的问题。

答案:D9.注释从功能上可以分为文件注释、函数注释和()。

A.程序员注释B.功能注释C.时间注释D.版权注释答案:B10.二进制数1101.0101转换为十进制数是（）。

A.11.3225B.12.3125C.13.0125D.13.3125答案:D11.十六进制数C1B转换为二进制数是（）。

计算机算法的设计与分析

计算机算法的设计与分析计算机算法的设计和分析随着计算机技术的不断发展，算法成为了关键的核心技术之一。

算法的设计和分析是指通过一系列的步骤和方法来解决计算机问题的过程。

本文将详细介绍计算机算法的设计和分析。

一、算法设计的步骤：1. 理解和定义问题：首先需要明确所要解决的问题，并对其进行深入的理解，确定问题的输入和输出。

2. 分析问题：对问题进行分析，确定问题的规模、特点和约束条件，以及可能存在的问题解决思路和方法。

3. 设计算法：根据问题的性质和特点，选择合适的算法设计方法，从而得到解决问题的具体算法。

常见的算法设计方法包括贪心算法、分治算法、动态规划算法等。

4. 实现算法：将步骤3中设计的算法转化为计算机程序，并确保程序的正确性和可靠性。

5. 调试和测试算法：对实现的算法进行调试和测试，包括样本测试、边界测试、异常输入测试等，以验证算法的正确性和效率。

二、算法分析的步骤：1. 理解算法的效率：算法的效率是指算法解决问题所需的时间和空间资源。

理解算法的时间复杂度和空间复杂度是进行算法分析的基础。

2. 计算时间复杂度：时间复杂度用来表示算法解决问题所需的时间量级。

常用的时间复杂度包括常数时间O(1)、对数时间O(logn)、线性时间O(n)、平方时间O(n^2)等。

3. 计算空间复杂度：空间复杂度用来表示算法解决问题所需的空间资源量级。

常用的空间复杂度包括常数空间O(1)、线性空间O(n)、指数空间O(2^n)等。

4. 分析算法的最坏情况和平均情况：算法的最坏情况时间复杂度和平均情况时间复杂度是进行算法分析的关键指标。

最坏情况时间复杂度表示在最不利条件下算法所需的时间量级，平均情况时间复杂度表示在一般情况下算法所需的时间量级。

5. 比较算法的优劣：通过对不同算法的时间复杂度和空间复杂度进行分析，可以对算法的优劣进行比较，从而选择合适的算法。

三、常见的算法设计与分析方法：1. 贪心算法：贪心算法通过每一步的选择来寻求最优解，并且这些选择并不依赖于其他选择。

算法分析与设计


算法与数据结构
描述算法可以有多种方式
自然语言方式、表格方式、图示形式等 本书采用C++语言描述算法
算法与数据结构的关系
不了解施加于数据上的算法就无法决定如何构造 数据，可以说算法是数据结构的灵魂；
反之算法的结构和选择又常常在很大程度上依赖 于数据结构，数据结构则是算法的基础。
算法＋数据结构＝程序
无序表的数组占用的空间记在上层程序 的帐上.
例题2.3
实例特征：n，S(n)=0
Program Program 1.8 Add a[0:n-1]
例题2.4
实例特征:n ,递归栈需6 bytes S(n)=6(n+1)bytes
Program 1.9 Recursive code to add a[0:n-1]
例题2.2
实例特征：n，S(n)=0
Program 2.1 Sequential search
例题2.2(续)
T a[] 和T& x需2 bytes 指针(假定T为整 型)
形参 n 需2 bytes i 需2 bytes 以上均为实例特征独立的空间需求量
所以s(n)=0 注:上述分析是从程序调用的角度看,存放
Sartaj Sahni著，汪诗林等译，《数据结构、算法与应用--C++ 语言描述》，机械工业出版社，2003 （翻译版）
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms (the second edition)，The MIT Press，2001《算法导论（第二版）》（影印版，中文本），高 等教育出版社，2003

算法设计与分析

算法设计与分析算法是计算机科学中的核心概念，它是解决问题的一系列步骤和规则的有序集合。

在计算机科学的发展中，算法设计和分析扮演着至关重要的角色。

本文将探讨算法设计和分析的相关概念、技术和重要性。

一、算法设计的基本原则在设计算法时，需要遵循一些基本原则来确保其正确性和有效性：1. 正确性：算法设计应确保能够正确地解决给定的问题，即输出与预期结果一致。

2. 可读性：设计的算法应具有清晰的结构和逻辑，易于理解和维护。

3. 高效性：算法应尽可能地减少时间和空间复杂度，以提高执行效率。

4. 可扩展性：算法应具备良好的扩展性，能够适应问题规模的变化和增长。

5. 可靠性：设计的算法应具备稳定性和鲁棒性，对不同的输入都能给出正确的结果。

二、常见的算法设计技术1. 枚举法：按照规定的顺序逐个尝试所有可能的解，直到找到满足条件的解。

2. 递归法：通过将一个大问题分解成若干个小问题，并通过递归地解决小问题，最终解决整个问题。

3. 贪心算法：在每个阶段选择最优解，以期望通过一系列局部最优解达到全局最优解。

4. 分治算法：将一个大问题划分成多个相互独立的子问题，逐个解决子问题，并将解合并得到整体解。

5. 动态规划：通过将一个大问题分解成多个小问题，并存储已解决子问题的结果，避免重复计算。

三、算法分析的重要性算法分析可以评估算法的效率和性能。

通过算法分析，可以：1. 预测算法在不同规模问题上的表现，帮助选择合适的算法解决具体问题。

2. 比较不同算法在同一问题上的性能，从而选择最优的算法。

3. 评估算法在不同硬件环境和数据集上的表现，选择最适合的算法实现。

四、常见的算法分析方法1. 时间复杂度：衡量算法所需执行时间的增长率，常用的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)和O(n^2)等。

2. 空间复杂度：衡量算法所需占用存储空间的增长率，常用的空间复杂度有O(1)、O(n)和O(n^2)等。

3. 最坏情况分析：对算法在最不利情况下的性能进行分析，可以避免算法性能不稳定的问题。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例子：[伪定理] 所有马都只有一种颜色。
证明：任何一个马的集合都只有一种颜色
=>所有马只有一种颜色。
设H为任何一个马的集合，对H中马数量n归纳：
1)n=0，H
成立；n=1，显然成立。
2)设H中的马为h1, h2, … hn，由于任意n-1匹马的集合有唯
一的颜色，那么 H1
h2 h3 h4 … hn
即 第1个月买了1对兔子；第2个月仍只有1对；第3 个月有2对…
依此类推，如兔子不死亡，那么各月的兔子数由 Fibonacci序列给出：递归f0形式0; f11
fnfn1fn2, n2
序列以0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Fibonacci序列的算法：
Function Fibonacci(n)
确定性 清晰、无歧义 有限性 指令执行次数、时间
特点：
执行时，不能包含任何主观的决定； 不能有类似直觉/创造力等因素。
精品课件
5
例子：
人们日常生活中做菜的过程，可否用算法 描述？
✓ 如：“咸了”、“放点盐”、“再煮一会”。 ✓ 可否用计算机完成？
算法必须规定明确的量与时间； 不能含糊字眼。
通常，描述算法用类Pascal的结构化编程语言。
精品课件
8
算法的证明技巧
反证法(proof by contradication)/间接证明(indirect proof)：为了证明命题的正确性，转而证明该命题 的反命题能导致矛盾。
例子：
[欧几里德] 定理：存在无穷多个素数。
证明：假设P为有限素数集，那么显然 P 。
方格位置随意
瓷砖材料形状为
精品课件
14
归纳法证明举例-铺砖定理
证明：不妨假设 m 2n
。
1)当n=0时，显然成立；n=1时，也显然成立；
2) n1 m ， 2n
2n1，对2n1
大小的地板显然成立，现四分地板得到4个相同大小的
地板。
也变成存在特殊 方格地板地板
特殊方格地板
[证毕]
精品课件
15
归纳法证明举例-马的颜色
H2 h1
h3 h4 … hn
对两个集合应用归纳假设：
H1一种颜色 H2一种颜色
=>
H1和H2同种颜色
H具有同种颜色。？
精品课件
16
归纳法证明举例-马的颜色
n 0 n 1，
必须 n 3
正确 ，从2=>3，3=>4，…
不能1=>2。
精品课件
17
归纳法证明举例-斐波纳契序列
例子：[Fibonacci序列] 每个月一对繁殖期的兔子 会产生一对后代，而这对后代2个月后又会繁殖。
3
第一章 预备知识
学习要点:
理解算法的概念。 理解什么是程序，程序与算法的区别和内在联
系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C++语言描述算法的方法。
精品课件
4
什么是算法？
算法(algorithm)
一个（由人或机器进行）关于某种运算规则的集合
输入 规则 输出
Aho, Hopcroft, Ullman. 数据结构与算法（ 1983年影印本，清华出版社）
Thomas H. Cormen 等4人. 算法导论（MIT第2版 ）, 高教出版社影印本
潘金贵. 现代计算机常用数据结构和算法（南大 出版社），即Cormen等3人书第一版的翻译
精品课件
2
参考书目
简化
function DumpEuclid(P:整数集)
{P为非空有限素数集}
XP中最大的元素;
repeat XX+1 until X是素数;
return d
精品课件
13
算法的证明技巧
归纳法(induction)： 特殊=>一般法则。 例子：[铺砖定理] 铺砖问题总是有解的。
m×m个方格(m为2的幂)
d1; repeat dd+1 until d整除Y;
return d
通过上述证明d定为
素数且 dP
？
精品课件
12
派生出算法
function Newprime(P:整数集) 通过上述证明d定为
XP中所有元素的乘积; YX+1;
素数且 dP
d1;
repeat dd+1 until d整除Y;
return d
if n<2 then return n;
else retu精r品n课F件ibonacci(n-
18
如何选择算法？
当解决一个问题时，存在几种算法可供选择，如 何决定哪个最好？
两种研究方法：
经验(Empirical)：对各种算法编程，用不同实例实 验；
理论(Theoretical)：以数学化的方式确定算法所需 要资源数与实例大小之间函数关系。
精品课件
6
当然不是所有算法都要明确的选择，有些 概率算法进行选择。
“随机”<>“随意”
有些问题没有实用算法（求解精确解，需 要几百年）。
✓ 去寻找{规则集}
近似算法
启发式算法
可以预测误差， 且误差足够小
误差无法控制， 但可预计误差大小
在可接受的时间内可以算出足够好的近似解
精品课件
7
如何描述算法
算法分析与设计
陶军 CS dept. 李文正楼北203 Tel: 83790366 juntao@
精品课件
1
参考书目
Aho, Hopcroft, Ullman. The Design and Analysis of Computer Algorithms. （1974版 影印版，铁道出版社）
M. H. Alsuwaiyel. Algorithms: Design Techniques and Analysis（电子工业出版社影 印本，方世昌等译）
王晓东. 算法设计与分析.（电子工业出版社） Sara Baase等. 计算机算法：设计与分析导论（
第3版），高教出版社影印本。
精品课件
P 且有限， 将P中所有元素相乘，X表
示积
Y=X+1。
对Y分析：d为Y的一个最小的且大于1的约数。
精品课件
9
[欧几里德]证明
Y>1，且不要求d一定不等于Y， d一定存在。
d定为素数，否则存在一个约数z，使得z可整除Y
。
d为Y的一个最小的约数
又=>
矛z<盾d
d P
=>
，且X是P中所有元素的积
d是X
的约数
d0
即d可以同时整除X和Y=X+1。
对于
，否可则以Y 同m 时整除o d连 d续1整数
精品课件
10
[欧几里德]证明
矛盾
因此，P为无限集合。 [证毕]
下面衍生出找素数的一个算法：
Байду номын сангаас
精品课件
11
派生出算法
function Newprime(P:整数集)
{变量P为一非空有限的素数集} XP中所有元素的乘积; YX+1;