蓝桥杯 - 分数拆分 C语言实现

分数拆分

输入正整数k，找到所有的正整数x>=y,使得1/k=1/x + 1/y; 

样例输入： 
2 
12 
样例输出： 
2 
1/2 = 1/6 + 1/3 
1/2 = 1/4 + 1/4 
8 
1/12 = 1/156 + 1/13 
1/12 = 1/84 + 1/14 
1/12 = 1/60 + 1/15 
1/12 = 1/48 + 1/16 
1/12 = 1/36 + 1/18 
1/12 = 1/30 + 1/20 
1/12 = 1/28 + 1/21 

1/12 = 1/24 + 1/24 

分析：

经典的枚举题，暴力枚举不用太用脑，但对问题进行一定的分析往往会让算法更清晰、高效。

由 x >= y , 1/k=1/x+1/y 可以推导出  x >= 2k >= y
且 y  >= 1 
所以我们循环 y （因为y有限），x则根据 y 和 k 求得，但需要注意除数不能为0且x >= 2k 。

代码在此：

#include<stdio.h>

/*
由 x >= y , 1/k=1/x+1/y 可以推导出  x >= 2k >= y

y >= 1 
所以我们循环 y 因为y有限，x则根据 y 和 k 求得，但需要注意除数不能为0且x >= 2k 
*/
int main () {
	
	int k;
	int i, j;
	
//	scanf("%d", &k);
	k = 12;
	double count = 1.0 / k;
	
	double x;
	for(i = 1; i <= 2 * k; i ++){
		double temp = (count - 1.0 / i);
		
		if(temp == 0)
			continue;
			
		x = 1 / temp;
		
		if(x >= 2 * k)
			printf("1/%d=1/%.0lf+1/%d\n", k, x, i);
	}  
	
	return 0;
}