V2EX › dujiaoxi 的所有回复 › 第 1 页 / 共 1 页

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

2022-02-12 11:55:07 +08:00

回复了 williamjing 创建的主题 › 算法 › 算法问题，大神进！

看了上面人对信息的分析，也可以建议把题目改成如何用 1bit 区分 012 这三个数，解决了可以干翻香农公式了

2022-02-12 11:46:16 +08:00

回复了 williamjing 创建的主题 › 算法 › 算法问题，大神进！

@williamjing 也就是你出了个残缺的需求让开发去实现算法呗。卡号的生成方式，有效取值范围，什么都没说，上来就 16 位 10 进制，还🦐限定 512mb 内存。然后一点一点的加限定条件补完需求改题目，不如直接加个允许有亿分之 4 的误判率好了。建议题目改成 4 亿个 16 位 10 进制的数，无压缩的编码在 512 兆储存空间，求允许数最杂乱的规律是什么。参考其他人的解法，全随机分布目前最少的需要 1.43g ，然后如果都是同一个值只要 54bit

2022-02-12 08:58:42 +08:00

回复了 williamjing 创建的主题 › 算法 › 算法问题，大神进！

假如已有的卡号和要判断的卡号都在 10^16 空间上随机分布没有规律，题目上已有的 4 亿个数字占整个 10^16 比例是亿分之 4 ，那么就有一个很好的解决方法了，直接 return false ，时间复杂度 O(1)，不需要读取硬盘，不需要额外内存，误判率只有亿分之 4 ，基本可以满足生产需求了（雾）