首页 > 其他分享 >设计点灯游戏前的总结

设计点灯游戏前的总结

时间:2022-12-03 21:12:20浏览次数:65  
标签:总结 状态 第一行 游戏 点灯 复杂度 房间 按钮

设计点灯游戏前的总结

因c语言程序设计实践课,恰好选择了对点灯游戏的实现,则我们先来归纳如何去求点灯游戏的方案。

零——前置芝士

点灯游戏简介

一层大楼共有 \(n×n\) 个房间,每个房间都有一盏灯和一个按钮。按动一个房间的按钮后,这个房间和周围四个相邻的房间的灯的状态全部都会改变(由暗变为亮或者亮变为暗)。目标是通过按按钮把所有的灯都点亮(默认情况下全暗)。

点灯游戏规律

我们不难发现以下规律

\(1.\)按偶数次按钮相当于没有按。

\(2.\)无论按按钮顺序如何结果总是一样的。

因此我们有以下结论

\(1.\)对于盘面上的每一个按钮,我们只需要考虑其按开或关的状态。

\(2.\)每一个按钮的状态都是互相独立的,不需要考虑按按钮的顺序。

壹——解决算法

1.完全穷举法,\(O(2^{n^2})\)

对于每一个按钮,只有开和关两种状态。

而如果所有按钮的状态确定了,那么灯的状态也就确定了。

那么,我们就将点灯的问题转化为了对按钮状态的统计,只需要将所有按钮的所有可能的状态列举出来,算出灯所对应的状态并判断灯是否全部点亮即可。

不难发现,一个按钮的状态有开关 \(2\) 种,因此x个按钮的状态则为 \(2^x\) 种。一个房间共有 \(n×n\) 个按钮,因此共 \(2^{n×n}\) 种状态。复杂度则为 \(O(2^{n^2})\) 。

\[注:此处应为 O(2^{n^2}+n^2),因为每个灯的计算还需要O(1),但是n^2远小于2^{n^2},\\故可忽略不记。 \]

2.首行穷举法, \(O(2^n)\)

对于算法1,当 \(n=6\) 时,状态已达到 \(2^{36}=68719476736\) 。所以我们要考虑剪枝或者进一步简化。

比如只按1或2个按钮的状态显然不成立,可以快速排除。

我们将整个房间的每一排从上到下看作有顺序的,那么从第一行开始按按钮。

假设我们已经决定了第一行按钮的状态,此时只有第一行和第二行的灯的状态发生了改变。

由于只有第一行和第二行才会改变第一行灯的状态,那么为了使第一行全亮,而且此时第一行按钮状态已确定,我们只能通过改变第二行按钮的状态来使第一行全亮。

同理,为了使第二行全亮,因第二行按钮已确定,所以要改变第三行按钮的状态,以此类推,整个房间的按钮都被第一行的按钮所确定,而房间里除了最后一行也都是全亮的。

因此,我们不需要把房间里所有的按钮可能的状态列出来,只需第一行。对于每一种第一行的状态,再按上面的步骤计算后面 \(n-1\) 行的按钮状态,然后判断最后一行的灯是否全亮即可。

第一行共 \(n\) 个灯,因此共 \(2^n\) 种状态。复杂度为 \(O(2^n)\) 。

3.完全方程法,\(O(n^6)\)

虽然算法2已经将复杂度降到了 \(O(2^n)\) ,但是当 \(n>30\) 时,这仍是普通计算机无法承受之大。那么我们怎么才能再降一降时间复杂度呢?

在我们从 \(1 \rightarrow 2\) 时,发现了一行灯的状态由它的上一行,这一行和下一行按钮决定,而不是所有按钮,是行与行的关系。

这启发我们是不是对于同一行的按钮或者灯的状态也能找出来关系呢?

答案是肯定的。我们知道,一个按钮可以影响它和它周围4个灯的状态,反过来,一个灯的状态则由它本身和周围最多4个按钮决定的。

\[\color{gold}{——————————奇迹时间到——————————} \]

我们假设方块为按钮,圆圈为灯,黑表示开,白表示关。

再假设一个灯由两个按钮决定状态,那么具体可以表示为:

\[\Box+\Box= \circ\\ \blacksquare+\Box=\bullet\\ \Box+\blacksquare=\bullet\\ \blacksquare+\blacksquare= \circ \]

看起来好像可以转化为数学式子,假设

\[\Box=0,\blacksquare=1,\circ=1,\bullet=1 \]

那么,上面四个等式可转化为

\[0+0=0\\ 1+0=1\\ 0+1=1\\ 1+1=0 \]

欸,这个+好像不是加法,而是(逻辑上的)异或运算 \(\oplus\)

现在,把灯转化为一般情况,那么就由本身以及上下左右四个按钮来决定灯的状态。例如

\[\Box12+\Box21+\Box22+\Box23+\Box32=\circ22 \]

那么,对于房间里所有按钮和灯,我们可以列出 \(n*n\) 个式子,而且因为我们的目的是将所有灯点亮,那么灯的状态应均为 \(\bullet\) ,若此时以按钮为未知数,即为 \(n^2\) 元一次方程组。

我们只需要解方程就可以了(✿◡‿◡)

说到解方程,大家可能立马会想到矩阵。没错,我们把方程式表示成矩阵的形式,然后对矩阵高斯消元即可。

高斯消元的过程等同于求逆矩阵,而所得的矩阵的每一行就表示需要单独点亮一个灯,需要按哪些按钮。

而且可以通过矩阵秩的运算求出多解,这里不过多说明。

高斯消元本身的复杂度是 \(O(n^3)\) ,而矩阵边长为 \(n^2\) ,所以总时间复杂度为 \(O(n^6)\) 。(成功进入线性时代)

4.首行方程法, \(O(n^3)\)

如同从1到2,3到4也是实现了由整体到第一行,不再过多说明。

高斯消元复杂度为 \(O(n^3)\) ,由第一行按钮推算全部的按钮复杂度为 \(O(n^2)\) ,总体为 \(O(n^3)\) 。

5.n不同时解的数量

挖个坑,学完线性代数再回来填。

秩真不明白。

逼零集,点灯游戏和解线性方程组 - 知乎 (zhihu.com)

贰——点灯游戏代码的实现

此处代码并非只是方案实现的代码,也要实现程序设计课程的要求以及程序的美观。

(下周这个时候不见不散。)

标签:总结,状态,第一行,游戏,点灯,复杂度,房间,按钮
From: https://www.cnblogs.com/jasony/p/16948777.html

相关文章

  • 2022-2023-1 20221317《计算机基础与程序设计》第十四周学习总结
    作业信息这个作业属于哪个课程:首页-2022-2023-1-计算机基础与程序设计-北京电子科技学院-班级博客-博客园(cnblogs.com)这个作业的要求在:2022-2023-1《计算......
  • 第十四周学习总结
    #学期(如2022-2023-1)学号(如:20221426)《计算机基础与程序设计》第十四周学习总结##作业信息|这个作业属于哪个课程|<班级的链接>(如[2022-2023-1-计算机基础与程序设计](h......
  • 【面试题】Java中子类和父类静态代码块、非静态代码块、构造函数的执行顺序总结一览表
    在面试的时候,有时候我们会被问到这样的问题:子类A继承父类B,Aa=newA();则父类B的构造函数、父类B静态代码块、父类B非静态代码块、子类A构造函数、子类A静态代码块、子类A......
  • 金蝶Cosmic虚拟机简单使用与总结
    背景知己知彼简单学习下友商发出来的测试软件看看有否对自己现在的工作有所指导也看看对方的部署方式有啥优缺点当然了仅是测试,不是生产软件可能有失真.注意我没......
  • PTA第6~8题目集总结
    PTA第6~8题目集总结目录PTA第6~8题目集总结1.前言2.程序设计分析题目集六7-1电信计费系列1-座机计费题目集七7-1电信计费系列2-手机+座机计费题目集八7-1电信计费系列......
  • 总结数组和对象的遍历方法
    【总结】数组、对象的遍历方法一、for...of与for...in的区别:for...of遍历可迭代对象(Array,Map,Set,String,TypedArray,arguments对象等)遍历可迭代对象定义要迭代的数据......
  • 2022-2023-1 20221307《计算机基础和程序设计》第十四周学习总结
    这个作业属于那个班级 https://edu.cnblogs.com/campus/besti/2022-2023-1-CFAP作业要求 https://www.cnblogs.com/rocedu/p/9577842.html#WEEK14作业目标学习《C语言程......
  • SpringCloud游戏平台改造-Day1
    Day1今天主要的工作是有,新建项目结构(后期可能会根据实际情况修改),实现了登录注册API项目思路目前的项目思路为以下几部分:GameAuth:用来提供用户登录注册接口,认证接口......
  • SpringCloud游戏平台改造-Day2
    Day2今天主要目的是接入SpringSecurity和JWT,不多说开干!Day1Day2接入SpringSecurityStep1实现来自SpringSecurity的UserDetailService接口,实现它的loaduserByUser......
  • jenkins使用与总结
    一.Jenkins下载下载地址=>https://mirrors.jenkins-ci.org/war/更换下载插件的源=>http://updates.jenkins.io/update-center.json配置系统全局变量1)点击系统管理 ......