原题链接: 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;
- }
在参照网友的博客时, 我也发现了这个题也可以用循环做:
- #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 的时候好像没考虑到.......
来源: http://www.bubuko.com/infodetail-3392468.html