文章插图
非门电路
文章插图
或门电路这是两个「简单」的逻辑门 ， 分别实现了将信号翻转的非门和将两路信号做或操作的或门 。在另一个也很著名的沙盒游戏——《我的世界（Minecraft）》里面 ， 玩家也可以通过游戏中的材料 ， 红石（其实在此之前的 Windows 10 操作系统的每一年的更新代号就是用红石来命名） ， 实现各种各样的复杂逻辑操作 ， 更有玩家利用红石在 Minecraft 里制造出了真正能运行的计算机 。。。
文章插图
红石计算机 ， 具有完整的寄存器 ， 加法器等部件 [6]算了 ， 我已经不敢想象扫雷会变成什么样了 。。。判断有没有解都是一件很难的事情Find solution回到文章最开始 ， 我们人去破解一个扫雷问题的话 ， 很容易就会死掉了 ， 那把这个问题交给计算机来做会怎么样？然而很遗憾的是 ， 一般情况下 ， 计算机目前对扫雷这个问题还是无能为力 。。。
文章插图
难过稍微值得庆幸的是 ， 在我们平时玩的比较小的棋盘下 ， 计算机还可以通过搜索得到答案 。为了了解计算机处理问题难度的几个级别 ， 有必要先知道一个概念——多项式时间 。对于同一个算法 ， 根据处理问题大小的不同 ， 计算机一般来说需要不同的时间进行计算 。用最直观的例子来说 ， 小明要去洗衣服 ， 他洗 1 件衣服的时间为 2 分钟 ， 洗 5 件衣服的时间为 10 分钟 ， 洗 10 件衣服的时间为 20 分钟 ， 处理问题的时间随问题规模的变化为线性关系 ， 一次多项式 。现在我们假设小明还是要洗衣服 ， 只不过现在的衣服比较特殊 ， 他洗 1 件这种衣服的时间为 2 分钟 ， 但洗 5 件的时间变为 32 分钟 ， 洗 10 件的时间变为 1024 分钟 ， 这个时候就是指数关系的 ， 而不再是多项式了 。评价一个算法 ， 随着问题规模的增大 ， 计算时间怎么增长是一个十分重要的指标 。
文章插图
在计算机里面 ， 对于多项式级别的时间 ， 我们还是认为很快的 。如果把问题按照求解的难度来进行分类的话 ， P 是指能够用多项式时间求解的问题 ， 俗话说就是算起来很快的问题 。NP是指算起来不一定快 ， 但是任何答案我们都可以检查起来很快的问题 。NP 完全问题 ， 是比所有 NP 问题都要难的 NP 问题 。虽然人们有个美好的想法 ， 总觉得验算起来很快的应该可以找到办法让他算起来很快 ， 但目前还是个未知数 。。。[7]很不幸 ， 求解一个扫雷游戏的解 ， 正好是一个 NP 完全问题——在能够轻松验证结果是否正确的问题里面最难的那一类 。这一类问题目前为止人们还没有发现多项式时间的求解算法 ， 通常只有指数级甚至阶乘级的搜索算法来解决 。
文章插图
用来显示液晶数字的逻辑电路 。我们可以很方便地一个一个试 ， 但是反过来却很难 ， 尤其是在这个逻辑电路非常庞大的时候扫雷游戏属于一个如此困难的问题 ， 其原因就出在上一章到的 ， 可以把扫雷游戏看做一个个逻辑门进行运算的逻辑电路 。给定一个逻辑电路 ， 在已知输出结果的情况下 ， 能否确定每个输入的值？这个问题被称为 SAT 问题 ， 是世界上第一个被证明其为 NP 完全的问题 。[8]这种问题验证起来非常容易 ， 你只需要把结果代入到逻辑电路中 ， 马上能知道是否符合要求 ， 但倒过来想要计算符合结果的输入就极端地麻烦 。求解扫雷游戏的结果 ， 利用那些构造的逻辑门 ， 恰恰等价于求解 SAT 问题 。[9]扫雷还和渗透有关系Precolation
以上关于本文的内容，仅作参考！温馨提示：如遇健康、疾病相关的问题，请您及时就医或请专业人士给予相关指导!
「四川龙网」www.sichuanlong.com小编还为您精选了以下内容，希望对您有所帮助：- 面松石能盘玩出来吗 绿松石如何盘玩
- 会玩的夫妻婚姻更幸福
- 普通人发抖音赚钱的方法 玩游戏怎么赚钱
- 钢铁雄心3好玩吗 钢铁雄心3怎么玩
- 经典斗地主玩法规则 斗地主规则
- 2021年电竞手机排行榜 玩手游用什么手机牌子好
- 空调安装还有口诀？ 空调的安装
- 八达岭长城实用游玩攻略 八达岭长城游玩攻略
- 广州10个著名的景点 广州好玩的地方有哪些
- 超实用的夫子庙游玩攻略！ 夫子庙游玩攻略