精华内容
下载资源
问答
  • NOIP题目解析之石子问题

    千次阅读 2018-02-03 17:33:03
    甲乙两人轮流从一堆中石子,最后一颗石子的一方获胜,甲先,请问甲有没有获胜策略?如果有,甲第一步应在哪一堆里多少? 解析: 在解这一道题之前,我们可以先来把问题简化。把五堆石子转化成两堆,石子...

    题目:
    现有5堆石子,石子数依次为3,5,7,19,50.甲乙两人轮流从任一堆中取石子,取最后一颗石子的一方获胜,甲先取,请问甲有没有获胜策略?如果有,甲第一步应在哪一堆里取多少?

    解析:
    在解这一道题之前,我们可以先来把问题简化。把五堆石子转化成两堆,石子数分别为 3 和 5 。探查其规律,我们发现,要使甲获胜,必须使得存在一种可能,就是当甲取了石子之后,到乙开始取石子时,两堆石子的数目要保持一致。这样,不管乙取多少,只要甲在另一堆取走相同的数量的石子,则甲最后必定是最后一个取走最后一颗石子的。(可以在纸上进行一下推算)

    那么,在这个简化的题目上,我们发现很重要两个判定:
    1)要想甲取胜,则当其取石子时,两堆石子必定是保持不平衡的状态,此时甲取走多余的部分,使得两堆石子保持平衡
    2)当乙在两堆数目相同的石子上任意选一堆取一定的棋子时,都必定会使得当前两堆棋子形成一种不平衡的状态(两端数据不对称即为不平衡)

    而我们发现,要使得甲获胜,则必须保证在其取石子前,石子的数据应该是保持不平衡的状态,我们姑且用非负态来表示这种不平衡的状态。反之,我们则用负态来表示平衡的状态。那么前面根据两个判定,我们可以得出另外一个结论:

    要使得非负态转化成负态,只有一种操作,就是保持平衡。而当我们处于负态时,可以通过操作一定的石子改变这种状态

    也就是说,其实我们可以捡走石子的过程,就是不断在改变这两种状态的过程。而只要甲能够保持在这个状态转换的过程中,一直处于将非负态转化成负态的过程即可获胜。

    那么,我们明白了甲要获胜的一个原理,就要继续回到我们的实践操作之——应该取走多少石子。

    因为我们发现,整一个过程就是两种状态的切换,也就是可以和不可以的问题。那当我们面临着两种情况的分析的时候,我们一般使用符合计算机思维的二进制数字进行分析,那什么是二进制呢?这个时候就需要先普及一个知识点:
    基础:二进制
    二进制数字,指的是逢二进一,意思是当我们从0开始数数时,当数到2时,需要向前进一位,而当前位为0。也就是说,二进制数字只有0 和 1这两个数字。它和十进制的区别就在于什么时候进位。我们来看一组二进制和10进制的对比:

    二进制                            10进制
    0                                   0
    1                                   1
    10                                  2
    11                                  3
    100                                 4
    101                                 5
    110                                 6
    111                                 7
    1000                                8
    1001                                9
    1010                                10

    我们发现,同样是数字,在二进制里面就没有出现过2以上的数字,这也是因为我们逢二进一的结果。
    那我们说到要用二进制,可是题目的数据又是十进制的,那我们怎么实现二进制和10进制的转换呢?我们来看一下:

    二进制和十进制的相互转换
    1.十进制转化成二进制:
    当我们要将10进制转化为2进制时,有一个比较简单的方法,我们可以通过筛查的方式实现,什么意思呢?跟着思路走:
    1.在纸上画出一个筛选的“柱子”,从右到左分别是2的0次方—–2的n-1次方。比如:

      256  128   64    32   16   8  4  2  1

    然后,把我们要转换的10进制数取出来(以数字9为例),我们判断这个数字在哪个区间段之间(9在 8->16之间),取最小值(8)。,在8的上面写1。也就是

                                 1 
      256  128   64    32   16   8  4  2  1

    接着,用9减去8,剩余的数字是1,重复上述的操作,直到10进制数最终减为0(在这里,1对应1,在1上面写下1,此时1-1已经等于0),而柱子表示为:

                                 1        1
      256  128   64    32   16   8  4  2  1

    最后:把所有没有1的部分写上0,即

       0    0    0      0    0    1  0  0  1
      256  128   64    32   16    8  4  2  1

    最左边一个1往左的所有0可以删去,即最后的结果为:1001
    2.二进制转10进制
    我们上面介绍了10进制转2进制的方式,那二进制转10进制呢,其实也是通过我们的“柱子”。怎么来呢?
    第一步,把柱子写出来:

    256 128 64 32 16 8 4 2 1

    第二步:把二进制数字的最右边和柱子的最右边契合,以10010为例:

                   1 0 0 1 0
    256 128 64 32 16 8 4 2 1

    第三步:把二进制中1所在的柱子的数字拿出来,相加,就是

    16+2=18

    18就是我们想要的结果~

    好啦,说完了二进制,我们继续回归刚才的问题,我们同样以3 和 5 为例,我们要判断当前棋子的分布式哪一种状态,是不是就是看这两堆石子是不是处于平衡的状态。比如:

    3的二进制是:          011
     则其对应状态应该也是   011 
     而5的二进制是:       101 
     则我们可以很清晰地看到,应该对应的状态
     除于非负态,甲有获胜策略。那要取多少石子呢?
     是不是就是 101 - 011=5-3=2.

    上面的是以两堆石子为例的情况分析。那当我们面临多堆石子的情况时,应该怎么确定应该对应的状态呢?其实我们可以发现,只要我们保证在二进制情况下,每一次甲取完之后,只要各个数位的1的总和为偶数,则不论乙怎么取其中的哪一堆上的数字,甲都能通过取走其他堆的石子,使其继续保持偶数的状态。比如:

    0 1 1
    0 1 1
    
    0 2 2
     我们发现往上往下看,每个
     数位上的1都是偶数个(0也算偶数)

    那么,对于 3 5 7 19 50这5堆石子来说,因为50的数目是最大的,也就是我们有且仅有取这一堆石子的时候,才能保证把剩余的不平衡的状态去掉,变成一个平衡的状态,也就是非负态。所以,我们题目可以理解为:
    当目前有3 5 7 19这四堆石子时,添加多少石子可以使其变成负态。即:

    数字                                   对应的二进制数
    3                                         00011
    5                                         00101
    7                                         00111
    19                                        10011 
    
    个数位的1的个数:                           10234
    那我们的对应状态
    就应该是(奇数为1,偶数为0):               10010                                

    也就是说,要使得当前状态为负态,则第五堆的石子数量应该是(10010),转化成10进制数,就是18。
    也就是说,当甲第一次在50个石子里面取(50-18=32)个石子时,能够使得当前的状态为负态。也就是必胜的策略。解题完毕~~~

    展开全文
  • 要证明的问题:  前提条件:在有向无环图中...(强连通图:任取两个不同的顶点a和b,a都可以到达b) 要证:当前是强连通图, 即证:任取顶点 i 、j (i和j是不同顶点),i可到达j, 即证:假设i不可到达j,必产...

    要证明的问题:

           前提条件:在有向无环图中(即自己本身是不是强连通的不知道,但其任何子图都不是强连通的)

           待证命题:不存在入度为0的点  ∧ 不存在出度为0的点 => 该图是强连通图。

    (强连通图:任取两个不同的顶点a和b,a都可以到达b)

    要证:当前是强连通图,

    即证:任取顶点 i 、j (i和j是不同顶点),i可到达j,

    即证:假设i不可到达j,必产生矛盾。

     

    那么就用假设法,假设i不可到达j:

    看到达j的路径:看j的上1个点,上2个点,……,上n个点(由于前提条件有说:不存在入度为0的顶点,所以j至少有上1个顶点);

    再看i走出去的路径:看i的下1个点,下2个点,......,下m个点(由于前提条件有说:不存在出度为0的顶点,所以i至少有下1个顶点);

     

    因为不存在入度为0的顶点,所以j(-n)顶点必有其来路。由于根据假设i不可到j,所以其来路只能在链(1)中。但是如果这样,则链(1)中有环,环是强连通分量,与条件“所有点的任何真子集都不是强连通分量”相矛盾。所以j(-n)顶点的上一顶点只能来自链(2)。(同理,若通过说明 i(m) 顶点的下一顶点必须来自链(1)也可以找到矛盾)

     

    所以,i可到达j;

    <=>假设失败;

    <=>该有向图是强连通图。

     

    所以结论是,如下命题是真命题:

    (前提条件:在有向无环图中)

    命题1:不存在入度为0的点  ∧ 不存在出度为0的点 => 该有向图是强连通图

    命题2:该有向图是强连通图 => 不存在入度为0的点  ∧ 不存在出度为0的点

    那么在相同的前提条件下,它们的逆否命题也是真命题

    命题3(命题1的逆否):该有向图是非强连通图 => 存在入度为0的点 ∨ 存在出度为0的点

    命题4(命题2的逆否):存在入度为0的点 ∨ 存在出度为0的点 => 该有向图是非强连通图

    展开全文
  • 定理1:连通多重图中存在欧拉回路当且仅...在图中任取一点,以该点作为起点,沿着欧拉回路走,当前顶点的出度为1,然后经过其它的顶点,注意到如果欧拉路径经过一个顶点(包括起点),它必然离开这个点,这样出入度...

    转载自https://www.cnblogs.com/xpjiang/p/4396106.html

    定理1:连通多重图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。

    首先,我们来证明充分性,即存在欧拉回路则图中的所有顶点的度数必然为偶数。在图中任取一点,以该点作为起点,沿着欧拉回路走,当前顶点的出度为1,然后经过其它的顶点,注意到如果欧拉路径经过一个顶点(包括起点),它必然离开这个点,这样出入度之和为偶数,直到所有的边逐一被走过,回路的终点在起点处结束,使得起点的入度加1,这样经过起点的度数和变成偶数,欧拉回路结束(注意到我们未加说明的假设了边的个数是有穷的,因此这个过程必然结束)。

    其次,我们来证明必要性,即如果连通图中所有顶点的度数为偶数,则必然存在欧拉回路。我们通过构造性的存在性证明来说明这一点(这里有一些证明方法的相关介绍)。首先,我们在连通图中找寻一条回路(回路的选取是任意的并且总是能找到的,由上述充分性的证明可以有效的说明这一点),如果这条回路就是欧拉回路,那么结论已然成立了,否则,我们删除掉该回路中的所有边,出现孤立的顶点就忽略它,那么子图(不一定是连通的,并且仍然满足所有顶点的度数都是偶数的性质)与删除掉的回路一定有公共顶点(图的连通性保证了这一点),以该点作为起点继续找寻回路,然后删除,续行此法,直到所有的边都被删除为止(同上述充分性的证明中一样,边的个数的有穷性保证了这个过程必然结束),所有这些删除的回路连接起来就构成了一条欧拉回路。

    至此,我们完成了欧拉回路存在性的充要条件的证明,并且应当引起注意的是在构造性的存在性证明中我们给出了一种找寻欧拉回路的算法过程。

    接下来,我们证明下述定理。

    定理2:连通多重图中存在欧拉通路且不存在欧拉回路当且仅当连通图中有且只用两个顶点的度数为奇数。

    仍然先来证明充分性,即存在欧拉通路则图中有且只有两个顶点的度数为奇数,其他顶点的度数皆为偶数,注意到由于起点和终点是不同的,因此欧拉通路的起点和终点必然是两个奇数度的顶点,此外,不可能再有其他的奇数度的顶点了,因为我们沿着欧拉通路的起点走开来,只要经过一个顶点必然离开该顶点,一条入度边搭配一条出度边,共同为该顶点贡献偶数度,直到到达终点为止(当然,也可能再离开,只要终点还有边没有被走过)。

    接下来,我们来证明必要性,即连通图中有且只有两个奇数度顶点,则必然存在欧拉通路,怎么来证明这一点呢?一种非常巧妙的方式是把欧拉通路做成欧拉回路,换句话说,我们连接两个奇数度顶点,这样连通图中所有顶点的度数均为偶数,由刚刚证明的定理1可知,该连通图存在欧拉回路,注意到只需把我们自己增加的那条辅助边删除,便证明了欧拉通路的存在性,我们再一次借助构造性的存在性证明来证明了这一点。

    展开全文
  • 注意到 我们由此定义一般的 矩阵A的广义逆矩阵定义1:设 ,若存在 满足以下条件:(1) (2) 则称 是 的广义逆矩阵事实上,可逆矩阵的逆矩阵就是它的一个广义逆矩阵我们尤其关注广义逆矩阵的存在性,由此可得定理1:...

    可逆矩阵在线性代数中地位重要,应用方便。但遗憾的是,不是所有的矩阵都是可逆矩阵。我们有必要对矩阵的逆进行推广,使得每个矩阵甚至是非方块的矩阵都有广义的逆。

    对于可逆矩阵A,注意到

    我们由此定义一般的

    矩阵A的广义逆矩阵

    定义1:设

    ,若存在
    满足以下条件:

    (1)

    (2)

    则称

    广义逆矩阵

    事实上,可逆矩阵的逆矩阵就是它的一个广义逆矩阵

    我们尤其关注广义逆矩阵的存在性,由此可得

    定理1:任意

    矩阵
    都有广义逆矩阵

    证:设

    ,则必定存在
    阶可逆矩阵
    以及
    阶可逆矩阵
    ,使得

    ,其中
    ,
    分别是任意
    矩阵以及
    矩阵,则这样的
    就是
    的广义逆矩阵

    上述证明过程提供了求广义逆矩阵的一种方法,从证明过程中也可以看出广义逆矩阵不一定唯一

    例1:对于矩阵

    ,有:对任意的复数
    ,
    都是
    的广义逆矩阵

    我们可以进一步加条件,使得矩阵的逆的推广保证存在唯一性。早在1920年,Moore开始研究广义逆矩阵,但三十多年来广义逆矩阵得不到重视。直到1955年Penrose在前面所叙述的两个条件下增加两个条件,定义了所谓的Moore-Penrose广义逆矩阵,简称M-P广义逆矩阵,这样定义的M-P广义逆矩阵满足存在唯一性

    定义2:设

    ,若存在
    满足以下条件:

    (1)

    (2)

    (3)

    (4)

    则称

    Moore-Penrose广义逆矩阵,简称M-P广义逆矩阵,也称为伪逆矩阵,记为
    ,以便与通常的逆矩阵加以区分。这里
    表示
    共轭转置矩阵

    事实上,可逆矩阵的逆矩阵就是它的一个M-P广义逆矩阵

    定理2:

    ,则
    的M-P广义逆矩阵存在且唯一

    证:存在性:设

    ,则必定存在
    阶可逆矩阵
    以及
    阶可逆矩阵
    ,使得

    矩阵
    ,
    矩阵

    是列满秩矩阵,
    是行满秩矩阵,且
    (事实上,任意矩阵都能分解为一个列满秩矩阵与一个行满秩矩阵的乘积,这种分解叫做满秩分解)

    此时

    ,
    均为
    阶可逆矩阵(提示:验证
    ,可仿照实矩阵中二次型的方法,利用复矩阵中共轭二次型予以证明)

    ,则

    同理,

    存在性得证

    唯一性:若

    也是
    的M-P广义逆矩阵,则

    唯一性得证

    定理2中存在性的证明已经提供了利用满秩分解求M-P广义逆矩阵的方法。

    例2:

    的M-P广义逆矩阵

    解:取

    ,
    (
    ,
    是一系列初等矩阵的乘积,对
    作初等变换即可得到),而
    ,令

    ,且
    列满秩,
    行满秩,代入公式得

    下一篇文章我们将继续探究M-P广义逆矩阵(也称伪逆矩阵)的相关性质以及应用。

    展开全文
  • 作为副产品,我们还证明引力和电磁仅决于共形Killing方程组的二阶射流(1922年被E. Cartan称为“兴高采烈”),因为在兴高采烈的束中任何具有值的1形式都可以分解唯一地包含在直接和(R,F)中,其中R是对称协变2...
  • 游戏的2021-01-10 21:25:40看了一篇关于C/C++浮点数的博文,在Win32下,把int, 指针地址,long等4字节整数赋给一个double后,再用该double数赋给原始类型的数,得到的结果于最初的数值一致,即不存在...
  • 因为想实现分布式时可以在另一台电脑上到相应客户端 为了保持同步,是不是对一个客户端的任一属性更改时都要set一次?这样做会不会很影响效率? 初次接触redis,很多地方不懂合不合理,请指教。
  • 题目 2001年9月11日,一场突发的灾难将纽约世界贸易中心大厦夷为平地,Mr.... F可以从这N块水晶中任取M(1≤M≤N)块来搭建。但是他不知道能否使两座塔有同样的高度,也不知道如果能搭建成一座...
  • 一道网易2015年的内推笔试题实现采用java和c++ ,超详解,外加推理理解;思路:可以考虑选出的在2n个数中找到n个数使的这n个数的和...参数本身可以0和1,意思是如果存在2n个数中存在n个数的和为m ,则将其置为1;首...
  • 有沒有必要創建自己的功能,而且很坦率地說,它似乎浪費了現在可以用已經存在的sql函數很容易地完成這個務。必須小心處理馬虎數據輸入。這裏是另一種方式來實現自己的既定目標:with name_list as(select ' Parisi...
  • 任给N堆石子,两人轮流从任一堆中任取(每次只能取自一堆),规定每方每次最多取K颗,取最后一颗石子的一方获胜.问先取的人如何获胜? 巴什博奕和尼姆博弈的综合。 令Bi=Mi mod(Li+1) 定义T‘=B1 xor B2 xor ... xor ...
  • 向量空间中的Fourier变换:DFT DFS DTFT

    千次阅读 2013-10-24 19:04:33
    持久的动态系统一定存在振荡现象。从直观理解来说,不沿着圆运动的物体终将...任取两个不同的基计算内积,化简为等比数列求和,分子为0,即正交。不过它们不是标准正交,乘以1/sqrt(N)标准化因子后才是标准正交基。 W
  • 题意:平面上有n个红点,m个黑点,是否存在一条直线,使得任取一对红点和蓝点都在直线的异侧,这条直线不能穿过红点或者黑点。 题解:分成两个点集,分别求凸包,然后判断两个凸包是否有交集,判断如下: 任取红...
  • 对于一个已经排序好的数组,一定有该特性:任取一个数字,其左边的数字(若存在)全部小于该数字,其右边的数字(若存在)一定大于该数字。 那么我们便可以对一个未排序数组,任取一个数字(中心数),将小于它的放...
  •  有n个红点和m个蓝点,问你是否存在一条直线,使得任取任取一个红点和一个蓝点,都在直线的两边?这条直线不能穿过红点或蓝点. 分析:  先求出红点的凸包和蓝点的凸包,则分离两个点集的充要条件是分离两个凸包.  
  •  有n个红点和m个蓝点,问你是否存在一条直线,使得任取任取一个红点和一个蓝点,都在直线的两边?这条直线不能穿过红点或蓝点. 分析:  先求出红点的凸包和蓝点的凸包,则分离两个点集的充要条件是分离两个凸包.  .....
  • n个红点,m个蓝点,是否存在一条直线,使得任取一个红点和一个蓝点都在直线的异侧?这条直线不能穿过红点或者蓝点 解题思路: 先求出红点和蓝点的凸包,如果这两个凸包是相离的,那么一定能找到一个满足条件的...
  • 然后我捞点干货出来写在这 首先是超实数的一些定义定理(我用我自己的话来说了) ①定义 x={XL | XR},大写X... XR (我下面都用这种写法,表示XL中任取,XR中任取) 或者 XL或XR 不存在也行 ②对 x={XL | XR},y=...
  • 任取一个数组元素放入新数组,遍历剩下的数组元素任取一个,与新数组的元素一一比较,如果有不同的,放入新数组。 遍历数组,取一个元素,作为对象的属性,判断属性是否存在 1. 删除后面重复的: function ov(arr)...
  • 3.任取一个数组元素放入新数组,遍历剩下的数组元素任取一个,与新数组的元素一一比较,如果有不同的,放入新数组。 4.遍历数组,取一个元素,作为对象的属性,判断属性是否存在 1. 删除后面重复的: function ov1...
  • 凸集与凸集分离定理、Farkas引理凸集定义:凸集注意凸集的定义,任取两点满足某个条件为凸集:证明是凸集的目标有了凸集的性质也有了,可以利用凸集性质(逐个证明)(1)分析:任取,因为是要证明是凸集也就是要对于...
  • 这里 可用任意范数代替,因为:[有限维空间上范数等价] 设 是 上的范数,则存在常数 ,使得 ,其中 是欧氏范数。...任取 ,有 。于是 关于 Lipschitz连续,在紧集 上取到最小值 。 谱半径Gelfand公式记...
  •  有n个红点和m个蓝点,问你是否存在一条直线,使得任取任取一个红点和一个蓝点,都在直线的两边?这条直线不能穿过红点或蓝点. 分析: 刘汝佳训练指南>> P274例题8  先求出红点的凸包和蓝点的凸包,则分离两个点集的...
  • 机器学习之向量空间的基本概念

    千次阅读 2018-10-17 15:48:12
    向量空间:如果在一个空间中,任取若干个向量进行相加或数乘,其计算...子空间:在一个向量空间V中,如果存在一个空间S,其中任取若干个向量进行相加或数乘,其计算结果仍然在空间S中,则该空间S称为向量空间V的子...
  • 最大权闭合子图

    2018-08-16 16:58:59
    对于一个有向图G,存在点集合V,任取点u属于V,u的出边的另一个点也属于V,则为闭合图。 理解:任取一起点,终点必定是无出度的点。   最大权闭合子图: 当每个点有一个权值w(有正有负),点权和最大的闭合图...
  • ... 题意:一个公司要裁员,裁员可以给公司省下其工资及奖金。...闭合图:对于一个有向图G,存在点集合V,任取点u属于V,u的出边的另一个点也属于V,则为闭合图。 理解:任取一起点,终点必定是无出度的点。...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 238
精华内容 95
关键字:

存在任取