暴力破解最常用的就是枚举法,也叫穷举法。 这是我在刚接触算法的时候,用的最顺手的、也是最爱用的方法哈哈哈,我把他叫做“暴力递归”。
枚举法(穷举法) 枚举法是在分析问题时,逐个列举出所有可能情况,然后根据条件判断此答案是否合适,合适就保留,不合适就丢弃,最后得出一般结论。主要利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检验,从中找出符合要求的答案,因此枚举法是通过牺牲时间来换取答案的全面性。 说白了,就是通过循环或者递归,把所有可能的情况过一遍,符合条件就留下,不符合继续找。
方法步骤:1.确定枚举对象、枚举范围、判断条件。 2.循环验证每一个解。 火柴棒等式 【问题描述】给你n根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0)。用火柴棍拼数字0-9的拼法如图所示: 注意: 1. 加号与等号各自需要两根火柴棍 2. 如果A≠B,则A+B=C与B+A=C视为不同的等式(A、B、C≥0) 3. n根火柴棍必须全部用上 【输入】输入一个整数n(n≤24)。 【输出】输出能拼成的不同等式的数目。 问题简述:给你n(n<=24)根火柴棒,叫你拼出 “A + B = C”这样的等式,求方案数。 思路:本题最多24根火柴,等号和加号共用4根火柴,所以A,B,C这3个数字需用20根火柴。我们考查A和B的最大的取值可能:0~9这10个数字所用的火柴数为6,2,5,5,4,5,6,3,7,6,很明显数字1用的火柴棒最少只要2根,不妨让B为1,那么A和C最多可以使用18根火柴,而C>=A,满足条件的A的最大取值为1111。所以枚举A和B的范围是从0~1111。 为了加快速度,可以将0到2222的所有整数需要的火柴棒数目提前算好保存在数组中。 代码如下: #include <iostream>
using namespace std;
int a[2223]={6,2,5,5,4,5,6,3,7,6};
const int b[10]={6,2,5,5,4,5,6,3,7,6};
//计算自然数n所需要的火柴数
int need(int n)
{
int tmp, num;
num=0;
if(n==0) return 6;
while(n>0) {
tmp=n%10;
num+=b[tmp];
n/=10;
}
return num;
}
int main( )
{
int n,A,B,C,D,sum;
cin>>n;
sum=0;
for(int i=10; i<2223; i++) //预处理
a[i]=need(i);
for(int i=0; i<=1000; i++) {
for(int j=0; j<=1000; j++) {
A=a[i]; B=a[j]; C=n-4-A-B;
D=a[i+j];
if(D==C) sum++;
}
}
cout<<sum<<endl;
system("PAUSE");
return 0;
}
|