开始

首先给出我们要解决的问题:

有 12 枚外表一模一样的硬币，其中一枚是假币，其余都是真币。假币的重量与真币不同，但是更重还是更轻不知道。给你一个没有砝码和刻度的天平，最少称几次才能确保找出假币?

类似的题目的变种也非常的多而且经常会时不时出现在我的面前,但是一法通 万法通,只要掌握了方法这类问题也就变成了有通解的简单数学题而已.以前的我也是这么想的,但是在机缘巧合之下看到了这个硬币的两面,感觉非常有趣便在此记录一下.

离散数学

让我们先从逻辑谓词的角度来看看这个问题.当然如果你对离散学习非常熟悉的话,在看到这个问题的时候应该就能想到:”这不就是纠错码吗?”,没错,离散数学的解决方法就是纠错码.

Hamming Code

汉明码（Hamming Code）是广泛用于内存和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发生的错误，还可以用来修正错误。（要注意的是，汉明码只能发现和修正一位错误，对于两位或者两位以上的错误无法正确和发现）。

纠错,一位,完美适应我们提出的硬币问题!那么我们就开始吧~

过程

首先对于硬币称重这个问题来说,我们可以假设称完硬币有状态:1(左边),2(右边),而将0保留为没有上天平的硬币.那么我们就有$3^3=27$种状态:000,001,002…..,221,222.首先可以排除000这种状态,因为这表明这个硬币没有被用到(浪费显然是不可能的).然后我们要排除所有状态中的共线的状态(对于每一位数乘以2取余3后结果相同为共线),然后我们就一共剩下了下面的13种可能的状态:

当然因为我们这里是需要对硬币称重,所以需要每次上天平的硬币数量相同,那么我们只要保留前12组(没称,左边,右边)就可以了.

接下来我们要对硬币开始调平,对于第一行来说,有4个0和8个1,所以把最后4组都乘以2取余3:

然后来看第二行:多了2个1,因为第一行已经固定了所以这次只能在第一行为0的列中下手,我们对3,4列乘以2:

整个称重的过程就已经出现了:

• 第一次:
  • 左边:5,6,7,8
  • 右边:9,10,11,12
• 第二次:
  • 左边:2,8,11,12
  • 右边:3,4,9,10
• 第三次:
  • 左边:1,4,6,10
  • 右边:3,7,9,12

对于结果来说:

• 1代表左倾,2代表右倾,0是平衡,如果能够直接在表中找到结果,那么对应的硬币则为假币且比真的更重
• 如果在表中找不到结果但是有其共线的向量,那么对应的硬币为假币且更轻.

例子

比如:

• 第一次:右边重(2)
• 第二次:右边重(2)
• 第三次:右边重(2)

那么(2,2,2)9号为假币且更重

• 第一次:左边重(1)
• 第二次:右边重(2)
• 第三次:平衡(0)

那么(1,2,0)其共线向量硬币为11且更轻

解决了!

没错,通过一个简单的矩阵就可以解决这一类的问题并且非常的简单:查表就完事了~当然这需要对纠错码非常的敏感才能映射到这个问题上并且加以运用才行.

有限域

当然如果数学非常流批的话,可以直接忽视上面的纠错码而直接进行数学推导也是可行的.在这里给出纯粹的数学推导的方法:(直接给出大佬的博客:称硬币问题、小白鼠找毒药问题与编码理论),在推导结束之后写出矩阵和称重的过程是完全一致的.

信息论,还是信息论!

当然信息论给了我们一个有力的工具:纠错码,但是这还不够!如果我们将这个问题进行变种:在要求最少称重次数的情况下需要称过的球的次数也最少.

纠错码似乎就变得束手无策了,看一下维基百科上对于纠错码的描述:

实现错误检测和纠正的一般思路是添加一些信息冗余（例如一些额外数据）到消息，从而使接收器可以用它来检查消息的一致性，并恢复被确定为损坏的数据。错误检测和纠正的方案可以是系统性或非系统性：在系统性方案中，发射机发送原始数据，并且附加其通过一些确定性算法从数据比特导出的固定数量的校验位（或奇偶校验数据）。如果仅需要错误检测，则接收器可以简单对接收到的数据位应用相同的算法，并将其输出与接收到的校验位进行比较。如果值不匹配，则传输期间的某个点位发生错误。在非系统性的编码系统中，原始消息被变换与原始消息相等或更长比特的被编码消息。

也就是说,纠错码的纠错机制是建立在冗余之上的,而在这个问题中对于称球的次数也明显出现了冗余的信息.

二分

其实对于CS的学生来说(最起码对于我)想到的第一个解决的思路就是二分,而二分的可贵之处在于:

二分搜索为什么好，就是因为它每次都将可能性排除一半并且无论如何都能排除一半（它是最糟情况下表现最好的）。

那么对于这道题目的解法就是需要使得左倾,右倾和平衡三种结果的分支上的情况尽可能的相等,而12个硬币的可能情况有24种,也就是可以在$\lceil log_3(24) \rceil = 3$次之内解决这个问题.

下面给出解法(三分):

可以看到后面的称重是有效的利用了前面称重结果中的信息的(比如7轻8轻的情况下1必然已经是重的了,直接和1比较即可)

总结

这个问题的有趣之处在于其在搜索和信息论之间建立起的那座隐秘的桥梁,而对于这个问题的本质的追寻也是使得我难以忘记它的原因.

而大刘的这篇数学之美番外篇：快排为什么那样快也是十分耐人寻味的一篇文章,可以说对于这一个看似简单的问题而抛出的各种不同的解是很令人着迷的,而这也就是在CS这条路上不感到厌倦的原因吧.

对于汉明码解决问题的过程完全参考了这篇博客:Counterfeit Coin–Contributed by J. Dom nguez Montes.

吾尝终日而思矣,不如须臾之所学也.

当故事走到结尾的时候,我在思考:是什么让这个故事令人如此着迷和印象深刻?

可能,就是选择吧.在做出一次次能够决定故事走向的选择里,没有什么是完美的,现在的我仍旧能回想起当我第一次选择拒绝接凯特的电话而亲眼看见凯特跳楼自杀的时候,我在内疚什么?为了那浅薄的友情测试而放弃了一条生命吗?当自以为能够拯救克洛伊的父亲而回到过去却看到克洛伊坐在轮椅上的那一刻,我知道了:时间是不可能回溯的,在一次次通过时间倒流而获取别人的信任,拯救别人的时候你不得不把自己的价值观强加在别人的身上,所谓的拯救到头来也只能使得小镇消失殆尽.

我想每个人都会有:要是时间倒流我就能xxxx,xxxx.但是事实是没有时间倒流,麦克斯所做的任何一个抉择,在第一次抉择的时候就是在考量自己的内心,而那种做出选择之后的悔恨也是必须自己来接受的,没有一个选项是完美的,也没有一个选项能够去往happy ending,这才是life,strange life.

在每次用自己的目光去审视,打量游戏中的人物的时候,才会发现,每个人都是和你眼中的不一样的,因为麦克斯能够时间回溯才能了解到所有人的方方面面,从一开始的厌恶克洛伊的父亲到最后的感动,让人无法再带着自己的有色眼镜去评判身边的每一个人,每一个人都在努力生活只是有些努力不在你眼中发生而已.

而最后的双重选择也让人很难选择,虽然大部分人会说我选择拯救小镇,但是在统计数据里,拯救克洛伊的人也不在少数,你可以说这些人自私,但是一个能够时间回溯的人就是这么的自私,麦克斯可以不断的回溯,直到得到一个对于她自己来说”最好”的发展方向,而在故事的结尾,制作者告诉你:自私也是没有用的,现在摆在你眼前的只有2条路:一个人和一个小镇.这时才会发现麦克斯的无奈,获得了能力的你必须承受与之相对的伤害,除了麦克斯,没有人在事后会知道之前的故事,而当看见克洛伊被埋葬的那一刻,当回想起之前的一切才真的有触动,你做了越多的选择来留住克洛伊这时候就会越难过,所以时光回溯是什么,只是一次无聊的幻想罢了.

March comes in like a lion, and goes out like a lamb

一切也终将归于平静不论是拯救了克洛伊还是小镇,在一切寂静之后的麦克斯又会是怎样的心态呢?

而对我而言,这个故事的意义在于让我更深的去思考自己的每个选择和看待每个人和每件事的角度,毕竟没有时间回溯所以才要好好选择,而遗憾和后悔也是必然的,但是谁知道呢,毕竟:life is strange.

开始

之前写完博客需要:

1
2
3

hexo g
hexo d
hexo b

一系列的操作发布到github上之后再备份,这一点都不cooooooooool!,在之前做博客备份的时候就看到过有人使用CI来发布文章的,当时没有觉得很重要,而在经历了一次博客源文件丢失以及换电脑环境之后,才发现能够直接push一篇md就能完成整个流程是这么的美好,下面就记录一下整个配置流程(略有小坑)

Travis CI

这里使用了Travis CI来作为持续集成的工具,当然其他的工具也是同理

登录Travis CI

这里可以直接使用你的github帐号登录Travis CI不做赘述,登录之后执行下面的操作:

获取github的ACCESS_TOKEN

在github的Settings ==> Developer settings ==> Personal access tokens选择生成一个新的token,这里的token名字需要记住:

配置Travis CI环境

在刚才的setting页面下的环境中填写:

1. 刚才在github上设置的名字
2. update token之后复制的值
3. add到环境
   

博客配置

因为hexo需要将生成的文件推到github.io主页的master分支上才能正确展示,所以需要创建分支然后将hexo博客的文件上传上去,由于我之前做过backup,所以直接使用了backup分支.

创建.travis.yml文件

添加内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# 更新了脚本因为用了leancloud来统计访问次数
language: node_js   #设置语言
node_js: stable     #设置相应的版本
notifications:
  email:
    - mikasatang@gmail.com  #开启邮件通知
  on_success: always
  on_failure: always
cache:
    directories:
        - node_modules    #据说可以减少travis构建时间
before_install:
  - npm install -g hexo-cli
install:
  - npm install   #安装hexo及插件
  - npm install hexo-deployer-git --save
  - npm install hexo-git-backup --save
script:
  - hexo clean
  - hexo g   #生成
after_script:
# 替换同目录下的_config.yml文件中gh_token字符串为travis后台刚才配置的变量，注意此处sed命令用了双引号。单引号无效！
  - sed -i "s/gh_token/${Travis_CI}/g" ./_config.yml
  - grep "repo" ./_config.yml
  - touch ./public/CNAME
  - echo "misakatang.cn" >> ./public/CNAME
  - git config --global user.name "misakatang"
  - git config --global user.email "mikasatang@gmail.com"
  - hexo deploy
branches:
  only:
  - backup  #只监测这个分支，一有动静就开始构建

推送到分支开始构建

接下来只需要将文件推送到hexo文件的分支就会开始执行构建了. ex:

当然,每次都需要:

1
2
3

git add .
git commit -m "blog update"
git push origin backup

这也很不coooooool,所以直接如下:
git config --global alias.blog '!git add . && git commit -m "blog update" && git push origin gh-pages'
执行之后以后每次只需要执行git blog就可以推送博客到备份分支开始自动构建了,这下真的coooooool了.

一些小操作

1. MarkdownPicPicker:可以将剪切板的截图文件上传到(默认smms,可以自定义)图床并且直接返回md格式的链接,然后将其添加到path中,每次截图之后只需要运行命令就可以直接获得一个md格式的截图链接~~
2. 之前都是直接hexo new了博客就写,但是没写完需要修改之前的博客就很蛋疼,然后发现可以先hexo new draft打草稿,写好之后再hexo publish <filename>发布到_posts中区