POJ 1426 Find The Multiple
【摘要】 题目链接~~>
做题感悟:做了杭电上的两个题目,再做这个真是 so easy !但是还要写一下的,用第二种方法很不熟练。。。
解题思路:还是用取余的思想,每次都将余数乘 10 再加 上相应的数,0 要特判一下。
代码1:
#include<stdio.h>#include<iostream>#include<string...
做题感悟:做了杭电上的两个题目,再做这个真是 so easy !但是还要写一下的,用第二种方法很不熟练。。。
解题思路:还是用取余的思想,每次都将余数乘 10 再加 上相应的数,0 要特判一下。
代码1:
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std ;
int n ;
bool vis[300] ; // 标记余数是否相同
struct zhang
{
int x,num ;
string str ; // 这个很好用
} ;
int bfs()
{
queue<zhang>q ;
zhang curt,next ;
memset(vis,false,sizeof(vis)) ;
curt.x=0 ;
curt.str="" ;
curt.num=0 ;
q.push(curt) ;
while(!q.empty())
{
curt=q.front() ;
q.pop() ;
if(curt.num>100) continue ;
for(int i=0 ;i<2 ;i++)
{
next=curt ;
next.num+=1 ;
next.x=next.x*10+i ;
if(!next.x) continue ;
if(next.x%n==0)
{
next.str+=(48+i) ;
next.str+='\0' ;
cout<<next.str<<endl ;
return true ;
}
next.x=next.x%n ;
if(vis[next.x]) continue ;
vis[next.x]=true ;
next.str+=(48+i) ;
q.push(next) ;
}
}
return false ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(!n) break ;
bfs() ;
}
return 0 ;
}
代码2:
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#define MX 5000
using namespace std ;
int n ;
bool vis[300] ;
struct zhang
{
int x,m,pre,num ;
}q[MX];
void print(int k) // 输出 不用string 存数
{
if(k==-1)
return ;
print(q[k].pre) ;
printf("%d",q[k].x) ;
}
int bfs()
{
zhang curt,next ;
int start=-1,head=0 ;
memset(vis,false,sizeof(vis)) ;
curt.x=1 ;
curt.num=1 ;
curt.pre=-1 ;
if(n==1)
{
cout<<1<<endl ;
return true ;
}
vis[1]=true ;
curt.m=1 ;
q[++start]=curt ;
while(head<=start)
{
int h=head ;head++ ;
curt=q[h] ;
if(!curt.m)
{
print(h) ;
printf("\n") ;
return true ;
}
if(curt.num>100) continue ;
for(int i=0 ;i<2 ;i++)
{
next=curt ;
next.m=next.m*10+i ;
if(!next.m) continue ;
next.m=next.m%n ;
if(vis[next.m]) continue ;
vis[next.m]=true ;
next.x=i ;
next.num+=1 ;
next.pre=h ;
q[++start]=next ;
}
}
return false ;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
if(!n) break ;
bfs() ;
}
return 0 ;
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/17435837
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)