数学建模社区-数学中国

标题: 算法入门系列之二 -- 筛选法 [打印本页]

---

作者: matrix_spaceman    时间: 2004-6-8 16:42
标题: 算法入门系列之二 -- 筛选法
所谓筛选法就是从全集中将不合格的项全部删去，剩下的就是答案。
% L, y3 s. t# W7 T. i$ F8 z, H
1: 求1-100之间的质数
- n1 O+ @% `. V
    原理：先将2的倍数全部划掉，再将3的倍数全部划掉……直到将10的倍数全部划掉（10^2 = 100 ）。剩下的就是质数.

6 E5 S' J- b. u$ ^- G1 w) Pvoid fun1()
' U# X; j# C; h{
    int i, j;
    bool flag[100];
, F) U$ f, ?/ |7 P3 v4 R  R' l
    for ( i = 2; i < 100; i++ )
        flag = true;

! T+ |  R: M. l    //下面开始划掉合数
5 n' c& k! q# `5 j& C    for ( i = 2; i < 10; i++ ) //因为合数的最小正因数不大于它的平方根
$ ]+ A0 m" G! Z1 S) O; r    {
        if ( flag == false )
            continue; //既然i已经是合数，它的倍数应该已经被划掉
        for ( j = 2; j * i < 100; j++ )//划掉i*j
            flag[i*j] = false;
$ i3 M" y! W/ O5 Q3 _  O3 f    }
$ j/ ?& Y' E% b% p( ?0 u/ r
    //输出结果
    for ( i = 2; i < 100; i++ )
        if ( flag )
$ Z8 k% G% f6 H) [1 l            cout << i << ' ';
}

2: 30个人站成一圈，从第一个人开始报数，凡报到5的拉出去毙了，剩下的人接着从1开始报，直到只剩一人放掉。想活命该站哪？

! D( H: i4 I8 J" E! M    这是个经典问题，解法就是模拟整个过程，有点类似于循环队列。
3 f3 [2 q& l  P; R. v: O
    另外，为了程序上处理方便，可以假定所有的人都拉去毙了，然后看一下最后一个被毙掉的是谁。另一处为了处理方便而采取的措施是pos的初始值设为-1.很多时候，对问题的问法稍作变动，或者将初始值、加减变量的位置稍作调整，用程序处理起来会方便很多。

" g% G7 Z$ e' I3 ~% I4 svoid fun2()
{
1 j& P# X$ Z4 ~" x% R6 [/ ^    bool flag[30];//标记第i个人的状态，false已被毙掉,true还没被毙掉

& T& p/ S- _' s9 m7 o  a+ x    for ( int i=0; i< 30; i++ )
        flag = true;
  d8 p2 o. @# w4 h' X
    int n = 30;//还剩几个人
+ _+ b9 e1 B2 H" n$ k    int cnt;
. ~; d4 r5 h  }; Y& w4 g( i% X( ~    int pos = -1;//初始值不一定从0开始，设为-1处理起来较方便
    while ( n > 0 )
    {
' }' n  u$ r1 v) q: J2 P        cnt = 0;
$ }+ D) K2 p/ w& ]$ t1 O        while ( cnt < 5 )
        {
            if ( ++pos == 30 )
  A! M: A9 q% K                pos = 0;
+ J4 @, \+ m0 g# G- y            if ( flag[pos] )//此人还没被毙掉
                cnt ++;
" r) F4 G% Z* x2 Z. S2 C; G* }6 S        }
$ P! @( J9 \" F: @( D" ~, i        //退出时cnt == 5，pos指向报5的人
& F; V$ E) f" I2 ^; ?, x        flag[pos] = false;//毙掉
        n --;//剩余人数减1
    }
    //最后一个被毙的就是幸存者
    //之所以加1是因为程序中从0开始计数，输出却以1开始计数
! n& V. t/ w+ l; O( U    cout << pos + 1 << ' ';
3 V0 a- z7 x) k6 _}
# E6 j2 x& u9 F# Q' R4 c1 B0 d
3: 一个数被5除余3，被7除余2，求此数最小为几。
3 m; c7 E3 B! Q
. _4 C, I9 J0 d! T- @% v    筛选法不一定非要标记true/false,有时候也可以使用计数来进行筛选，这个问题就是一例。
& L) p6 |) J$ G) O; {" ?    首先，如果问题有解，则解必小于 5 * 7 = 35,只用在此范围内筛选即可。
    在程序处理上，如果一个数满足一个条件，就将计数值加1，最后计数值为3的即为所求。

void fun3()
{
# F* E# b+ c; }, k    int a[105];//105 = 5 * 7
    int i;
4 h$ k0 X- L" d1 Q$ M& _+ J    //计数清0
- F" }- B* n- @: N- ?  h    for ( i = 0; i < 35; i++ )
# ^$ \, u" y' F        a = 0;
7 S9 Z0 l( W, Q6 C' d9 X    //开始筛选
& v+ V; q, V1 M2 L: N% J; J    for ( i = 3; i < 35; i += 5 )
        a ++;
    for ( i = 2; i < 35; i += 7 )
: |& i, i: q3 l( Y        a ++;
4 G' e& J! ]5 ]* t, |1 A* b9 a( \
    for ( i = 0; i < 35; i++ )
. B( n6 x: T" o; U        if ( a == 3 )
/ V0 d$ _, X/ m: |* n, l  {0 [        {
            cout << i << endl;
4 \% K% `% G+ s# M( k            return;
6 E3 i; z8 N0 _4 u. J" e5 |! `# n        }
    //如果执行到这里说明无解
    cout << "No Answer!" << endl;
}
6 G' C2 j5 x* q  \) O+ }
3 R$ n. e$ _* A, o" L! [4 D: L
总结：
    筛选法的时间效率较高，但需要一个辅助数组，这就意味着对规模很大的问题不适用。例如第3个问题，条件多1个，需要的空间就翻几倍。解决的办法是：
' I4 ~  L( J* d7 ^( ^
: m7 t" B$ b' `7 Vfor ( int i = 0; i< n; i++ )
{
    if ( i % 5 == 3 && i % 7 == 2 && ... )
% v# s# j4 V  B+ H8 i# J- `        cout << i;
% f1 f& [1 {* E, G3 n5 k( j" r) p}
! X5 ^5 B  E5 \0 p    但相应的，这样做速度就慢了下来。所以还得根据问题的规模来决定使用什么方案。
' W0 w* D1 s; e/ j
0 F; D' g  [- H' c    总体来讲，对于可以条件判断较复杂，且根据前一个（不）符合条件的情况较简单的推出下一个（不）符合条件的情况，（不）符合条件的情况分布较稀疏的问题，用筛选法速度较快。如果第3题中加一个条件被2除余1，用筛选法就不太合算了。
% ^8 s! M- S1 S( C; N* R# g
3 f* M5 [3 I1 s7 ^    最后说明一下，此次给出的程序目的在于说明方法，在效率并不是最高的

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5