POJ 1426 Find The Multiple

题目链接~~>

做题感悟：做了杭电上的两个题目，再做这个真是 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