冰川网络2015春招笔试题第四题

第四题

给定一个正整数n，找出另一个正整数m，使n*m的积由1、0组成，m为满足条件的最小值

笔试的时候用的是蛮力法，显然不太好，这里进行了优化

思路：

1)若n长度为3, b=1000(二进制)

2）将b按值面值转为十进制 product = 1000(十进制)

3)若product%n==0 测输出product/n

4)若product%n!=0 b++回到2）

代码：

//给定一个正整数n，找出另一个正整数m，使n*m的积由1、0组成，m为满足条件的最小值
#include<iostream>
using namespace std;

//输入一个正整数
//输出这个正整数的长度
int Numlength(int num)
{
 int i = 0;
 while (num > 0)
 {
  num /= 10;
  i++;
 }
 return i;
}

//输入一个整数n
//输出n对应的二进制值面值。例如 n=5 对于二进制为101，输出数十进制的101
//若n*m由别的数组成 只需要对这个函数进行修改即可
unsigned int BinaryToDecimal(int n)
{
 int b = 1;
 int sum = 0;
 int k = 1;
 while (n > 0)
 {
  if (n & 0x1)
   sum += 1*k;
  k *= 10;
  n = n >>1;
 }
 return sum;
}

//输入一个正整数n
//输出一个数m，n*m的积由1、0组成且m为满足条件的最小数
int MainCode(int n)
{
 int b = 0x1 << Numlength(n);
 unsigned int product = BinaryToDecimal(b);
 while (1)
 {
  if (product%n == 0)
   break;
  product = BinaryToDecimal(b++);

 }
 
 return product/n;
}

int main()
{
 int n = 13;
 int m = MainCode(n);
 cout << m << endl;
 return 0;
}

结果：