回溯法:超级幸运数

问题阐述
幸运数为 4 和 7，超级幸运数则是指因数只有 4 和 7 的数，比如 28，16，49 等。给出一个个数为 N 的数列，求其中幸运数的个数；数据范围：num>1, N>1；

分析
暴力破解不难，直接给出代码：

void comparator(int num)
{
	if (num == 1)
		return;
	while (num!=0)
	{
		if (num == 1)
		{
			count_2++;
			break;
		}
		if (num % 4 != 0 && num % 7 != 0)
			break;
		if (num % 4 == 0)
			num /= 4;
		if (num % 7 == 0)
			num /= 7;		
	}
}

其中，第 3、5、12 行代码是容易忽略的地方。

那么，如何用回溯法解决此问题？不同于暴力破解对 num 的 拆分 (除、模)，回溯法是对 num 进行 拼凑 ，比如，对于数字 18，会尝试用 4*4，4*7 去拼凑，如果拼凑的结果大于 num，则回溯到上一层进行下一次尝试。图示如下：

根据图示，易得以下代码：

//num是需要检验的数字，luck是当前所在节点的累积数值，即紫色框中的数字
void lucky(int& num, int luck)
{
	if (num<luck*4)//即图示中的比大小，如果左子树进不去(luck*4)，则右子树也不可能进(luck*7)
		return;//回溯
	if (num == luck * 4 || num == luck * 7)
	{
		num = 0;//标记已成功
		count_1++;
		return;
	}
	lucky(num, luck*4);//先进左子树
	if (num == 0)
		return;
	lucky(num, luck*7);//如果未标记成功，则继续进入右子树
}

需要注意第 8、13 行代码，作用如图示：

可见，如果不标记检测成功，28 就被 count++了两次，实际上 count++ 一次后就应该停止回溯。所以需要在成功后将 num 设置为 0（也可以采用其他标记方式）以标记成功，后续不再进入右子树。

附上对数器，所有代码如下：

#include<iostream>
#include<cstdlib>//rand()
#include<ctime>//time()
#include<cstring>//memcpy()

int count_1;
int count_2;
void lucky(int& num, int luck)
{
	if (num<luck*4)
		return;
	if (num == luck * 4 || num == luck * 7)
	{
		num = 0;
		count_1++;
		return;
	}

	lucky(num, luck*4);
	if (num == 0)
		return;
	lucky(num, luck*7);
}

void comparator(int num)
{
	if (num == 1)
		return;
	while (num!=0)
	{
		if (num == 1)
		{
			count_2++;
			break;
		}
		if (num % 4 != 0 && num % 7 != 0)
			break;
		if (num % 4 == 0)
			num /= 4;
		if (num % 7 == 0)
			num /= 7;		
	}
}

int* generateRandomArr(int max, int len) {
	int* arr = new int[len];
	for (int i = 0; i < len; i++)
		arr[i] = rand() % max;
	return arr;
}

int* cpyArr(int* src, int len) {
	int* des = new int[len];
	memcpy(des, src, len * sizeof(int));
	return des;
}


int main()
{
	srand(time(NULL));
	int testTimes = 10000000;//测试次数
	int arrMaxLen = 1000;//数组最大长度
	int max = 100000;//最大数据

	for (int i = 0; i < testTimes; i++)
	{
		int arrLen = rand() % arrMaxLen;
		int* arr_1 = generateRandomArr(max, arrLen);
		int* arr_2 = cpyArr(arr_1, arrLen);
		count_1 = 0;
		count_2 = 0;

		for (int i = 0; i < arrLen; i++)
		{
			lucky(arr_1[i], 1);
			comparator(arr_2[i]);
		}
		if (count_1 != count_2)
		{
			std::cout << "go wrong" << std::endl;
			for (int i = 0; i < arrLen; i++)
				std::cout << arr_2[i] << " ";
			std::cout << std::endl;
			std::cout << count_1 << std::endl;
			std::cout << count_2 << std::endl;
			break;
		}
		else
			std::cout << "success" << std::endl;
	}

}