程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 1426 Find The Multiple bfs

POJ 1426 Find The Multiple bfs

編輯:C++入門知識

題意:給你一個數n,讓求一個只有0和1組成的十進制數x,x是n的倍數。
思路:bfs,因為只有0和1組成,所以最高位肯定是1,從1開始搜即可。搜索的過程中,若x%n已經出現過了,則不在入隊。輸出最先搜到的一個即可。
代碼:
[cpp]
#include <iostream> 
#include <cstdio> 
#include <string.h> 
#include <queue> 
using namespace std; 
 
#define CLR(arr,val) memset(arr,val,sizeof(arr)) 
typedef long long LL; 
int flag[210]; 
LL bfs(int n){ 
    CLR(flag,0); 
    queue<LL> qq; 
    qq.push(1); 
    flag[1%n] = 1; 
    while(!qq.empty()){ 
        LL x = qq.front(); 
        if(x % n == 0) 
            return x; 
        qq.pop(); 
        LL y = x * 10; 
        int yy = y % n; 
        LL z = x * 10 + 1; 
        int zz = z % n; 
        if(!flag[yy]){ 
           qq.push(y); 
           flag[yy] = 1; 
        } 
        if(!flag[zz]){ 
           qq.push(z); 
           flag[zz] = 1; 
        } 
    } 

int main(){ 
    //freopen("1.txt","r",stdin); 
    int n; 
    while(scanf("%d",&n) &&n){ 
       LL ans = bfs(n); 
       printf("%lld\n",ans); 
    } www.2cto.com
    return 0; 

 


作者:wmn_wmn

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved