侧边栏壁纸
博主头像
钱学超博主等级

火星人,1万小时法则的忠实拥趸。技术宅,象棋和羽毛球爱好者,马拉松PB成绩:4小时零8分。坚持认为算法是计算机的灵魂。喜欢解决问题,喜欢手工,喜欢与朋友们聊天喝酒吹牛X。

  • 累计撰写 62 篇文章
  • 累计创建 342 个标签
  • 累计收到 72 条评论
标签搜索

目 录CONTENT

文章目录

关于1772池算法的优化设计

钱学超
2021-09-10 / 0 评论 / 0 点赞 / 1,165 阅读 / 2,189 字 / 正在检测是否收录...
  1. 1772池就是把双色球所有开奖序列排列组合出来,给所有人平均分配。

  2. 这样无论如何不会产生漏奖的情况。

  3. 但是也存在问题。就是排列组合的数据量太大,17721088种排列组合,要做到给火星用户平均分配一下,还是需要非常大计算量的。

  4. 并且存储量也是非常大的。排列组合总体保存17721088种,就需要大约1G的内存空间。想要做到优化,还不能给用户表中直接保存号码组合,可以保存一个数字。数字代表了他分到的号码组合在17721088种组合中的位置。

  5. 但是这样一来,兑奖的时候就比较麻烦,我们需要把所有用户的所有排列组合查询出来,挨个兑奖,看看中了几个红球,几个蓝球。但是这个查询过程很麻烦,因为数据量特别大,数据库也会有很大的压力。

  6. 所以这时候,可以用到康托展开公式。

  7. 康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的名次,因此是可逆的。

  8. **X = A[0] * (n-1)! + A[1] * (n-2)! + … + A[n-1] * 0! **
    A[i] 指的是位于位置i后面的数小于A[i]值的个数,后面乘的就是后面还有多少个数的阶乘
    说明 :这个算出来的数康拖展开值,是在所有排列次序 - 1的值,因此X+1即为在全排列中的次序

  9. 但是双色球的开奖,属于组合,不属于排列。所以康托展开需要做一些变换。

  10. 我们把33个红球,用1表示选中,用0表示未选中,做成一个33位的字符串,用来表示一注号码。比如:111111000000000000000000000000000表示开奖号码为1,2,3,4,5,6的红球组合。

  11. 把这个33位的字符串,当成一个二进制数字来看。这样,比较大小就很容易了。最高位是1的,肯定比最高位是0的大。最高位都是1的,就比较下一位。

  12. 按照这个顺序进行排序。得到的排序是唯一的。既然顺序唯一,序号和组合,就可以完全一一对应起来。

  13. 所以任何一个方案的序号的表达形式,都可以认为是比它小的所有的数字的数量。

  14. 所以就可以理解为,将每一位号码从1置换为0之后,右侧部分的排列组合。所以这个数量也就可以比较简单的计算出来了。

  15. $f("0...0")=\sum_MC_{p[i]}$其中 $p[i]$表示第i个1在整个序列中的位置(从右向左)。例如:1011000(太多了,就不用33位了),第一个1,从右向左数,是第p[1]=4位,第二个1,第p[2]=5位,第3个1,第p[3]=7位。它在整体7位数选取3位的组合中($C_73$)的排序位置是:$C_41+C_52+C_73=49$

  16. 反向通过序号查找序列的方法也可以安排了。因为从左边开始,第1个1的位置,就是比他小的所有数字排列组合的数量。$C_pm$,下一位,以此类推。查找第一个位置,就是要找到这个1在这个数字中的位置p。比如你要查找第n位,只需要找到一个合适的p,使得$C_pm<=n$并且$C_{p+1}^m>n$即可。

  17. 上代码:

    /// 获取红球的序号第X个,自然数,从1开始。28,29,30,31,32,33 =  1
    // 1,2,3,4,5,6 = 1107568
    private static int getRedIndex(int[] redBalls) {
        int total = 0;
        int base = 6;
        // 从高位开始。
        for (int ball : redBalls) {
            int pos = 33 - ball;
            long compute = AlgorithmicUtils.C(pos, base--);
            compute = compute < 0 ? 0 : compute;
            total += compute;
        }
        return total + 1;
    }

   /**
     * 通过制定的序号,查找1772池对应的方案组合。
     * 序号取值范围是:1-17721088.自然数
     *
     * @return 返回一个格式化好的号码方案:01,02,03,04,05,06#01
     */
    public static String getPlan(int index) {
        // 规则判定
        if (index < 1 || index > 17721088) {
            return null;
        }

        // 蓝球在序列中的序号
        int blue = index % 16;
        // 计算完毕之后,再将蓝球转换为合法的数字
        if (blue == 0) {
            blue = 16;
        }

        // 红球在序列中的序号,第XX个,自然数。从1开始
        int redIndex = index / 16 + (index % 16 > 0 ? 1 : 0);
        // 修改为序列中的逻辑序号,从0开始。
        redIndex = redIndex - 1;
        // 查找红球。
        int[] reds = new int[6];
        for (int i = 0; i < 6; i++) {
            int base = 6 - i;
            for (int j = 0; j < 33; j++) {
                long tmp = AlgorithmicUtils.C(j, base);
                int km = (int) (tmp < 0 ? 0 : tmp);
                tmp = AlgorithmicUtils.C(j + 1, base);
                int kp1m = (int) (tmp < 0 ? 0 : tmp);
                if (redIndex >= km && redIndex < kp1m) {
                    reds[i] = 33 - j;
                    redIndex = redIndex - km;
                    break;
                }
            }
        }
        // 格式化方案
        return formatPlan(reds, blue);
    }
0

评论区