监狱难题 位运算和超立方体染色

原文链接: 监狱难题 位运算和超立方体染色

上一篇: Firefox 特性 svg mask 和clip-path的区别

下一篇: wasm 编译 cJSON 需要 安装CMAKE 3.18

视频和解法

https://www.bilibili.com/video/BV1UD4y1U7or

https://share.weiyun.com/rz2bTouu

问题描述

一个长度为n的01串, 你只能将其中的某一位进行反转, 使其可以传递出 0-n-1 中的任意数值

官方解法

64格棋盘问题的解法，精简版：首先定义非负整数a、b的异或运算a⊕b为不带任何进位的二进制加法。
例如：6⊕13，也即二进制里的110⊕1101，二进制个位是0+1=1，二位是1+0=1，四位是1+1=(1)0，不进位
只保留一个0，八位是0+1=1，所以结果是二进制的1011，也即6⊕13=11。
异或的性质有：
1. 交换律：a⊕b=b⊕a
2. 结合律：a⊕(b⊕c)=(a⊕b)⊕c
3. 单位元：a⊕0=0⊕a=a
4. 加即为减：a⊕a=0
5. 对2的幂封闭：假设存在非负整数n使得a,b<2^n，那么有a⊕b<2^n。
证明及其他具体细节请参考百度等。给64个棋盘格标号为0、1、……、63。假设在某一时刻棋盘上任意摆满了硬币，那么从这个硬币的排列里挑出所有
正面朝上的硬币，把所有这些硬币的序号取异或运算，然后可以把棋盘上的这一种硬币排列对应到序号为这个运
算结果的棋盘格上，如果没有硬币朝上则取0号棋盘格。当1号囚犯进入时，会见到对应某a号方格的硬币排列，
和藏在某x号方格下的钥匙。此时，1号囚犯翻转a⊕x号方格上的硬币。
例如：1号囚犯见到3、14、15号硬币正面朝上，此时对应a=3⊕14⊕15=2。如果钥匙藏在x=9号格下，那么1号
囚犯选择翻转a⊕x=2⊕9=11号硬币。2号囚犯进入，见到3、11、14、15号硬币正面朝上，会计算x=3⊕11⊕14⊕
15=9。接下来分析这个策略为什么会成功：由以上性质5，1号囚犯永远有硬币可以翻。
1. 如果这个硬币a⊕x本来正面朝下，那么翻转之后的硬币排列对应的结果是a⊕(a⊕x)，这其中a是本来所有
硬币的运算结果，而(a⊕x)是新多出来的一项。由于上述性质2到4，a⊕(a⊕x)=x，那么2号囚犯顺利得到钥匙
x。
2. 如果这个硬币a⊕x本来正面朝上，那么翻转之后本来的运算结果仍然是a，但是少了(a⊕x)这一项。由于性
质4，从a中“减去”(a⊕x)等同于向a中“加上”(a⊕x)，因此得到的结果仍然是a⊕(a⊕x)=x，2号囚犯顺利得
到钥匙x。

3bb 使用了超立方体染色的思路, 对于可解性判定做了说明, 只能判断哪些情况下不可解, 比如 n=63时, 虽然数据规模变小了, 但是一样不可解

参考的论文中使用信息论和汉明码

不仅如此, 还提出了在图像中传递数据的方式

对于图像数值矩阵, 每一个像素的灰度值, 0-255, 八位int, 我们可以修改最后一位比特值, 将最后一位的比特矩阵作为初始棋盘,  使用长度为32位的串基本上可以传递26个字母了, 对于512x512的图像来说, 可以传递  512x512 / 32 = 8196个字符

由于此种编码的性质具有比较强的随机性, 可以用于分类, 图书编码为16位的01串, 在做分类的时候, 如果使用人类易读的方式, 比如分16个架子, 每个架子上用前4个字母,  由于图书种类的不同, 可以有一部分的书架需要放很多书, 有的甚至空闲, 但是采用这种编码方式, 只和串中1的个数以及出现的位置有关系, 且非常随机和离散, 可以做到基本上随机分类

const random = require("random");const getList = (n = 16) =>Array(n).fill().map(() => random.int(0, 1));const code = getList();const getPosition = (list) => {let n = 0;list.forEach((v, k) => {v && (n ^= k);});return n;
};
console.log(code);
console.log(getPosition(code));

代码实现很简单, 但其中的思想和数学知识很有趣

const random = require("random");
const SIZE = 64;// 随机的初始棋盘
const getList = () => {return Array(SIZE).fill().map(() => random.int((min = 0), (max = 1)));
};// 目标位置
const getTarget = () => {return random.int((min = 0), (max = 63));
};
console.log(getList(), getTarget());const solve = (list, target) => {let n = 0;list.forEach((v, k) => {console.log(v, k, n);!v && (n ^= k);});// 翻转的位置const change = target ^ n;console.log(list, target, change);list[change] = 1 - list[change];console.log("=======");console.log(list);let m = 0;list.forEach((v, k) => {!v && (m ^= k);});console.log("m", m, target);
};solve(getList(), getTarget());

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！