Find The Multiple BFS入门

原题链接：1426 -- Find The Multiple

看不懂题意?嘿嘿，友情链接。

题意：输入一个n，就是找到一个由0,1组成的数M能够整除n，然后输出M。

老规矩直接上代码：

    BFS代码：

#include 
#include 
using namespace std;
int n;//宏定义 
void BFS(long long x)
{
    queueQ;
    Q.push(x);
    while(Q.size()) 
    {
        long long  M = Q.front();
        Q.pop();
        if(M%n == 0)// 
        {
            printf("%lld\n",M);
            return;
        }
        Q.push(M*10);
        Q.push(M*10+1);
    }
}
int main(void)
{
    while(~scanf("%d",&n),n)
    {
        BFS(1);
    }   
    return 0;
} 

    在参照网友的博客时，我也发现了这个题也可以用循环做：

#include 
#include 
#include 
using namespace std;
long long mod[1000000];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        int i;
        for(i = 1;; i++){//这里要从一开始，为什么看下面
            mod[i] = mod[i/2]*10+i%2;//这时关键语句，实际上和上一个代码的深搜是一个道理，只不过用循环代替了，很巧妙，我们来分析一下
            //因为每次只有两个操作，所以第i个数，应该由第i/2个数*10或者*10+1得到，因为每次都要乘十，所以每次都乘，只不过就是加一或者不加的问题
            //这里就巧妙用到下标奇偶性质，奇数模2为1，就相当与加一，而偶数相当于不加，所以下标从1开始是方便的，你可能问开始的两个加一或不加会不会出现零，因为题目要求不能出现
            //零，不会，因为第一个是1，第二个发现虽然不加1但是2/2=1了所以第二个元素还是1，所以从下标1开始很神奇！
            if(mod[i]%n==0){
                printf("%lld\n",mod[i]);
                break;
            }
        }
    }
    return 0;
}

View Code

小结：此题也是BFS题，每次搜索有两个方向*10或着*10+1，才看到这个题的时候没看懂题意，看懂题意就发现还是蛮简单的，不过我感觉BFS有点小瑕疵，就是当长度大于200的时候好像没考虑到······。