必赢56net手机版_亚洲必赢手机入口_必赢亚州手机网站
做最好的网站

美妙的德布鲁因种类,数学魔术【必赢56net】

相关的果壳网小组

  • 我爱解谜
  • 密码学

梅花8,梅花A,梅花2,梅花4,黑桃A,方片2,梅花5,黑桃3,方片6,黑桃4,红桃A,方片3,梅花7,黑桃7,红桃7,红桃6,红桃4,红桃8,方片A,梅花3,梅花6,黑桃5,红桃3,方片7,黑桃6,红桃5,红桃2,方片5,黑桃2,方片4,黑桃8,方片8。

必赢56net 1

接下来魔术师会让最后一个人拿走此时这叠牌最上面的一张,再把这叠牌给旁边的人,同样拿走最上面的一张,最后每个人手中都有一张牌。然后魔术师会说:“我看不到你们任何一个人的牌,但现在用意念已经知道你们每个人手中的牌是什么了。”很多人心里一定会想:这也太神奇了吧?魔术师又说:“首先请手中是黑色牌的童鞋站起来。”紧接着他就开始一一说出每个人手中的牌是什么:“你的是黑桃5,你的是梅花8……对于剩下手中是红色牌的童鞋,你的是红桃3,你的是方片……”最后把每个人的牌翻开一看,全部命中,无一错误。

所以32张牌的初始顺序如下:

魔术过程:

魔术师戴上眼罩,并请一位观众上台按照要求完成一系列操作:先从那叠牌里任意抽一张,记住抽到的牌是什么,并且向台下观众展示。需要注意的是,如果抽到的是A,要求把A放回去,重新抽一张,直到牌不是A为止。

在观众选好牌后,魔术师把观众抽到的那张牌随意地插到剩下那叠牌里,然后洗牌(当然只是做做样子)。期间魔术师戴着眼罩,所以他是什么都看不见的。

接着,魔术师把牌还给观众,要求观众按照下述规则再次洗牌:

按照先前抽到牌的牌面数字,比如3,从这叠牌最上面的一张牌开始,把第1张和第2张放到牌的最下面,把第3张翻过来放在这叠牌的最上面。然后再从这一张翻过来的牌开始,将第1张、第2张放到最下面,第3张翻过来……以此类推,直到把这7张牌全部翻面为止。

当观众完成任务之后,魔术师摘下眼罩,和观众一起检查这些牌,确认7张牌还是原先的7张,没有被掉包。确认完毕,魔术师按住观众左手一阵猛揉,故作冥思状,一通表演后果断猜出观众抽到的牌,在众人的惊讶与掌声中鞠躬致谢,魔术表演完美谢幕。

你看出其中的奥秘了吗?

参考资料:Magical Mathematics by Persi Diaconis & Ron Graham 

魔术能成功实施,必要条件就是要先记住32张牌的初始位置。然后切牌的时候暗示观众牌是洗过的。最后根据观众拿了黑色花色的牌举手,快速定位到5个连续的牌位于32张牌的哪个窗口,然后说出这5张牌的花色和点数。

 

魔术揭秘

这是一个很经典的魔术,不仅可以骗过醉醺醺的酒鬼,就连魔术师俱乐部里的专业魔术师、美国数学学会晚宴上的数学家们都对这个魔术毫无思绪,猜不出其中的原理。

表演的关键点在魔术师号称他已经知道每个人手中的牌是什么的时候。其实他对每个人手中的牌一无所知,在“首先请手中是黑色牌的童鞋站起来”之后他才知道了所有人手中的牌,他利用各位观众手中红牌、黑牌的排列顺序作为线索,推断出大家手中是什么牌。

具体来说,表演这个魔术需要两件道具:一是事先按顺序排列好的一叠牌,可以从一副扑克牌中取出数字1到8共32张,然后把它们按照下面的顺序排列(背面向上,由上到下)

梅花8,梅花A,梅花2,梅花4,黑桃A,方片2,梅花5,黑桃3,方片6,黑桃4,红桃A,方片3,梅花7,黑桃7,红桃7,红桃6,红桃4,红桃8,方片A,梅花3,梅花6,黑桃5,红桃3,方片7,黑桃6,红桃5,红桃2,方片5,黑桃2,方片4,黑桃8,方片8

这样排列的巧妙之处在于:即使被切过牌,也可以保证任意抽出五张连续的牌,其中黑色和红色的排列顺序一定是唯一的(如果黑色牌是0,红色牌是1,这些长度为5的二进制序列一定是互不相同的)。

另外一件道具是一张表格,可以把它藏在手心里,也可以把它藏在一本书里,当然还可以把它死记硬背下来。对于以上的扑克牌排列顺序,对应的表格是这样的:

必赢56net 2

假如在魔术中,你发现按照拿牌的先后顺序,第二位和第四位观众站起来了,则说明各观众手中的牌分别是红黑红黑红,二进制形式就是10101,按照表格一查,立刻就可以“感知到”这五个人手中的牌分别是方片5、黑桃2、方片4、黑桃8、方片8。

这一神奇魔术背后的数学原理是二进制的De Bruijn 序列,从这样的序列中任意取出相邻n个数(在我们的魔术中n=5),它们的二进制排列一定不相同。下面我们把最开始的那叠牌写成二进制形式(黑色0,红色1),大家可以验证一下是否如此。:

0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1

对于同样的32张牌,De Bruijn 序列自然不是唯一的,可以有很多种排列方法,不同的排列方法也对应着不同的“解密表格”。De Bruijn 序列长度也可以更长,随之变大的是每次需要取出相邻牌的个数(n)。对于不同数量的观众,我们需要准备不同数量的牌。5个观众比较适中,如果给一个班级所有人一起表演,尽管效果无比震撼,但是扑克牌估计要用麻袋来装了。

将所有的排列组合列举出来,如上图。当魔术师让黑色或者红色的牌的人出列的时候,就能确定到具体是哪一种组合了。于是也就可以直接说出每个人手上拿的是什么牌了。

魔术揭秘:

这个魔术的关键在观众“洗牌”部分。如果多试几次就会发现,无论隔几张翻一次牌,永远不会出现将一张牌从背面朝上被翻到牌面朝上,再翻回到背面朝上的情况,在整个过程中,所有的牌都只会被翻一次。

只有牌数是质数张的一叠牌才有这样的特性,因为一个质数n和从2到n-1之间的所有整数都是互质的。如果要将一个牌面被翻过来的牌再翻回去,一定恰好要移动n次牌(n为牌的数量,是质数),假设抽到的数字为p,则每次要移动(p-1)张牌到最下方,由于质数n不能被(p-1)整除,所以,无论观众抽到的数字是多少,从第一张被翻开的牌开始到翻牌结束,最上方的牌再次回到最上方的情况不会出现。到最后一张背面朝上的牌翻成正面为止,一定只翻了7次牌(因为一共只有7张牌)。 这就是选择7张牌而不是6张,8张或9张的原因。

我们再来单独看“洗牌”时扑克牌排列顺序的调换过程。魔术中的每次操作只是把几张牌从牌的最上面搬到牌的最下面,如果将7张牌按照圆的形式排列,这种操作就相当于旋转这个圆,相邻牌之间的相互顺序并没有变。当“搬牌”的总张数是7的倍数(相当于使圆旋转360度的倍数)时,这副牌在成一列展开时,顺序就会恢复原样。假设观众抽到的数字是p(2=必赢56net 3

说到这里,魔术师的秘密就全被揭开了。魔术师想知道观众抽的牌是哪一张也就不是一件难事,只要在最开始假装把抽到的牌任意放进右手那一叠牌中的时候,记住它被放在了第几张的位置,在最后和观众一起“验证”7张牌时锁定那个位置,直接一看,自然就知道观众抽到的牌是什么。至于把逮着观众的手来回揉捏的环节,如果观众是漂亮mm嘛,一定要保留,如果观众是个大叔……免掉也无所谓了。

 

你有没有看过这样一个扑克牌魔术:魔术师在五六个人好奇的注视下,拿来一叠扑克牌,说:“首先大家检查一下这叠牌是不是不同的花色和点数。”然后对一位观众说:“您可以从这叠牌的上方拿任意数量的牌放到这叠牌的下方(专业一点可以称作切一下牌)。”第一位观众照做之后,把这叠牌递给旁边的人,旁边人同样切一下牌之后,再递给下一个人,轮到最后一个人切完牌的时候,这副牌的顺序已经被完全打乱了。

6. 德布鲁因序列

这种方式的原理也是哈希,但是这种方式比单纯的哈希要快,因为它避免的取余的计算。

如果 x 为32位,那么哈希函数可以构造成下面这样:

(x * 0x077CB531) >> 27 

0x077CB531 是32位的德布鲁因序列之一。

构造这样一个哈希函数有2点优点:

  1. 由于这个二进制数是我们筛选出来的特殊的二进制数,原来的二进制数的末尾的1被我们筛选出来了。它本身其实就是二的次方,所以任何一个数字乘以这个特殊的二进制的数,都相当于左移运算。左移的位数就是原二进制数末尾1所在的位子。
  2. 德布鲁因序列相当于是全排列,枚举了所有的情况。所以它的两两子序列之间肯定不相同,这就是完美的哈希。

最后又移动27位是为了保证能取出开头的5位。

在 Go 的原生代码包中,有一个 nat.go 文件,在这个文件里面有这样一段代码:

const deBruijn32 = 0x077CB531var deBruijn32Lookup = []byte{ 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,}const deBruijn64 = 0x03f79d71b4ca8b09var deBruijn64Lookup = []byte{ 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4, 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5, 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11, 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,}

在这个文件中,同样有一个函数在解决上述的问题,只不过它换了一个角度。

求一个二进制数的末尾1所在的位置,其实可以转化为求这个二进制数末尾连续0有多少个的问题。

这个经典的问题在图灵奖获得者 Donald Ervin Knuth 的著作 《计算机程序设计艺术》的第四卷,section 7.3.1 上有,感兴趣的同学可以看看这个问题。

// trailingZeroBits returns the number of consecutive zero bits on the right// side of the given Word.// See Knuth, volume 4, section 7.3.1func trailingZeroBits int { // x & -x leaves only the right-most bit set in the word. Let k be the // index of that bit. Since only a single bit is set, the value is two // to the power of k. Multiplying by a power of two is equivalent to // left shifting, in this case by k bits. The de Bruijn constant is // such that all six bit, consecutive substrings are distinct. // Therefore, if we have a left shifted version of this constant we can // find by how many bits it was shifted by looking at which six bit // substring ended up at the top of the word. switch _W { case 32: return int(deBruijn32Lookup[(*deBruijn32)>>27]) case 64: return int(deBruijn64Lookup[(*(deBruijn64&_M))>>58]) default: panic("Unknown word size") } return 0}

这里还需要解释一下 deBruijn32Lookup 和 deBruijn64Lookup 数组里面初始装入的数字到底代表了什么意思。

deBruijn32 和 deBruijn64 分别是德布鲁因序列。两两之间的子序列都是不相同的,并且所有的子序列构成了一个全排列。

const deBruijn32 = 0x077CB531// 0000 0111 0111 1100 1011 0101 0011 0001const deBruijn64 = 0x03f79d71b4ca8b09// 0000 0011 1111 0111 1001 1101 0111 0001 1011 0100 1100 1010 1000 1011 0000 1001

我们用下面的哈希函数构造一个“完美”的哈希函数。

h = (x * deBruijn) >> 

n 是二进制数的位数。于是也就可以理解 (deBruijn32)>>27 和 ((deBruijn64&_M))>>58 是什么意思了,这就是在算对应的哈希值。

那么数组里面存的值就是我们最终的结果了,即末尾1所在的位置或者末尾连续有多少个0 。

其实数组里面存的数字是这样算出来的:

void setup{ int i; for(i=0; i<32; i  ) index32[ (debruijn32 << i) >> 27 ] = i;}

即把算出来的哈希值作为下标,对应下标存储的值是左移的位数。这个左移的位数就是我们要的结果。所以先算哈希值,然后通过数组取出哈希值里面存储的值即为我们的结果了。

举例,假设原二进制数是64位的

0011011011101100110011001001001111110011000000000000000000000000

x & -x 以后的结果

1000000000000000000000000

经过这一步以后就把二进制的末尾1截取出来了。剩下的问题就是要找这个1从右往左数在第几位了。

用64位的德布鲁因序列来求:

0000001111110111100111010111000110110100110010101000101100001001

用上面 x & -x 算出来的结果乘以这个64位的德布鲁因序列,就相当于左移几位,直接看0的个数,我们可以看出来是左移24位:

0111000110110100110010101000101100001001000000000000000000000000

最后取出这个数的前6位就是我们要的结果了。lg 64 = 6,所以取出前6位,011100 。

// findLSBSetNonZero64 returns the index (between 0 and 63) of the least// significant set bit. Passing zero to this function has undefined behavior.//// This code comes from trailingZeroBits in https://golang.org/src/math/big/nat.go// which references (Knuth, volume 4, section 7.3.1).func findLSBSetNonZero64(bits uint64) int { return int(deBruijn64Lookup[((bits&-bits)*(deBruijn64&digitMask))>>58])}

上述程序和之前的实现方式完全一致,只不过这里函数名的意义代表查找末尾1的位置,和查找末尾有多少个0,完全一致!

上述代码也是 Google S2 中的源码,它也是直接利用德布鲁因序列来查找末尾1所在的位。

总结一下,数组的下标和我们构造的哈希函数值相对应,哈希函数的值其实就是对应德布鲁因序列的前几位。而末尾1所在的位置被我们处理成了一个特殊的二进制数了,这个数的1所在的位置就是原二进制数末尾1所在的位置。这个特殊的二进制数末尾1后面全是0,所以任何数乘以它以后都相当于左移末尾0的个数。于是末尾1所在的位置就被转换成德布鲁因序列左移多少位的问题了。德布鲁因序列左移多少位,取出前几位,生成的数字就是哈希函数的值,它又和数组的下标关联起来了。于是最后查找数组里面对应哈希值位里面存的值就是我们要的结果了。

De Bruijn 序列的奇妙不仅体现在魔术上。我们还可以使用它为机器人做路标定位:将两种不同颜色的小方块排成一条长线摆在机器人行进的路上,机器人只要识别出自己前后的几个方块是什么颜色,既不需要GPS,也不需要高精度探测仪,就可以知道自己走了多少米。

研究人员利用 De Bruijn 序列设计了每次可以产生一个用于加密的不同随机数字的简单电子元件“反馈移位寄存器”,上一个随机数字和下一个随机数字之间只改变一个数位和移位一下就可以,电路构造非常简单。

必赢56net 4

在测量工程上,德布鲁因序列还可以用在基于光栅投影模式的三维形貌快速测量系统研究中。

必赢56net 5

在基因工程中,德布鲁因序列可以用在基因组重复区域组装上。

在医学研究中,德布鲁因序列通常用于神经科学和心理实验以检测刺激序列对神经系统的影响,其可专门用于功能磁共振成像。

在人工智能算法中,神经网络时间序列预测也有德布鲁因序列的身影。

Reference:

Wiki De Bruijn sequenceWolfram Mathworld de Bruijn Sequence The On-Line Encyclopedia of Integer SequencesDe Bruijn cycle generatorOn line Sequence Generatorde Bruijn cycles for neural decodingDe Bruijn sequence 《Using de Bruijn Sequences to Index a 1 in a Computer Word》

空间搜索系列文章:

空间搜索系列文章:

如何理解 n 维空间和 n 维时空 高效的多维空间点索引算法 — Geohash 和 Google S2 Google S2 中的 CellID 是如何生成的 ? Google S2 中的四叉树求 LCA 最近公共祖先 神奇的德布鲁因序列 四叉树上如何求希尔伯特曲线的邻居 ?

GitHub Repo:Halfrost-Field

Follow: halfrost · GitHub

Source:

这个魔术的道具是红桃A到红桃7七张扑克牌,把它们牌面朝下按数字顺序叠成一叠:

不只是魔术

De Bruijn 序列的奇妙不仅体现在魔术上。我们还可以使用它为机器人做路标定位:将两种不同颜色的小方块排成一条长线摆在机器人行进的路上,机器人只要识别出自己前后的几个方块是什么颜色,既不需要GPS,也不需要高精度探测仪,就可以知道自己走了多少米。

在一列很长的De Bruijn 序列中,中间任意取出n个数字(例如下面序列中的10011),然后向旁边移动一个位置,取出相邻的n个数字(例如下面序列中的00111),它们一定是不相同的,但又有(n-1)个数字是重叠的(0011)。

0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1

0,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1

研究人员利用De Bruijn 序列设计了每次可以产生一个用于加密的不同随机数字的简单电子元件“反馈移位寄存器”,上一个随机数字和下一个随机数字之间只改变一个数位和移位一下就可以,电路构造非常简单。

必赢56net 6

智利的研究人员还曾做过研究,他们设想这个纸牌魔术或许可以和电脑里的数据压缩(例如WINRAR、ZIP、JPEG图片压缩、MPEG视频压缩等)扯上关系。

也许你仅仅为这个魔术的表演效果感到很神奇,但绝对想不到这个魔术背后的原理还可以跨界到如此广阔的领域吧。数学与魔术结合,就是会产生如此奇妙的反应。

这个魔术中我们需要找的是 5 阶完备二进圆排列。答案是存在这样一个满足条件的序列。这个序列也就是文章的主角,德布鲁因序列。

还记得死理性派的“ 数学魔术:托儿也能如此低调 ”吗?我们都知道托儿对于魔术师的重要性,可是如果托不在身边,魔术该怎么演呢?让下面这个数学魔术来告诉你吧。

1. 定义

德布鲁因序列(De Bruijn sequence),记为B,是 k 元素构成的循环序列。所有长度为 n 的 k 元素构成序列都在它的子序列中,出现并且仅出现一次。

例如,序列 00010111 属于B。 00010111 的所有长度为3的子序列为000,001,010,101,011,111,110,100,正好构成了 {0,1} 3 的所有组合。

如果窗口大小为5,5张连续的扑克牌。二进制编码 25 = 32 ,所以需要32张牌。如果窗口大小为6,6张连续的扑克牌,二进制编码 26 = 64,需要64张扑克牌。总共牌只有52张,所以不可能到64张。所以32个人是上限了 。

在整个魔术中,有三个地方比较关键。第一个是参与的人数只能少于等于32 。一副完整的扑克牌中,总共有54张牌,但是除去2张鬼牌(因为他们花色只有2种),总共就52张牌。

数学中存在这样一个序列,它充满魔力,在实际工程中也有一部分的应用。今天就打算分享一下这个序列,它在 Google S2 中是如何使用的以及它在图论中,其他领域中的应用。这个序列就是德布鲁因序列 De Bruijn。

上面这32张牌的初始顺序魔术师是要记在心里的。

2. 长度

德布鲁因序列的长度为 kn。

注意到,所有长度为 n 的 k 元素构成的序列总共有 kn。而对于德布鲁因序列中的每个元素,恰好构成一个以此元素开头长度为 n 的子序列。所以德布鲁因序列的长度为 kn 。

1. 循环

可以用 for 循环,不断的右移目标数。找到末尾的1所在的位置。

for ( index = -1; x > 0; x >>= 1,   index ) ;

这种方式简单粗暴,时间复杂度为 O 。

扑克牌除了点数以外,还有4种花色。现在需要32张牌,就是1-8号牌,每号牌都有4种花色。花色用2位二进制编码,1-8用3位二进制编码。于是5位二进制正好可以表示一张扑克牌所有信息。

必赢56net 7

必赢56net 8

3. 构造特殊数字进行位运算

这种方式看上去比较巧,但是实际还是利用了二分搜索的思想。

index = 0;index  = (!!(x & 0xAAAAAAAA)) * 1;index  = (!!(x & 0xCCCCCCCC)) * 2;index  = (!!(x & 0xF0F0F0F0)) * 4;index  = (!!(x & 0xFF00FF00)) * 8;index  = (!!(x & 0xFFFF0000)) * 16;

这种方式的时间复杂度也是 O ,但是实际计算会比二分搜索快很多,因为它不需要比较运算,都位运算即可完成。

这个特殊的序列,任意取出其中一个窗口,即5个连续的二进制,5个二进制的第一位和第三位,或者倒数第三位和倒数第五位相加,加法遵循二进制规则,即可得到这个窗口紧接着的下一位。

必赢56net 9

必赢56net 10

5. 哈希

这种方式就比之前的方式都要高效了。

假设 x 有32位,所以末尾的1出现的可能只有32种。如果 x 为64,那就是64种可能,每一位上都有可能。通过哈希的方式 O 的时间复杂度查询出结果。

必赢56net 11

3. 数量

德布鲁因序列的数量 B 的数量为 ^ / kn 。

我们用数学归纳法证明一下上述的结论。

我们先假设德布鲁因序列是二进制的,即 k = 2。想计算序列数量总共有多少个,其实可以看这个序列每个子序列转换成10进制的数最大的是多少,那么就是它的数量。

由于每相邻的子序列是相互依赖的关系,比如下一个子序列是前一个子序列左移一位再加上 0 或者 1,产生下一个子序列。当然最后要 mod 2n,这样控制每个子序列的长度都在 n 位之间。于是我们可以得到这样的一个式子:

s[i 1]=(2s[i] mod

利用错位相减法,我们可以得到通项公式:

|B|= 2 ^ 2 / 2n

最后利用数学归纳法我们可以得到一个通用的式子,即:

|B| 的数量为 ^ / kn

最最常用的德布鲁因序列就是 k = 2 。计算一下 |B| 的数量,如下:

必赢56net 12

最后一个关键的地方就在切牌的手法上。由于德布鲁因序列是一个循环的序列,为了维护这个序列,切牌只能把上面的牌切到下面去,不能乱切。只有上面的牌切到下面,因为循环的原因,这样才不能影响德布鲁因序列。

第一步将扑克牌编码完成以后,第二步就需要找到一个序列,它必须满足以下的条件:由 2n-1个1和2n-1个0构成的序列或者圆排列,是否能存在在任意 n 个位置上0,1序列两两都不同。满足这个条件的序列也称为 n 阶完备二进圆排列。

将窗口大小为5的德布鲁因序列每5个二进制位都转换成扑克牌的编码,如下:

2. 二分搜索

把上述循环改成二分,时间复杂度就变成了 O

在上述魔术中,所有的牌都用二进制进行编码,要想任意说出任意连续的5张牌,那么必须这副牌具有全排列的特性。即枚举所有种组合,并且每个组合都唯一代表了一组排列。

如上图的例子,假设当前窗口里面的五位是 00001,左数第一位加上第三位,或者右数第三位加上第五位,得到的是0,那么这个窗口紧接着的后一位就是0 ,即 000010 。再举一个例子,当前窗口里面是 11000 ,左数第一位加上第三位为1,所以紧接着的下一位是1,即 110001 。

这个魔术中选取的德布鲁因序列也非常特殊,是可以通过一部分的递推得到。

4. 生成方式

由于德布鲁因序列并不唯一,所以用代码可以生成其中的任意一种。

def de_bruijn: """ de Bruijn sequence for alphabet k and subsequences of length n. """ try: # let's see if k can be cast to an integer; # if so, make our alphabet a list _ = int alphabet = list(map(str, range except (ValueError, TypeError): alphabet = k k = len a = [0] * k * n sequence = [] def db: if t > n: if n % p == 0: sequence.extend(a[1:p   1]) else: a[t] = a[t - p] db for j in range(a[t - p]   1, k): a[t] = j db db return "".join(alphabet[i] for i in sequence)

二进制的德布鲁因序列用的比较多,接下来看看它生成的序列。

B 就唯一一种情况。

i 01 s[i]0 0 01 1 1

B 由4位二进制位组成。也是唯一一种情况。

i 0011|0 s[i]0 00 . . . 01 01 12 . 11 . . 33 1|0 2

B 由8位二进制位组成。有2种德布鲁因序列。

i 00010111|00 s[i] i 00011101|00 s[i]0 000 . . . . 0 0 000 . . . . 01 001 1 1 001 12 . 010 . . . 2 2 . 011 . . . 33 101 5 3 111 74 . . 011 . . 3 4 . . 110 . . 65 111 7 5 101 56 . . . 11|0 6 6 . . . 01|0 27 1|00 4 7 1|00 4

B 由16位二进制位组成。对应有16种德布鲁因序列。

0x09af 00001001101011110x09eb 00001001111010110x0a6f 00001010011011110x0a7b 00001010011110110x0b3d 00001011001111010x0b4f 00001011010011110x0bcd 00001011110011010x0bd3 00001011110100110x0cbd 00001100101111010x0d2f 00001101001011110x0d79 00001101011110010x0de5 00001101111001010x0f2d 00001111001011010x0f4b 00001111010010110x0f59 00001111010110010x0f65 0000111101100101

取出其中的 0x0d2f :

 i 0000110100101111|000 s[i] 0 0000 . . . . . . . . 0 1 0001 1 2 . 0011 . . . . . . . 3 3 0110 6 4 . . 1101 . . . . . . 13 5 1010 10 6 . . . 0100 . . . . . 4 7 1001 9 8 . . . . 0010 . . . . 2 9 0101 510 . . . . . 1011 . . . 1111 0111 712 . . . . . . 1111 . . 1513 111|0 1414 . . . . . . . 11|00 1215 1|000 8

B 由32位二进制位组成。对应有2048种德布鲁因序列。由于太多了,这里没法一一列举出来,任意挑选一个出来举例:

 i 00000111011010111110011000101001|0000 s[i] 0 00000 . . . . . . . . . . . . . . . . 0 1 00001 1 2 . 00011 . . . . . . . . . . . . . . . 3 3 00111 7 4 . . 01110 . . . . . . . . . . . . . . 14 5 11101 29 6 . . . 11011 . . . . . . . . . . . . . 27 7 10110 22 8 . . . . 01101 . . . . . . . . . . . . 13 9 11010 2610 . . . . . 10101 . . . . . . . . . . . 2111 01011 1112 . . . . . . 10111 . . . . . . . . . . 2313 01111 1514 . . . . . . . 11111 . . . . . . . . . 3115 11110 3016 . . . . . . . . 11100 . . . . . . . . 2817 11001 2518 . . . . . . . . . 10011 . . . . . . . 1919 00110 620 . . . . . . . . . . 01100 . . . . . . 1221 11000 2422 . . . . . . . . . . . 10001 . . . . . 1723 00010 224 . . . . . . . . . . . . 00101 . . . . 525 01010 1026 . . . . . . . . . . . . . 10100 . . . 2027 01001 928 . . . . . . . . . . . . . . 1001|0. . 1829 001|00 430 . . . . . . . . . . . . . . . 01|000 831 1|0000 16

B 由64位二进制位组成。对应有67,108,864种德布鲁因序列。由于太多了,这里没法一一列举出来,任意挑选一个出来举例:

 i 0000001000101111110111010110001111001100100101010011100001101101|00000 s[i] 0 000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 1 000001 1 2 . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 000100 4 4 . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 010001 17 6 . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7 000101 5 8 . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 9 010111 2310 . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4711 011111 3112 . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 6313 111110 6214 . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 6115 111011 5916 . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 5517 101110 4618 . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 2919 111010 5820 . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 5321 101011 4322 . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 2223 101100 4424 . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 2425 110001 4926 . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 3527 000111 728 . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 1529 011110 3030 . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 6031 111001 5732 . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 5133 100110 3834 . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 1235 011001 2536 . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 5037 100100 3638 . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . . 939 010010 1840 . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 3741 001010 1042 . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 2143 101010 4244 . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 2045 101001 4146 . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 1947 100111 3948 . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 1449 011100 2850 . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 5651 110000 4852 . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 3353 000011 354 . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . . 655 001101 1356 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 2757 110110 5458 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 4559 01101|0 2660 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00 . 5261 101|000 4062 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000 1663 1|00000 32

B 和 B 在实际生产中都有广泛的用途。

必赢56net 13

在图论中,有这样一种无向连通图,有一条通路,能经过这个图的每条边一次并且仅一次的路径被称为欧拉回路。这个问题也是最常见的哥尼斯堡七桥问题:能不能一次走遍所有的7座桥,并且每座桥只经过一次。其实就是判断是否存在欧拉回路。

必赢56net 14

与欧拉问题非常类似的是汉密尔顿回路的问题。该问题起源于英国数学家威廉汉密尔顿(Willian Hamilton)于1857年发明的一个关于正十二面体的数学游戏:正十二面体的每个棱角上标有一个当时非常有名的城市,游戏的目的是“环绕地球”旅行,也就是说,寻找一个环游路线使得经过每个城市一次且恰好一次。

必赢56net 15

如果把正十二面体的20个棱角看成图中的顶点,将正十二面体画成如上图的平面图,那么问题就转换成:能否在图中找到一条回路,经过每个顶点一次有且仅有一次。上图就给出了一条符合要求的回路。

欧拉回路的问题一般求解方法有两种,DFS 和 Fleury 佛罗莱算法。但是汉密尔顿图没有一个有效的判断方法,它只是给出了一些充分条件或者必要条件,并非充要条件。

德布鲁因序列 和 欧拉回路,汉密尔顿回路 有紧密的联系。

若由 k 种符号组成的所有长度为 n 的序列列表为有向图的顶点,则图中有 kn 个顶点, 若顶点 m 去掉第一个符号并在尾端添加一个符号便可得顶点 n ,则有一个有向边由 m 指向 n,此时图就是 德布鲁因图。如下图,k = 2, n = 3 的图中,顶点 010 有两条对外的边,分别指向 101 和 100 。

我们以 B 举例。

在德布鲁因图中的汉密尔顿回路 即为 德布鲁因序列。如下图,左图中红色的汉密尔顿回路 ,图中对应的德布鲁因序列是 00010111,且这个汉密尔顿回路等价于窗口长度为 2 的德布鲁因序列中的一个欧拉回路,见下右图中标记的欧拉回路对应的顺序编号。

必赢56net 16

所以,窗口为 n 的德布鲁因图中的汉密尔顿回路可以等价转换为窗口为 n - 1 的德布鲁因图中的欧拉回路。

必赢56net 17

当然,一个德布鲁因图中的汉密尔顿回路并不一定唯一。如上左图,同样是 k = 2,n = 3 的德布鲁因图,还可以找到一条汉密尔顿回路。对应的欧拉回路的顺序也对应的发生了变化,见右图。

这也说明了,k = 2,n = 3 的时候,德布鲁因序列存在多个,并不唯一。

再进一步,既然说高阶的德布鲁因图的汉密尔顿回路可以转换成低级的欧拉回路。那么我们就用 k = 2,n = 3 的德布鲁因图的欧拉回路去构造高阶的汉密尔顿图,可以么?答案是当然可以。

必赢56net 18

如上图,用 k = 2,n = 3 的德布鲁因图中的一条欧拉回路,我们构造出了 k = 2,n = 4 的德布鲁因序列。

同理,当 k = 3,n = 2 的时候,德布鲁因图中依旧可以找到一条汉密尔顿回路,与之对应的 n = 1 的窗口的欧拉回路也存在。如下图。

必赢56net 19

德布鲁因序列用的比较广泛的一点应用就是 位扫描器。在 Google S2 中也是这个作用。

先来看一个比较常见的问题。

有一个非0的正数,它用二进制表示的。问如何快速的找到它二进制位中最后的1所在的位置。例如,0101010010010100,它的最后一个1所在的位置是从右往左数的第2位。

这道题有几种做法,从粗糙到最优依次分析分析。

最直接的想法是能把这个二进制数转换成只有一位为1的情况。如果上面这个问题转换成只有一个位上为1的情况,那很好解决。

那么问题转化为如何把末尾的1分离出来。可以直接用位运算进行分离。

x &= // 或者x &= -x

通过上面的操作可以把最后一位的1分离出来。

分离出来以后的解法就很多种了。

举个例子:

假设某个64位的二进制数如下:

393270003120262348811011010010011110000011101011110010000000000000000000000000000

必赢56net 20

经过 x & -x 操作以后,就能把末尾的1筛出来。原理是因为负数的存储方式是以原码的补码,即符号位不变,每位取反再加1 。末尾连续的0取反以后都为1,所以加1以后会一直往前进位,直到原来为1的那一位,因为它取反以后这一位变成0了,就不会往前进位了。

上述序列就是一个窗口大小为5的德布鲁因序列。任意连续的5个二进制相互之间都是两两不同的。所以给观众任意洗牌,不管怎么洗牌,只要最终挑出来是连续的5张,这5张的组合都在最终的结果之中。

如上图,00110 表示的就是梅花6 。11000 表示的是红桃8(因为没有 0 号牌,所以000就表示8)

有这样一个扑克牌魔术。魔术师手上拿着一叠牌,给5个人(这里的人数只能少于等于32,原因稍后会解释)分别检查扑克牌,查看扑克牌的花色和点数是否都是不同的,即没有相同的牌。

接着开始抽牌。魔术师让最后一个切牌的人抽走这叠牌最上面的一张,依次给每个人抽走最上面的一张。这时候抽走了5张牌。魔术师会说,“我已经看透了你们的心思,你们手上的牌我都知道了”。然后魔术师会让拿黑色牌的人站起来。然后魔术师会依次说出所有人手上的牌。最后每个人翻出自己的牌,全部命中。全场欢呼。

必赢56net 21

检查完扑克牌,没有重复的牌以后,就可以给这5个人洗牌了。让这5个人任意的抽一叠牌从上面放到下面,即切牌。5个人轮流切完牌,牌的顺序已经全部变化了。

第二个关键的地方是,只有让拿黑色的牌的人或者拿红色的牌的人站出来,魔术师才能知道这5个人拿到的连续5张扑克牌究竟是什么。其实魔术师说“我已经知道你们所有人拿到的是什么牌”的时候,他并不知道每个人拿到的是什么牌。

必赢56net 22

必赢56net 23

本文由必赢56net手机版发布于必赢56net,转载请注明出处:美妙的德布鲁因种类,数学魔术【必赢56net】

Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。