Find The Multiple
程序员文章站
2022-05-24 09:37:54
...
【题目大意】
给定正整数n,编写程序找出非零值n的倍数m,并且m的十进制数表示仅包含数字0和1。你可以假设n不大于200,且有不超过100位的相应m。
【分析】
不要逐个测试n的倍数是否全由0和1组成即可,这样做会花费大量时间,效率低。
可以反过来想,只由0和1组成的数相比于整个搜索空间而言是非常少的,可以去搜索由0和1组成的数,然后通过判断这些数能否整除n来求解这个问题。于是,可将由0和1组成的数字num作为一个搜索状态。能由num扩展得到的状态有两个,一个是10*num,另一个是10*mun+1。这两个状态都必然是由0和1组成的。而且整个过程无需设置记录访问的数组。
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
void BFS(int n)
{
queue<long long> myqueue;
myqueue.push(1);//压入初始状态
while(!myqueue.empty())
{
long long current=myqueue.front();
myqueue.pop();
if(current%n==0)//查找成功
{
cout<<current;
return ;
}
myqueue.push(current*10);
myqueue.push(current*10+1);
}
}
int main()
{
int n;
while(cin>>n)
{
if(n==0)
break;
BFS(n);
}
return 0;
}
推荐阅读
-
jQuery中find()方法用法实例教程
-
【Leetcode】724-寻找数组的中心索引(Find Pivot Index)
-
使用find命令查找Linux中的隐藏文件的方法
-
Linux中的find命令使用时的一些注意点整理
-
OPPO Find X2 Pro获蓝牙5.1认证:6.7寸2K屏、后置双4800万三摄
-
Linux find命令中-exec参数的作用介绍
-
Linux find命令中-path -prune参数作用详细介绍
-
Yii框架中 find findAll 查找出制定的字段的方法对比
-
外媒泄露OPPO Find X2 Pro已获得NBTC认证 全球上市指日可待
-
OPPO Find X2搭载独家定制大底传感器 沈义人:awesome