第3章计算机算法初步

程序代码#include <stdio.h> #include <math.h> main( ) { int a, b, c,t; printf( “Input a,b,c: ” ); scanf( “%d%d%d”, &a, &b, &c ); t = b*b – 4*a*c; if (t<0) printf( “No solution\n” ); else if ( t==0 ) printf( “X = %lf\n”, -b/(2.0*a) ); else { double t0; t0 = sqrt( (double)t ); printf( “X1 = %lf, X2= %lf\n”, (-b+t0)/(2*a), (-b-t0)/(2*a) ); } }

3.2 概述

穷举法

穷举法，又称为枚举法，是人们日常生活中常用的一种求解问题的方法。例如，从某个班中找出所有班干部，需要逐一对每个同学进行查看，判断是否是班干部。这种方法的基本思路就是一一列举每个

可能性，逐个进行排查。因此，穷举法的核心在于明确问题的所有可能性，并针对每种可能情况逐个进行判断，最终找出正确问题的答案。

穷举法应用实例1:素数的判断

所谓素数是指仅能被1和自身整除，且大于等于2的数值。判断一个给定的数值是否是素数是穷举法的典型实例。

例2:判断给定整数是否是素数。问题分析

为了检查一个整数是不是素数，可以采用穷举法。假设给定的整数用x表示，则判断过程就是确认x不能整除以2~x-1之间的任何整数。这就需要一一列举出2~x-1之间的每个整数进行排查。

算法描述开始

输入x

2 t

N t<x Y Y x%t==0 N t 加1 N t == x Y

输出“不是素数”

输出“是素数”

结束

程序代码#include <stdio.h> main( ) { int x, t; printf( “Enter an integer: ” ); scanf( “%d”, &x ); for (t = 2; t<x; t++ ) /* 列举小于x大于1的所有

整数 */ if ( x%t == 0 ) break; if ( t == x ) /* 是否通过循环条件出口 */ printf( “%d is prime\n”, x ); else printf( “%d isn’t prime\n”, x ); }

穷举法应用实例2:百钱买百鸡

“百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚，希望买一百只鸡；不同的鸡价格不同，公鸡5枚钱一只，母鸡3枚钱一只，而小鸡3只1枚钱。试问：如果用百枚钱买百只鸡，可以包含几只公鸡、几只母鸡和几只小鸡。

例3:百钱买百鸡。问题分析

从题目要求可知：公鸡、母鸡和小鸡的数量是有限的，都不会超过100。通过对不同数量的公鸡、母鸡和小鸡进行组合，可以计算出购买这些鸡所用的花费，但这个题目要求找出那些花费正好100枚且鸡的总数也为100只的情况。因此，可以采用穷举法，将不同的公鸡、母鸡和小鸡的数量枚举一遍，找出那些符合题目要求的解。

算法描述开始 0 x

N x <= 100/5 x 加1 Y 0 y

结束

N y <= 100/3 x Y 0 z y 加1

N z<=100 z 加1 Y 条件判断 Y N

输出 x, y, z

程序代码#include <stdio.h> #include <math.h> main( ) { int x, y, z;for( x=0; x<=100/5; x++ ) for( y=0; y<=100/3; y++ ) for( z=0; z<=100; z++ ) { if (x+y+z ==100 &&15*x+9*y+z==300) printf( “x=%d, y=%d, z=%d\n”, x, y, z ); } }

第3章计算机算法初步.doc 将本文的Word文档下载到电脑

下载这篇word文档

上一篇：离子色谱法测定深层地下水中的溴离子含量

下一篇：2013-2018年中国红外人体感应开关行业投资前景分析预测报告