[编程之美_2.8]找符合条件的整数

题意很简单，给定一个n, 求一个最小的m，使得n_m中的10进制表示只有0,1
方法1：Brute Force [大整数的情况需要考虑，何时终止，时间复杂度如何？]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


bool CheckNumber(int number)
{
   while(number)
   {
       if (number%10 != 0 && number%10 != 1)
           return false;
       number /= 10;
   }
   return true;
}

int CalcMBruteForce(int n)
{
   int m = 1;
   while (!CheckNumber(m * n))
   {
       m++;
   }
   return m;
}

方法2：BFS [大整数的情况需要考虑，何时终止，去重复计算问题]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


int CalcM(int number)
{
   int i = 1;
   vector<int> vList;
   vList.clear();
   vList.push_back(0);
   vList.push_back(1);
   vector<int> vListC;
   int k = 1;
   // TODO:
   // BigInt
   // Delete duplicate
   while (true)
   {
       vListC.clear();
       for (vector<int>::size_type i = 0; i < vList.size(); i++)
       {
           if (vList[i] && vList[i] % number == 0)
           {
               return vList[i];
           }
           vListC.push_back(vList[i] + 0);
           vListC.push_back(vList[i] + (int)pow(10.0, k));
       }
       vList.clear();
       vList = vListC;
       k++;
   }
}