优秀网站制作定制,浙江建设招生网站,addfilter wordpress,邢台企业做网站多少钱炮兵问题的优化#xff0c;设立逻辑数组
蛮力法设计思想
有策略地穷举 验证
制定穷举策略避免重复
简单来说#xff0c;就是列举问题所有可能的解#xff0c;然后去看看是否满足题目要求#xff0c;是一种逆向解题方式。#xff08;我也不知道答案是什么#xff0c;… 炮兵问题的优化设立逻辑数组
蛮力法设计思想
有策略地穷举 验证
制定穷举策略避免重复
简单来说就是列举问题所有可能的解然后去看看是否满足题目要求是一种逆向解题方式。我也不知道答案是什么但是我知道答案肯定在这些范围里面我一个个试就完了。
所以我们应该做的是
知道可能的答案都有哪些使用方法将其一一列举将每个解依次与条件比照
蛮力法使用范围 所有解空间例如a,b,c取值范围都是 0~9问abc组成的三位数的所有情况所有路径遍历图、遍历树
蛮力法的格式
蛮力法由循环和选择语句构成
使用循环穷举所有情况使用选择判断当前情况是否成立 若成立则得到问题的解若不成立则继续循环
循环 分支
for(){for(){// 获取X所有可能的情况if(X满足条件){printf(X);}}
}蛮力法思想穷举所有情况找到符合条件的。
这也意味着得能够穷举因此问题规模不能太大。
示例1求完全数 思想穷举所有数字将符合条件的找出来。
关键点求数字的所有因子。 对于数x因子y需要x % y 0此处y也需要尝试1 ~ x-1的所有数。
判断因子和是否等于x。
因此程序为
// 求完全数
#include iostream
using namespace std;int main() {for (int i 2; i 1000; i) {int sum 0;for (int j 1; j i - 1; j) {if (i % j 0) { // 若是因子sum j;}}if (sum i) {cout 完全数 i endl;}}return 0;
}
这里还有点bug是数学知识不完备因子在1 ~ m/2的范围因子不可能比原数字的一半还要大除了它本身我们循环地太多了。内循环应该是j i/2。
结果为 我们需要非常清晰地体会到构建程序框架的思维过程。
int main() {// 穷举所有情况for (int i 2; i 1000; i) {// 求因子之和// 比较因子与该数是否相等}return 0;
}然后我们再实现其细节。
充分体会穷举情况再依次判断的计算过程。
示例2求水仙花数
在数字100~999中求水仙花数例如13 53 33 153。
同样地穷举 验证。
关键点求一个三位数的每一位的数。
先建立思维框架
// 穷举100~999的所有数字
for(){// 求三位数的每一位数将其立方和相加// 判断数字与其立方和是否相等}代码为
// 求水仙花数
#include iostream
using namespace std;int main() {for (int i 100; i 999; i) {int sum 0;int temp i;while (temp){int x temp % 10;sum (x*x*x);temp / 10;}if (i sum) {cout 水仙花数 i endl;}}return 0;
}答案为 再强调一遍
循环 选择先构建思维框架再填充细节
示例3象棋算式 我们先将问题的输入找到也就是5个变量且满足
每个变量范围是0~95个变量各不相同
然后穷举所有的可能性看是否能够满足表达式这是恐怖的5层循环但是问题规模还在可接受范围内。
我们试试看。
兵a炮b马c卒d车e
#include iostream
using namespace std;int main() {int a, b, c, d, e;for (a 0; a 9; a) {for (b 0; b 9; b) {for (c 0; c 9; c) {for (d 0; d 9; d) {for (e 0; e 9; e) {// 若5个数都不同再看是否满足表达式if (!(a b || a c || a d || a e|| b c || b d || b e|| c d || c e|| d e)) {int add1 a * 1000 b * 100 c * 10 d;int add2 a * 1000 b * 100 e * 10 d;int sum e * 10000 d * 1000 c * 100 a * 10 d;if (sum add1 add2) {cout 兵 a 炮 b 马 c 卒 d 车 e endl;}}}}}}}return 0;
}结果是 不过显然太低效率了如果有n的话这个算法的时间复杂度是O(n5)这几乎是不可接受的太暴力了问题规模显得有点大是105了。
所以我们虽然遵循了 循环 选择但是穷举地过于直接看看有没有其他办法呢
思想即便是穷举也要“聪明地”穷举
同样是穷举也有不同的方法最粗暴的就是循环一层循环不行就嵌套多重循环……好蠢但是很简单好想。
我们来看看同样是穷举不同做法的差异。
示例
对于一个含有6个元素的一维数组该数组每个数只能是0或1将所有情况穷举出来。 例如(0,0,0,0,0,0)、(0,1,0,1,1,0)
最愚蠢的做法直接6重循环。
#include iostream
using namespace std;int main() {int a, b, c, d, e, f;int number[6];for (a 0; a 1; a) {for (b 0; b 1; b) {for (c 0; c 1; c) {for (d 0; d 1; d) {for (e 0; e 1; e) {for (f 0; f 1; f) {number[0] a;number[1] b;number[2] c;number[3] d;number[4] e;number[5] f;for (int i 0; i 6; i) {cout number[i] ;}cout endl;}}}}}}return 0;
}结果 这的确可以完成任务但是这样的算法真的很糟糕不是吗
我们来看看优化后的穷举的方法
我们将其与二进制结合因为对于这样的0、1序列与二进制有直接联系我们直接将十进制是0~63转换为二进制存入数组中就可以了这样大大降低了时间复杂度
#include iostream
using namespace std;int main() {int number[6];for (int i 0; i 63; i) {// 转换为二进制除二求余再倒置int temp i;for (int j 5; j 0; j--) {number[j] temp % 2;temp / 2;}// 输出结果for (int k 0; k 6; k) {cout number[k] ;}cout endl;}return 0;
}穷举加验证循环加选择蛮力解难题
穷举有方法验证有策略循环尽量浅选择看题目
我们之前谈过穷举法需要能够穷举数据规模不太大现在我们在此基础上进行了优化同样能够穷举的穷举方式的选择也很重要。
对于循环我们希望尽可能减少嵌套层数。
当然了简单的属于通用普适技法稍难的就需要动用你的观察力但是这些东西你熟悉了也就变成了简单的了。
接下来我们尝试优化示例3。
示例3优化
我们只关注如何进行穷举并且尽可能减小穷举规模空间关注一个条件5个数各不相同。
这样一来我们的问题规模就由105 10,000 变成了 10 x 9 x 8 x 7 x 6 30,240 变成了原来的30%左右。
可以用多重循环来列举出它们各种不同的取值情况逐一地判断它们是否满足上述等式为了避免同一数字被重复使用可设立逻辑数组xx[i]0≤i≤9值为1时表示数i没有被使用为0时表示数i已被使用。
int main() {int x[10];int a, b, c, d, e, i, m, n, s;for (i 0; i 9; i) x[i] 1; /*x数组置初值*/for (a 1; a 9; a){x[a] 0; /*表示不能再让其他变量取与a相同的值*/for (b 0; b 9; b)if (x[b]) /*如果b取的当前值未被其他的变量重复*/{x[b] 0; /*表示不能再让其他变量取与b相同的值*/for (c 0; c 9; c)if (x[c]) /*如果c取的当前值未被其他的变量重复*/{x[c] 0; /*表示不能再让其他变量取与c相同的值*/for (d 0; d 9; d)if (x[d]) /*如果d取的当前值未被其他的变量重复*/{x[d] 0; /*表示不能再让其他变量取与d相同的值*/for (e 0; e 9; e)if (x[e]){m a * 1000 b * 100 c * 10 d;n a * 1000 b * 100 e * 10 d;s e * 10000 d * 1000 c * 100 a * 10 d;if (m n s)printf(兵:%d 炮:%d 马:%d 卒:%d车:%d\n,a, b, c, d, e);}x[d] 1; /*本次循环未找到解,让d取其他值*/}x[c] 1; /*本次循环未找到解,让c取其他值*/}x[b] 1; /*本次循环未找到解,让b取其他值*/}x[a] 1; /*本次循环未找到解,让a取其他值*/}return 0;
}重要的收获穷举有方法不能上来题都不看就开始举有条件地穷举减少解空间对于本题5个数不同可以当作题目条件来验证也可以当成穷举的约束条件。
同样的条件不同的看法就会产生不同的解决方案。
还记得离散数学中的附加条件证明法吗将结论中的前提当条件用再推出最终结论极大简化了运算。
百元买百鸡问题 已知公鸡5元一只母鸡3元一只小鸡1元三只用100元买100只鸡问公鸡、母鸡、小鸡各多少只 知道解空间 公鸡x 0~20母鸡y 0~33小鸡z 0~100 如何列举 最简单思路三重循环 如何验证 x y z 1005x 3y z/3 100z % 3 0这样看来可以将z变量去掉了解空间也减少了100倍三重循环也变成了二重循环。也就是我们将验证条件当成解空间的约束条件减少了解空间的规模这与我们上面的示例3优化是一个思路。
注意小鸡是1元3只需要注意 z/3 时int会去掉小数点需要验证z是3的倍数。
#include iostream
using namespace std;int main() {int x, y, z;for (x 0; x 20; x) {for (y 0; y 33; y) {if ((100 - x - y) % 3 0) {if ((5 * x 3 * y (100 - x - y) / 3) 100) {cout 公鸡 x endl;cout 母鸡 y endl;cout 小鸡 100 - x - y endl;cout ********** endl;}}}}return 0;
}示例 求所有的三位数,它除以11所得的余数等于它的三个数字的平方和. 分析
解空间三位数x100~999如何枚举循环如何验证约束条件x % 11 三个数字平方和约束条件可否去限制解空间? 否
#include iostream
using namespace std;
// 求所有的三位数,它除以11所得的余数等于它的三个数字的平方和.
int main() {for (int i 100; i 999; i) {// 求三个数平方和int sum 0;int temp i;while (temp){int x temp % 10;sum (x * x);temp / 10;}// 验证if (sum i % 11) {cout 数字 i endl;}}return 0;
}结果
对问题进行建模
我们进一步分析上一题 求所有的三位数,它除以11所得的余数等于它的三个数字的平方和. 假设3位数A的三个数是xyz。
0 A % 11 10x2 y2 z2 10x*100 y*10 z A1 x 3 0 y 30 z 3且都是整数
这样一来经过简单的人工处理解空间减少了很多然后再进行 穷举 验证 就可以了显然比之前的更加高效因为进行了人工分析。
int x, y, z;
for (x 1; x 3; x) {for (y 0; y 3; y) {for (z 0; z 3; z) {int num x * 100 y * 10 z;if ((x*x y * y z * z) num % 11) {cout 数字 num endl;}}}
}这里强调的其实也是将验证条件进一步分析将其转换为解空间的约束条件以降低解空间规模。
穷举 验证穷举范围、穷举方式、验证条件、约束条件
我们再回顾之前的例子充分体会穷举法的分析思路。
穷举依赖的技术是遍历也就是解空间的每个解都要找一遍注意尽量避免充分。
示例1 解空间2~1000验证条件各因子之和等于本身约束条件没有可以转化的验证条件穷举方式解空间 约束条件–循环
示例2 在数字100~999中求水仙花数例如13 53 33 153。 解空间100~999验证条件水仙花数约束条件无穷举方式解空间约束条件–循环
示例3 解空间5个变量每个变量范围0~9验证条件满足题目表达式约束条件5个变量各不相同穷举方式解空间约束方式–减小解空间–5重循环如果有值重复则跳出
示例4 对于一个含有6个元素的一维数组该数组每个数只能是0或1将所有情况穷举出来。 例如(0,0,0,0,0,0)、(0,1,0,1,1,0) 注意本题本身就是求解空间
解空间6个数每个数是0或1求全部的0、1序列验证条件情况不重复约束条件无穷举方式解空间约束条件–6重循环
问题建模 转化类二进制数
很明显这题的0、1序列与二进制数类似可以转换问题改为求0~63十进制的二进制间接解题。
属于特殊解法需要惊人的洞察力。
示例5 已知公鸡5元一只母鸡3元一只小鸡1元三只用100元买100只鸡问公鸡、母鸡、小鸡各多少只 原始解空间3个变量x∈[0,20]y∈[0,33]z∈[0,100]验证条件 x y z 100看做约束条件5x 3y z/3 100z / 3为整数z % 3 0 约束条件将验证条件中第一条转换为约束条件也就是z 100 - x -y这与就去掉了一个变量这个变量范围最大能够充分减少解空间。约束后解空间2个变量x∈[0,20]y∈[0,33]穷举方式双重循环
注意谁是验证条件谁是约束条件是跟你的看法有关的。
示例6 求所有的三位数,它除以11所得的余数等于它的三个数字的平方和. 原始解空间数字A三个位是xyzA范围100~999验证条件 A % 11 x2 y2 z2 约束条件由验证条件进一步分析得出需要有经验和洞察力 A % 11 ∈[0,10]x∈[1,3]y∈[0,3]z∈[0,3] 约束后解空间x∈[1,3]y∈[0,3]z∈[0,3]穷举方式三重循环
备注验证方式需要具体问题具体分析。
充分体会不同算法的组合因为一道题目可能背后涉及到多个不同的算法的组合。
