文档介绍：Lesson 8 计算机算法初步
学****目标:
3
1
掌握几个常用的解题算法:穷举、迭代
3
穷举法
2
概述
穷举法,又称为枚举法,是人们日常生活中常用的一种求解问题的方法。
根据问题中的部分条件(已知的条件)将所有可能解的情况列举出来,然后通过一一验证是否符合整个问题的求解要求,而得到问题的解。
3
穷举法
2
1、旅行途中发现自己忘记了***的密码,怎么办?
2、从某个班中找出所有班干部,需要逐一对每个同学进行查看,判断是否是班干部。
3
穷举法
2
穷举法的核心在于明确问题的所有可能性,并针对每种可能情况逐个进行判断,最终找出正确问题的答案。
穷举解题步骤:
1、问题解的可能搜索的范围:
用循环或循环嵌套结构实现
2、写出符合问题解的条件。
3
穷举法
2
所谓素数是指仅能被1和自身整除,且大于等于2的数值。如7,11,17,23等
例1:判断给定整数是否是素数。
3
穷举法
2
问题分析
为了检查一个整数是不是素数,可以采用穷举法。假设给定的整数用x表示,则判断过程就是确认x不能整除以2~x-1之间的任何整数。这就需要一一列举出2~x-1之间的每个整数进行排查。
算法描述
N
Y
开始
输入x
2 t
t < x
t 加1
x%t==0
结束
输出“不是素数”
输出“是素数”
Y
N
t == x
Y
N
#include <>
int 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 );
return 0;
}
注意判断是否是素数的条件与判断位置
如果要找一个范围内那些是素数怎么改写程序?
#include <>
int main( )
{
int i,x,y,t,j=0;
do{ printf( "Input numerical range(x,y,x<y):\n");
scanf("%d%d", &x,&y );
}while(x<2||y<3||x>y);
for(i=x;i<=y;i++)
{ for(t = 2; t<i; t++ ) /* 列举小于i大于1的所有整数*/
if ( i%t == 0 ) break;
if ( t == i ) /*是否通过循环条件出口*/
{ j++ ; printf( "%d%c", i,j%8==0?'\n':'\t' ); }
}
return 0;
}
每行输出8个数
3
穷举法
2
例2:百钱买百鸡
“百钱买百鸡”是我国古代数学家张丘建提出的一个著名的数学问题。假设某人有钱百枚,希望买一百只鸡;不同的鸡价格不同,公鸡5枚钱一只,母鸡3枚钱一只,而小鸡3只1枚钱。试问:如果用百枚钱买百只鸡,可以包含几只公鸡、几只母鸡和几只小鸡。