回溯法:超级幸运数
问题阐述
幸运数为 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;
}
}
版权声明:
本站所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自
后端技术分享!
喜欢就支持一下吧