算法入门系列之二 -- 筛选法
所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。1: 求1-100之间的质数
原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.
void fun1()
{
int i, j;
bool flag;
for ( i = 2; i < 100; i++ )
flag = true;
//下面开始划掉合数
for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
{
if ( flag == false )
continue; //既然i已经是合数，它的倍数应该已经被划掉
for ( j = 2; j * i < 100; j++ )//划掉i*j
flag = false;
}
//输出结果
for ( i = 2; i < 100; i++ )
if ( flag )
cout << i << ' ';
}
2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？
这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。
void fun2()
{
bool flag;//标记第i个人的状态，false已被毙掉,true还没被毙掉
for ( int i=0; i< 30; i++ )
flag = true;
int n = 30;//还剩几个人
int cnt;
int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
while ( n > 0 )
{
cnt = 0;
while ( cnt < 5 )
{
if ( ++pos == 30 )
pos = 0;
if ( flag )//此人还没被毙掉
cnt ++;
}
//退出时cnt == 5，pos指向报5的人
flag = false;//毙掉
n --;//剩余人数减1
}
//最后一个被毙的就是幸存者
//之所以加1是因为程序中从0开始计数，输出却以1开始计数
cout << pos + 1 << ' ';
}
3: 一个数被5除余3，被7除余2，求此数最小为几。
筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。
void fun3()
{
int a;//105 = 5 * 7
int i;
//计数清0
for ( i = 0; i < 35; i++ )
a = 0;
//开始筛选
for ( i = 3; i < 35; i += 5 )
a ++;
for ( i = 2; i < 35; i += 7 )
a ++;
for ( i = 0; i < 35; i++ )
if ( a == 3 )
{
cout << i << endl;
return;
}
//如果执行到这里说明无解
cout << "No Answer!" << endl;
}
总结：
筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
for ( int i = 0; i< n; i++ )
{
if ( i % 5 == 3 && i % 7 == 2 && ... )
cout << i;
}
但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的
页:
[1]