Linkedin面试题

linked3
实现函数 void printFactors(int n)，将一个正整数 n 分解为多个正整数的乘积，打印出所有可能的分解情况，但不包括重复分解的情况，比如已经打印输出 3*4 ,就不应该打印输出 4*3。测试用例如下：

input:12
output:
1 * 12
2 * 6
2 * 2 * 3
3 * 4

input:32
output:
1 * 32
2 * 16
2 * 2 * 8
2 * 2 * 2 * 4
2 * 2 * 2 * 2 * 2
2 * 4 * 4
4 * 8

任何一个数都可以分解为两个数字的乘积 , 以32为例：

2*16
4*8

实现上述分解的代码(java)：

public static void function1(int n){
    	int shang,yushu,chushu;
        //chushu<=sqrt(n)目的是使除数小于等于商,摒除重复分解
    	for(chushu=2;chushu<=Math.sqrt(n);chushu++){
    		yushu = n % chushu;
    		shang = n / chushu;
    		if(yushu==0){
    			System.out.println(chushu+"*"+shang);
    		}
    	}
    }

上述分解的结果中，商可以继续两两分解，比如 2*16 , 16 可以继续分解为 2*8，4*4，不断递归对商做两两分解，直到商为质数为止，每分解一次，输出一次分解结果。因为输出要保留 “2*”，所以把 “2*”作为下一轮递归函数的参数 , 对 function1 输出结果中的商递归分解结果如下：

2*16
2*2*8
2*2*2*4
2*2*2*2*2
2*4*4
2*4*2*2
4*8
4*2*4
4*2*2*2

实现上述递归分解的代码：

public static void function2(int n,String str){
    	int shang,yushu,chushu;
    	for(chushu=2;chushu<=Math.sqrt(n);chushu++){
    		yushu = n % chushu;
    		shang = n / chushu;
    		if(yushu==0){
    			System.out.println(str+chushu+"*"+shang);
    			function2(shang,str+chushu+"*");
    		}
    	}
    }

在输出结果中出现多对重复，比如 2*4*2*2 和 2*2*2*4 互相重复。在 function2 中已经保证了除数一定是小于等于商的，但是还需要保证本轮分解的除数要大于等于上一轮分解中的除数才可以，比如：2*16分解为2*4*4，这一轮除数为4，继续分解得到 2*4*2*2，这一轮除数为2，那么 2*4*2*2 一定是重复分解，在前面出现过，所以可以得到代码的第三个版本：

public static void function3(int n,int preChushu,String str){
    	int shang,yushu,chushu;
    	for(chushu=2;chushu<=Math.sqrt(n);chushu++){
    		yushu = n % chushu;
    		shang = n / chushu;
    		if(yushu==0&&chushu>=preChushu){
    			System.out.println(str+chushu+"*"+shang);
    			function3(shang,chushu,str+chushu+"*");
    		}
    	}
    }

当 n=32时，运行结果为

2*16
2*2*8
2*2*2*4
2*2*2*2*2
2*4*4
4*8

最终代码：

public static void printFactors(int n) {
	System.out.println(1 + "*" + n);
	function(n, 1, "");
}

public static void function(int n, int preChushu, String str) {
	int shang, yushu, chushu;
	for (chushu = 2; chushu <= Math.sqrt(n); chushu++) {
		yushu = n % chushu;
		shang = n / chushu;
		if (yushu == 0 && chushu >= preChushu) {
			System.out.println(str + chushu + "*" + shang);
			function(shang, chushu, str + chushu + "*");
		}
	}
}

转载请注明：晋坤的博客 » Linkedin面试题