目录
方法一：直接dfs
方法二：打表+搜索
题目链接http://poj.org/problem?id=1426
方法一：直接dfs
【题意】输入一个n（≤200），找到只由0、1组成的不超过100位的数能整除n并输出，如果有多个答案，输出一个即可。
【分析】在担心深搜会不会爆内存，因为有2^100，但是这道题肯定是可以搜到答案的，所以不会?
【dfs】想用vis数组来避免死循环，因为感觉可能会发生类似无限循环小数的情况，但是用了之后会wa....因为会有很多数据输出不了
所以，是不需要用vis数组的啊，dfs肯定是会结束的不会死循环，如果这里循环了那么到达递归结束条件了就结束递归了，所以是不用担心会死循环的问题的。而且如果用了vis来进行标记的话，其实真正递归的只有200个状态了（因为x%n），但是实际上肯定是不止这些状态的，实际其实是有2^200个状态，这样的话很多情况都输出不了了。
如果真的要用vis来标记的话，这道题有两个状态，一个是递归深度，还有一个就是余数。所以二维vis来标记某深度下某余数是否访问过，这样一来就不会有数据输不出来。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;const int maxn=210;
vector<int>v;
//int vis[maxn];
int n;void dfs(int x)
{if(v.empty())return;if(v.size()>100)return;if(x%n==0){for(int i=0;i<v.size();++i)printf("%d",v[i]);puts("");v.clear();return;}x=x%n;// if(vis[x])return;// vis[x]=1;v.push_back(0);dfs(x*10);if(v.empty())return;//v.pop_back();v.push_back(1);dfs(x*10+1);if(v.empty())return;//这里注意判断一下，如果v已经为空了是不可以pop的v.pop_back();
}
int main()
{while(~scanf("%d",&n)){if(n==0)break;v.clear();// memset(vis,0,sizeof(vis));v.push_back(1);dfs(1);}
}
方法二：打表+搜索
【分析】先打表，找出范围，发现最多也就是19位。然后就可以dfs或bfs搜索了。知道怎么做了就挺简单的一道题了。
【打表代码】
#include<bits/stdc++.h>
using namespace std;int check(string &s,int mod)
{int flag=0;for(int i=0;i<s.size();i++)flag=(flag*10+s[i]-'0')%mod;return flag==0;
}
string bfs(int n)
{queue<string>q;q.push("1");while(!q.empty()){string x=q.front();q.pop();if(check(x,n))return x;for(int i=0;i<2;i++){string t=x+char('0'+i);if(check(t,n))return t;q.push(t);}}
}
int main()
{for(int i=1;i<=200;i++)cout<<bfs(i)<<endl;return 0;
}
【题目代码】dfs
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
using namespace std;typedef long long ll;
int n,flag;void dfs(int k,ll now)
{if(k==20 || flag)return;if(now%n==0){printf("%lld\n",now);flag=1;return;}dfs(k+1,now*10);dfs(k+1,now*10+1);
}int main()
{while(~scanf("%d",&n)&&n){flag=0;dfs(1,1);}return 0;
}或者 bfs
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;const int maxn=210;
typedef long long ll;
int n;void bfs()
{queue<ll>q;q.push(1);while(!q.empty()){ll now=q.front();q.pop();// cout<<now<<endl;if(now%n==0){printf("%lld\n",now);return;}q.push(now*10);q.push(now*10+1);}
}
int main()
{while(~scanf("%d",&n)&&n){bfs();}
}