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

系统管理员 2022-08-07 11:43 189阅读 0赞

第四题

给定一个正整数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;
    }

结果：

![Center][]

[Center]: /images/20220805/a60dbbf4975d41fd933c0ee15b252e42.png