2.2　筛选法模拟

（1）筛选法模拟的思想

筛选法模拟是先从题意中找出约束条件，并将约束条件组成一个筛；然后将所有可能的解放到筛中，并将不符合约束条件的解筛掉，最后在筛中的即问题的解。

（2）筛选法模拟的特点

·结构和思路简明、清晰，但带有盲目性，因此时间效率并不一定令人满意。

·关键是给出准确的约束条件，任何错误和疏漏都会导致模拟失败。

·筛选规则通常不需要很复杂的算法设计，因此属于简单模拟。

【2.2.1　Self Numbers】

1949年，印度数学家D.R.Kaprekar发现了一类被称为自数（self-number）的数。

对任意的正整数n，定义d(n)是n与n每一位数再相加的总和。d表示位相加（digitadition），是由Kaprekar创造的术语。例如，d(75)=75+7+5=87。给出任意正整数n作为起始点，可以构造整数n的无限增量序列：d(n),d(d(n)),d(d(d(n))),…。例如，如果以33作为起始点，下一个数是33+3+3=39，再下一个数是39+3+9=51，再下一个数是51+5+1=57，可以产生序列33,39,51,57,69,84,96,111,114,120,123,129,141,…。

整数n被称为d(n)的生成数，在上述序列中，33是39的生成数，39是51的生成数，51是57的生成数，等等。一些数有一个以上的生成数，例如，101有两个生成数91和100。没有生成数的数称为自数（self-number）。在100以内有13个自数：1、3、5、7、9、20、31、42、53、64、75、86和97。

输入

本题没有输入。

输出

写一个程序，以递增的顺序输出所有小于10 000的自数，每个数一行。

试题来源：ACM Mid-Central USA 1998

在线测试：POJ 1316，ZOJ 1180，UVA 640

试题解析

本题采用筛选法模拟。设筛子为数组g，其中g[y]=x表明y是x的递增序列中的一个数。按照“d[x]=x+x的每位数”，我们先设计一个子程序generate_sequence(x)，从x出发，构造整数x的无限增量序列[d(x),d(d(x)),d(d(d(x))),…]，将序列中每个数的生成数设为x，则

g[d(x)]=g[d(d(x))]=g[d(d(d(x)))]=…=x

x的增量序列中的所有数都不是自数，应从筛子g中筛去。这个过程一直进行到产生的数大于等于10 000或者已经产生过（g[x]≠x）为止，因为若x已经产生过，则继续构造下去会发生重复。

有了核心子程序generate_sequence(x)，便可以展开算法了。

首先，将g[i]初始化为i（1≤i≤10 000）；然后，依次调用generate_sequence(1)，…，generate_sequence(10 000)，计算出g[1..10000]后，筛中剩下的数（满足条件g[x]==x）即自数。

参考程序

---

#include <stdio.h>                        //预编译命令
#define N 10000                           //定义N为常数10000
unsigned g[N];                            //定义无符号数组g
unsigned sum_of_digits (unsigned n)       //计算n的各位数字之和
{
    if (n < 10)
        return n;
    else
        return (n % 10) + sum_of_digits (n / 10);
}
void generate_sequence (unsigned n)       //构造整数n的无限增量序列
{
    while (n < N)                         //若n未达到上限，则循环
    {
        unsigned next=n+sum_of_digits(n); //计算d[n]
        if (next >= N || g[next] != next) //若d[n]超过上限或者非自数，则返回
            return;
        g[next] = n;                      //将d[n]放入n的无限增量序列
        n = next;                         // 继续扩展d[n]
    }
}
int main ()
{
    unsigned n;
    for (n = 1; n < N; ++n)               //最初假设所有数为自数
        g[n] = n;
    for (n = 1; n < N; ++n)               //计算g[1..10 000]
        generate_sequence (n);
    for (n = 1; n < N; ++n)               //输出筛中满足g[x]==x条件的自数
        if (g[n] == n)
            printf ( "%u\n", n);
    }

---