题意:
给一个数n,让你找出一个只有1,0,组成的十进制数,要求是找到的数可以被n整除。
用DFS是搜索 当前位数字 (除最高位固定为1),因为每一位都只有0或1两种选择,换而言之是一个双入口BFS。
用DFS也可用queue代替BFS也可。
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include<cmath> using namespace std; bool found; void dfs(unsigned __int64 t, int n, int k) { if (found) return; if (t%n == 0) { printf("%I64u\n", t); found = true; return; } if (k == 19) return; dfs(t * 10, n, k + 1); dfs(t * 10 + 1, n, k + 1); } int main() { int n; while (cin >> n, n) { found = false; dfs(1, n, 0); } return 0; }
#include<iostream> #include<stdio.h> #include<queue> using namespace std; void bfs(int n) { queue<long long>q; q.push(1); while(!q.empty()) { int i; long long x; x=q.front(); q.pop(); if(x%n==0) { printf("%lld\n",x); return ; } q.push(x*10); q.push(x*10+1); } } int main() { int n; while(scanf("%d",&n)&&n) { bfs(n); } return 0; }