乐趣区

算法吸血鬼算法详解

jiezi

吸血鬼算法

  • 题目

    吸血鬼数字是指位数为偶数的数字，可以由一堆数字想乘而得到。而这对数字各包含乘积的一半位数的数字，其中从最初的数字中选取的数字可以任意排序。以两个 0 结尾的数字是不允许的，例如，下列的数字都是“吸血鬼”数字：

    1260=21*60

    1827=21*87

    2187=27*81

    写出一个程序，找出 4 位数的所有吸血鬼数字

  • 思路

    • 个人思路

      1. 使用两位数的循环相乘得出四位数
      2. 将两个两位数和四位数分别拆成单个字符，保存在 List 中
      3. 使用 List 的 equals 方法判断是否相等

    • 官方思路

      1. 遍历所有四位数
      2. 将四位数拆分并分别组合成两个两位数，一共有 12 种搭配方式
      3. 每一种搭配方式都判断

    • 优势

      1. 个人思路能够减少近一半的遍历次数，约 3000 次

  • 实现

    • 个人思路 

      package ten;

import java.util.*;

public class VampireNumberImp {static int VampireJudgeImp(){List<Integer> VampireArray = new ArrayList<Integer>();
        List<Character> ikList = new ArrayList<Character>();
        List<Character> sumList = new ArrayList<Character>();
        int point = 0;
        for (int i = 11 ; i < 100 ; i++){for (int k = i ; k < 100 ; k++){

                int sum = i * k;
                // 判断是否为四位数, 判断是否为两个零结尾
                if (sum < 1000 || sum > 9999 || sum % 100 == 0 || VampireArray.contains(sum)){continue;}
                point++;
                // 判断是否为吸血鬼数字
                    // 将数字添加进 list
                    ikList.add((char) (i / 10));
                    ikList.add((char) (i % 10));
                    ikList.add((char) (k / 10));
                    ikList.add((char) (k % 10));
                    sumList.add((char) (sum / 1000));
                    sumList.add((char) (sum % 1000 / 100));
                    sumList.add((char) (sum % 1000 % 100 / 10));
                    sumList.add((char) (sum % 10));
                    // 数字排序
                    Collections.sort(ikList);
                    Collections.sort(sumList);
                    // 判断是否为吸血鬼数字
                    if (ikList.equals(sumList)){VampireArray.add(sum);
                        System.out.println(sum);
                    }
                ikList.clear();
                sumList.clear();}
        }
        return point;
    }
    public static void main(String[] args) {long startTime=System.currentTimeMillis();
        int point = VampireJudgeImp();
        // 测试代码执行时间
        long endTime=System.currentTimeMillis();
        System.out.println("程序运行时间："+(endTime - startTime)+"ms");
        System.out.println("程序运行次数："+point+"次");
    }
}/* output
1395
1260
1827
2187
1530
1435
6880
程序运行时间：19ms
程序运行次数：3210 次
*/

    • 官方思路 

      package ten;

public class VampireNumberOfficial {static int a(int i) {return i/1000;}
    static int b(int i) {return (i%1000)/100;
    }
    static int c(int i) {return ((i%1000)%100)/10;
    }
    static int d(int i) {return ((i%1000)%100)%10;
    }
    static int com(int i, int j) {return (i * 10) + j;
    }
    static void productTest (int i, int m, int n) {if(m * n == i) System.out.println(i + "=" + m + "*" + n);
    }
    public static void main(String[] args) {long startTime=System.currentTimeMillis();
        for(int i = 1001; i < 9999; i++) {productTest(i, com(a(i), b(i)), com(c(i), d(i)));
            productTest(i, com(a(i), b(i)), com(d(i), c(i)));
            productTest(i, com(a(i), c(i)), com(b(i), d(i)));
            productTest(i, com(a(i), c(i)), com(d(i), b(i)));
            productTest(i, com(a(i), d(i)), com(b(i), c(i)));
            productTest(i, com(a(i), d(i)), com(c(i), b(i)));
            productTest(i, com(b(i), a(i)), com(c(i), d(i)));
            productTest(i, com(b(i), a(i)), com(d(i), c(i)));
            productTest(i, com(b(i), c(i)), com(d(i), a(i)));
            productTest(i, com(b(i), d(i)), com(c(i), a(i)));
            productTest(i, com(c(i), a(i)), com(d(i), b(i)));
            productTest(i, com(c(i), b(i)), com(d(i), a(i)));
        }
        long endTime=System.currentTimeMillis();
        System.out.println("程序运行时间："+(endTime - startTime)+"ms");
      }
}/*output 
1260 = 21 * 60
1395 = 15 * 93
1435 = 41 * 35
1530 = 51 * 30
1827 = 87 * 21
2187 = 27 * 81
6880 = 86 * 80
6880 = 80 * 86
程序运行时间：54ms
*/
退出移动版