2019的分解方法

2019的分解方法 问题描述

把2019分解成3个各不相同的正整数之和,并且要求每个正整数都不包含数字2和4,一共有多少种不同的分解方法?注意交换3个整数的顺序被视为同一种方法,例如1000+1001+18和1001+1000+18被视为同一种。

思路分析

本题中，要求将2019分解成三个各不相同的数，且仅交换顺序被视为同一种方法，即(i + j + k)与(j + k + i)是同一种方法，既然如此，我们就规定i < j < k，再用循环计数即可。至于是否包含2和4的判断，有两种方法实现：第一种是直接将待判断数的每个数位取出判断；第二种是先将数字转化为字符串，再在字符串里查找是否含有‘2’和‘4’，注意这里的‘2’和‘4’是单个字符，而不是数字。

代码

方法一：

#include 
using namespace std;
bool Check(int x){//Methods a
	while(x != 0){
		if(x % 10 == 2 || x % 10 == 4) return false;
		x /= 10;
	}
	return true; 
}
int main(){
	long sum = 0;
	for(int i = 1; i < 673; i++)
		for(int j = i + 1; j * 2 < 2019 - i; j++)
			if(Check(i) && Check(j) && Check(2019 - i - j))
				sum++;
	cout << sum;
	return 0;
}

方法二：

#include 
using namespace std;
bool Check(int x){//Methods b
	stringstream ss;
	ss << x;
	string str;
	ss >> str;
	if(str.find('2') != string::npos || str.find('4') != string::npos)
		return false;
	return true; 
}
int main(){
	long sum = 0;
	for(int i = 1; i < 673; i++)
		for(int j = i + 1; j * 2 < 2019 - i; j++)
			if(Check(i) && Check(j) && Check(2019 - i - j))
				sum++;
	cout << sum;
	return 0;
}

i < 673:
由于已经规定好了i < j < k，那么i作为三个数中最小的一个数，必满足i < 2019/3，即i < 673。i, j, k的值最接近的一种情况为672，673， 674。
j * 2 < 2019 - i：
i, j的值确定好后，k的值即为2019 - i - j，根据i < j < k，j < 2019 - i - j，即 j * 2 < 2019 - i。

结语

本题的最终结果为40785。
PS：上述两种方法第一种较优，两种方法运行时间分别为0.1184s和0.55s左右。
文中如果出现错误还请广大读者批评指正(o°ω°o)。
如果对各位看官有帮助不妨留下一个点赞￣ω￣=。