第2单元控制结构 24伪代码 前面介绍了利用流程图实现自顶向下的程序设计方法。实际上,在使用C++的程序员们 中还流行着一种利用伪代码进行自顶向下程序设计的方法。伪代码使用C++的几种控制语 句和自然语言结合起来描述算法,比画流程图省时省力,且更容易转化为程序。 例2-2编出“验证”哥德巴赫猜想的程序 算法:对图29中的各程序模块作进一步的分解。这一次采用伪代码表示程序求精 分解的结果。“验证”哥德巴赫猜想首先要解决如何生成和测试素数的问题。素数即质数,即 除了1和自身之外没有其他因子的正整数。大多数素数都不能简单地根据某个数学表达式计 算出来,只能通过逐个检验正整数是否符合素数的定义的方法得出。因此,可以先编写一个 生成素数表的函数,用其生成给定范围内所有的素数并存放在一个素数表中,这样“求一个 素数”或检查一个数是否素数的工作就可以转化为对素数表的查询了 我们使用“筛法”来生成素数表,这是生成素数最古老,同时也是最有效的方法,由古 希腊的哲学家兼数学家埃拉托色尼提出。因为准备验证的最大偶数小于M,所以用到的最大 素数也不会超过M。因此,列出0到M之间的所有自然数 0,1,2,3,4,5,6,7,8,…,M- 然后将所有2的倍数,3的倍数,5的倍数,…,直到M2的倍数均从表中删去(置换为0) 即可。 我们用数组 Primelist存放生成的素数。按上法生成的素数表有一个特点,即如果 Primelist[x]≠0,则x为素数,否则x为合数这样,就可以很方便地根据该素数生成素数,或 者判别一个数是否素数了。我们将生成素数表的工作编成一个函数,其原型为 void CreatePrimeList(int PrimeList[) 用伪代码描述生成素数表的算法如下 将 PrimeList的各元素设置为2到M-1之间的自然数 分别从表中去掉已经确定的各素数的倍数(将其置换为0); 第1步可以用一个for型的循环实现 for(i=0: i<M: i=i+1) Primelist[i] =i 第2步稍微复杂些。我们使用工作变量i指示出最后确定的素数的位置,在表中将数组 元素 Prelist[的倍数转换为0: while(i<M/2) for (j=i+l: j<M; j=j+1) if( PrimeList [j]≠0且是 Primelist[i]的倍数)第 2 单元 控制结构 - 25 - 2.4 伪代码 前面介绍了利用流程图实现自顶向下的程序设计方法。实际上, 在使用Ｃ++的程序员们 中还流行着一种利用伪代码进行自顶向下程序设计的方法。伪代码使用Ｃ++的几种控制语 句和自然语言结合起来描述算法, 比画流程图省时省力, 且更容易转化为程序。 [例 2-2] 编出“验证”哥德巴赫猜想的程序。 算 法：对图 2-9 中的各程序模块作进一步的分解。这一次采用伪代码表示程序求精 分解的结果。“验证”哥德巴赫猜想首先要解决如何生成和测试素数的问题。素数即质数, 即 除了 1 和自身之外没有其他因子的正整数。大多数素数都不能简单地根据某个数学表达式计 算出来, 只能通过逐个检验正整数是否符合素数的定义的方法得出。因此，可以先编写一个 生成素数表的函数, 用其生成给定范围内所有的素数并存放在一个素数表中, 这样“求一个 素数”或检查一个数是否素数的工作就可以转化为对素数表的查询了。 我们使用“筛法”来生成素数表, 这是生成素数最古老, 同时也是最有效的方法, 由古 希腊的哲学家兼数学家埃拉托色尼提出。因为准备验证的最大偶数小于 M, 所以用到的最大 素数也不会超过 M。因此, 列出 0 到 M 之间的所有自然数: 0, 1, 2, 3, 4, 5, 6, 7, 8, ..., M−1 然后将所有 2 的倍数, 3 的倍数, 5 的倍数, ..., 直到 M/2 的倍数均从表中删去 ( 置换为 0 ) 即可。 我们用数组 PrimeList 存放生成的素数。按上法生成的素数表有一个特点, 即如果 PrimeList[x]≠0, 则 x 为素数, 否则 x 为合数。这样，就可以很方便地根据该素数生成素数, 或 者判别一个数是否素数了。我们将生成素数表的工作编成一个函数, 其原型为: void CreatePrimeList(int PrimeList[]); 用伪代码描述生成素数表的算法如下: 将 PrimeList 的各元素设置为 2 到 M-1 之间的自然数; 分别从表中去掉已经确定的各素数的倍数 ( 将其置换为 0 ) ; 第 1 步可以用一个 for 型的循环实现: for(i=0; i<M; i=i+1) PrimeList[i] = i; 第 2 步稍微复杂些。我们使用工作变量 i 指示出最后确定的素数的位置, 在表中将数组 元素 PrimeList[i]的倍数转换为 0: i = 2; while(i<M/2) { for(j=i+1; j<M; j=j+1) if(PrimeList[j]≠0 且是 PrimeList[i]的倍数)