编程之美 找符合条件的整数

今天看了《编程之美》上的2.8节---找符合条件的整数。

 

这道题的解法比较好，就是变换思路：将查找M，使得M*N这个数只含有0,1的问题转化为先找只含有0，1数字的X问题。

 

解法1：暴力求解。从1开始查找M，然后判断M*N=X这个数字是否只含有0,1.

 

解法2：因为X只含有0,1所以满足这个条件的X的个数会比满足条件的M少。利用BFS方法进行遍历。f（a*10），f（a*10+1）

具体代码如下：

 

解法3：是对解法2的优化。因为题目要求的是查找最小的数字X。所以余数的范围为0-(N-1)。并用数组存储余数为i的最小数字。即a[i]表示的是当位数为K位时，余数为i的最小数字。

这样的好处就是对BFS遍历进行剪枝。

具体代码如下：

#include <iostream>
#include <queue>
#include <set>

using namespace std;

struct _node
{
    int    value;
    int    remainder;
};

int    main()
{
    int    N = 0;
    set <int> res;
    queue<struct _node> q;
    struct _node node;
    struct _node elem;
    set<int>::iterator iter = NULL;
    int r = 0;

    //输入N
    scanf( "%d", &N );

    node.value = 1;
    node.remainder = 1;
    q.push( node );

    int size = 0;
    while( !q.empty() )
    {
        size = q.size();
        res.clear();
        while( size > 0 )
        {
            elem = q.front();
            //printf( "[%d]value=%d,remainder=[%d]\n", __LINE__, elem.value, elem.remainder );
            //printf( "size=[%d]\n", res.size() );

            //判断该数字的余数是否能被N整除
            if( elem.remainder == 0 )
            {
                cout << elem.value << endl;
                return 0;
            }
            q.pop();

            //以下为剪枝部分，得到第一个最小的余数为i的数字
            //elem*10
            int r = (elem.remainder * 10)%N;
            iter = res.find(r);
            if( iter == res.end() )
            {
                res.insert(r);
                node.value = elem.value * 10;
                node.remainder = r;
                q.push( node );
            }

            //elem*10+1
            r = (elem.remainder * 10 + 1)%N;
            iter = res.find(r);
            if( iter == res.end() )
            {
                res.insert(r);
                node.value = elem.value * 10+1;
                node.remainder = r;
                q.push( node );
            }
            size--;
        }
    }
}