1的单位分解

缘起

面试题

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
30
31
32
33
34
35
可以把1分解为若干个互不相同的单位分数之和。
例如：
1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
等等，类似这样的分解无穷无尽。
我们增加一个约束条件：最大的分母必须不超过30
请你求出分解为n项时的所有不同分解法。
数据格式要求：
 
例如，
输入：
4
程序应该输出：
1/2 1/3 1/8 1/24
1/2 1/3 1/9 1/18
1/2 1/3 1/10 1/15
1/2 1/4 1/5 1/20
1/2 1/4 1/6 1/12
再例如，
输入：
5
程序应该输出：
1/2 1/3 1/12 1/21 1/28
1/2 1/4 1/6 1/21 1/28
1/2 1/4 1/7 1/14 1/28
1/2 1/4 1/8 1/12 1/24
1/2 1/4 1/9 1/12 1/18
1/2 1/4 1/10 1/12 1/15
1/2 1/5 1/6 1/12 1/20
1/3 1/4 1/5 1/6 1/20

资源约定：
峰值内存消耗 < 256M
CPU消耗  < 2000ms

分析

类似的题目在【1】中做过, 就是裸体的dfs, 和【1】中代码风格保持一致.

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#define LOCAL
const int maxn = 105; // n最多100
int n, ans[maxn], cnt; // ans中存储答案的, 这里我们要求ans是递减的

bool ck() // 检查ans中保存的是不是一组解,注意, 这里避开了浮点数
{
	int sum = 1, sum1 = 0;
	for (int i = 0;i<n; i++)
	{
		sum*=ans[i];
	}
	for (int i = 0;i<n; i++)
	{
		sum1+=sum/ans[i];
	}
	return sum^sum1;
}

void dfs(int cur, int min) // 当前决定 a[cur], 而且要求ans[cur+1,...]都>=ans[cur]
{
	if (!(cur^n))
	{
		if (!ck()) // 检查当前得到的ans是不是一组解
		{
			++cnt;
			printf("1 = ");
			for (int i = 0; i<n; i++)
			{
				if (i)
				{
					putchar('+');
				}
				printf("1/%d ", ans[i]);
			}
			puts("");
		}
		return;
	}
	for (int i = min; i<=30;i++)
	{
		ans[cur] = i;
		dfs(cur+1, i+1); // 如果题目允许1=1/4+1/4+1/4+1/4这样的分解的话,就要写i,而不是i+1
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d", &n);
	printf("1的%d-单位划分方案如下:\n", n);
	dfs(0,2);
	printf("共计%d种方案.", cnt);
	return 0;
}

参考

【1】https://yfsyfs.github.io/2019/07/17/面试题-整数划分/