Find The Multiple BFS入门

原题链接:http://poj.org/problem?id=1426

看不懂题意?嘿嘿,友情链接

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

老规矩直接上代码:

    BFS代码:

 

#include <stdio.h>
#include <queue>
using namespace std;
int n;//宏定义 
void BFS(long long x)
{
    queue<long long>Q;
    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;
} 

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

Find The Multiple BFS入门
#include <iostream>
#include <cstdio>
#include <cstring>
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的时候好像没考虑到······。

上一篇:C - Find The Multiple


下一篇:0055 html5新增表单属性:required、placeholder、autofocus、autocomplete、multiple