清华大学出版社 TSINGHUA UNIVERSITY PRESS 例25对一个大于或等于3的正整数,判断 它是不是一个素数。 概念:所谓素数,是指除了1和该数本身之外 不能被其它任何整数整除的数。例如,13是 素数。因为它不能被2,3,4,…,12整除。 分析:判断一个数n(n≥3)是否素数的方法 将n作为被除数,将2到(n-1)各个整数轮流作 为除数,如果都不能被整除,则n为素数。 16
16 例2.5 对一个大于或等于3的正整数，判断 它是不是一个素数。 概念：所谓素数，是指除了1和该数本身之外， 不能被其它任何整数整除的数。例如，13是 素数。因为它不能被2，3，4，…，12整除。 分析：判断一个数n(n≥3)是否素数的方法： 将n作为被除数，将2到(n-1)各个整数轮流作 为除数，如果都不能被整除，则n为素数
清华大学出版社 TSINGHUA UNIVERSITY PRESS 算法如下 S1:输入n的值 S2:i=2 (i作为除数) S3:n被除,得余数r S4:如果r=0,表示η能被除,则打印η不是 素数”,算法结束。否则执行S5 S5:1+1 I S6:如果i≤n-1,返回S3。否则打印n“是素数 。然后结束。 实际上,n不必被2到(n-1)的整数除,只需 被2到n/2间整数除,甚至只需被2到荔间的 整数除即可。 17
17 算法如下 ： S1：输入n S2：i=2 （i作为除数） S3：n被i除，得余数r S4：如果r=0，表示n能被i整除，则打印n“不是 素数”，算法结束。否则执行S5 S5：i+1 i S6：如果i≤n-1，返回S3。否则打印 n “是素数 ” 实际上，n不必被2到(n-1)的整数除，只需 被2到n/2间整数除，甚至只需被2到 之间的 整数除即可。 n
清华大学出版社 TSINGHUA UNIVERSITY PRESS §2.3算法的特性 个算法应该具有以下特点: 有穷性包含有限的操作步骤 ·确定性∶算法中的每一个步骤都应当是确 定的 有零个或多个输入:输入是指在执行算法 时需要从外界取得必要的信息 有一个或多个输出:算法的目的是为了求 解,“解”就是输出 有效性∴算法中的每一个步骤都应当能有 效地执行,并得到确定的结果 18
18 §2.3 算法的特性 • 有穷性：包含有限的操作步骤 • 确定性：算法中的每一个步骤都应当是确 定的 • 有零个或多个输入：输入是指在执行算法 时需要从外界取得必要的信息 • 有一个或多个输出：算法的目的是为了求 解，“解” 就是输出 • 有效性：算法中的每一个步骤都应当能有 效地执行，并得到确定的结果 。 一个算法应该具有以下特点：
清华大学出版社 TSINGHUA UNIVERSITY PRESS §2.4算法的表示 可以用不同的方法表示算法,常用的有 自然语言 传统流程图 结构化流程图 伪代码 PAD图 19
19 §2.4 算法的表示 可以用不同的方法表示算法，常用的有： –自然语言 –传统流程图 –结构化流程图 –伪代码 – PAD图
清华大学出版社 TSINGHUA UNIVERSITY PRESS §2.4.1用自然语言表示算法 自然语言就是人们日常使用的语言,可以 是汉语或英语或其它语言。用自然语言表 示通俗易懂,但文字冗长,容易出现“歧 义性”。自然语言表示的含义往往不大严 格,要根据上下文才能判断其正确含义 描述包含分支和循环的算法时也不很方便 。因此,除了那些很简单的问题外,一般 不用自然语言描述算法 20
20 §2.4.1 用自然语言表示算法 自然语言就是人们日常使用的语言，可以 是汉语或英语或其它语言。用自然语言表 示通俗易懂，但文字冗长，容易出现“歧 义性”。自然语言表示的含义往往不大严 格，要根据上下文才能判断其正确含义， 描述包含分支和循环的算法时也不很方便 。因此，除了那些很简单的问题外，一般 不用自然语言描述算法