再上一篇:7 .2 .1 数组整体作参数
上一篇:7 .2 .2 void 类型的函数
主页
下一篇:8 .2 使用解析法设计算法
再下一篇:8 .3 排序算法
文章列表

第 8 章 常 用 算 法

《程序设计基础》(基于C语言讲解) 石光华 编著 —北京: 清华大学出版社

8 .1 使用穷举法设计算法

有一个问题:有一把锁和十把钥匙怎样才能找出所有开这把锁的钥匙?

1 .穷举法的概念

穷举法就是根据问题的性质,确定正确结果所在的范围;在该范围内采用循环的方式,列举出该问题所有可能的解(不能遗漏,也不能重复);并在逐一列举的过程中,检验每个可能的解是不是问题的真正解,若是,采用此解,否则抛弃它。

使用穷举算法的步骤如下。

(1) 确定正确结果所在的范围。

(2) 列举所有可能的解(不能遗漏,也不能重复)。

(3) 检验每个可能的解。通常采用循环进行穷举。

2 .穷举法的应用

【例8-1】 从1~100中找出所有能被7或9整除的数。用流程图描述解决此数学问题的算法。

试题分析 穷举的范围为1~100;可能的解是能被7或9 整除的数。解决该问题的算法如图8-1所示。

3 .最大公约数和最小公倍数算法

如果整数ifirst 能被iloop整除,则iloop是 ifirst 的约数,公约数是指两个整数共同的约数,其中最大的一个称为最大公约数。

由于最大公约数不会大于两个数中的较小数,所以只要引入一个变量iloop,让它从1开始一次增加1, 每次都检查iloop是否为ifirst 和isecond的公约数。如果是,则存入变 第8章 常用算法 109

图8-1 例8-1的算法

量itmp中。由于iloop是从小到大变化的,所以itmp中最后得到的数必定是两数的最大公约数。用流程图表示的算法如图8-2所示。

用穷举法求最大公约数的思路如下。

(1) 穷举的范围是从1到两个整数中的最小数;

(2) 可能的解是两个数分别除以iloop时都能整除,余数为0的那个iloop。

最小公倍数等于两个数的积除以最大公约数。

【例8-2】 编写两个函数,分别求出两个正整数的最大公约数和最小公倍数;在主函数中输入两个正整数,调用函数,并输出其最大公约数和最小公倍数。

#include < stdio .h>

int maxno(int ifirst,int isecond);

int minno(int ifirst,int isecond);

void main()

{

int ino1=0,ino2=0,imax=0,imin=0;

printf(″Please input twonumber:\n″);

scanf(″%d%d″,&ino1,&ino2);

imax=maxno(ino1,ino2);

imin=minno(ino1,ino2);

110 程序设计基础

图8-2 最大公约数算法

printf(″maxno is %d\n″,imax);

printf(″minno is %d\n″,imin);

}

/ *求最大公约数*/

int maxno(int ifirst,int isecond)

{

第8章 常用算法 111

int itmp=0,iloop=0;

if(ifirst>isecond)

{

itmp=ifirst;

ifirst=isecond;

isecond=itmp;

}

iloop=1;

while(iloop< =ifirst)

{

if (((ifirst % iloop) = =0) && ((isecond % iloop) = =0))

itmp=iloop;

iloop=iloop+1;

}

return itmp;

}

/ *求最小公倍数*/

int minno(int ifirst,int isecond)

{

int itmp=0;

itmp=ifirst*isecond/ maxno(ifirst,isecond);

return itmp;

}

4 .数字分解算法

对一个自然数 n,其个位上的数字可以通过对 n求10的余数得到;将 n与10 进行整除后,再求其与10的余数,则得到第2位的数字;反复这个过程直到 n<0即可得到全部的数字。其算法如图8-3所示,程序如下。

#include< stdio .h>

void main()

{

int ino=0, itmp=0;

scanf(″%d″,&ino);

112 程序设计基础

while(ino>0)

{

itmp=ino%10; / *取得个位的数字*/

printf(″%d\n″,itmp);

ino=ino/ 10; / *把数缩小10倍*/

图8-3 数字分解的算法

【例8-3】 输出所有“水仙花数”。所谓水仙花数,是指一个3位的十进制数,该数各

位数字的立方之和等于该数本身。例如,153是一个水仙花数,因为13 +53 +33 =153。

#include < stdio .h>

void main()

{

int ige=0,ishi=0,ibai=0,ino=0,itmp=0;

for(ino=100;ino<1000;ino=ino+1)

{

ige=ino%10;

ishi=(ino/ 10)%10;

ibai=(ino/ 100)%10;

第8章 常用算法 113

itmp=ige*ige*ige+ishi*ishi*ishi+ibai*ibai*ibai;

if(itmp = =ino)

printf(″no is %d,%d %d %d\n″,ino,ibai,ishi,ige);

}

}