找到所有4位数的吸血鬼号码

Question

我正在解决一个问题,找出所有4位数的吸血鬼号码.

甲吸血鬼数 V = X*Y被定义为"n"个偶数的由一对"N/2'-位数字(其中数字被从原始数采取以任何顺序)乘以形成数字的数x和你在一起.如果v是吸血鬼号码,那么x&y被称为"fangs".

吸血鬼号码的例子是:

    1.    1260=21*60
    2.    1395=15*93
    3.    1530=30*51

我已经尝试过强力算法来组合给定数字的不同数字并将它们相乘.但是这种方法效率很低,占用了大量时间.

是否有更有效的算法解决方案来解决这个问题？

Answer 1

或者您可以使用此页面上描述的吸血鬼号码属性(从维基百科链接):

Pete Hartley发现了一个重要的理论结果:

      If x·y is a vampire number then x·y == x+y (mod 9) 

证明:令mod为二进制模运算符,d(x)为x的十进制数之和.众所周知,对于所有x,d(x)mod 9 = x mod 9.假设x·y是吸血鬼.然后它包含与x和y相同的数字,特别是d(x·y)= d(x)+ d(y).这导致:(x·y)mod 9 = d(x·y)mod 9 =(d(x)+ d(y))mod 9 =(d(x)mod 9 + d(y)mod 9) mod 9 =(x mod 9 + y mod 9)mod 9 =(x + y)mod 9

同余的解是(x mod 9,y mod 9){{0,0),(2,2),(3,6),(5,8),(6,3),(8, 5)}

所以你的代码看起来像这样:

for(int i=18; i<100; i=i+9){          // 18 is the first multiple of 9 greater than 10
   for(int j=i; j<100; j=j+9){        // Start at i because as @sh1 said it's useless to check both x*y and y*x
       checkVampire(i,j);
   }
}

for(int i=11; i<100; i=i+9){          // 11 is the first number greater than 10 which is = 2 mod 9
   for(int j=i; j<100; j=j+9){
       checkVampire(i,j);
   }
}

for(int i=12; i<100; i=i+9){
   for(int j=i+3; j<100; j=j+9){
       checkVampire(i,j);
   }
}

for(int i=14; i<100; i=i+9){
   for(int j=i+3; j<100; j=j+9){
       checkVampire(i,j);
   }
}

// We don't do the last 2 loops, again for symmetry reasons

因为它们在每个集合中都是40个元素,所以{(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100}只有4*40 = 160迭代才能进行104次迭代.如果考虑>= 1000约束,则可以执行更少的操作,例如,您可以避免检查是否j < 1000/i.

现在您可以轻松扩展以查找超过4位数的吸血鬼=)

Answer 2

迭代所有可能的f牙(100 x 100 = 10000种可能性),并找出他们的产品是否与f牙相同的数字.

Answer 3

又一个蛮力(C)版本,带有免费的泡泡排序......

#include <stdio.h>

static inline void bubsort(int *p)
{ while (1)
  { int s = 0;

    for (int i = 0; i < 3; ++i)
      if (p[i] > p[i + 1])
      { s = 1;
        int t = p[i]; p[i] = p[i + 1]; p[i + 1] = t;
      }

    if (!s) break;
  }
}

int main()
{ for (int i = 10; i < 100; ++i)
    for (int j = i; j < 100; ++j)
    { int p = i * j;

      if (p < 1000) continue;

      int xd[4];
      xd[0] = i % 10;
      xd[1] = i / 10;
      xd[2] = j % 10;
      xd[3] = j / 10;

      bubsort(xd);
      int x = xd[0] + xd[1] * 10 + xd[2] * 100 + xd[3] * 1000;

      int yd[4];
      yd[0] = p % 10;
      yd[1] = (p / 10) % 10;
      yd[2] = (p / 100) % 10;
      yd[3] = (p / 1000);

      bubsort(yd);
      int y = yd[0] + yd[1] * 10 + yd[2] * 100 + yd[3] * 1000;

      if (x == y)
        printf("%2d * %2d = %4d\n", i, j, p);
    }

  return 0;
}

几乎瞬间运行.变量名称不是太具描述性,但应该非常明显......

基本的想法是从两个潜在的f牙开始,将它们分解为数字,并对数字进行排序以便于比较.然后我们对产品做同样的事情 - 将其分解为数字和排序.然后我们从排序的数字重新构成两个整数,如果它们相等,我们就有一个匹配.

可能的改进:1)开始j在1000 / i代替i,以避免做if (p < 1000) ...？,2)可能使用插入排序而不是冒泡排序(但谁的会通知那些2条额外的掉期),3)使用真正swap()实施,4)直接在阵列比较而不是从中构建合成整数.但是,不确定其中任何一个会产生任何可衡量的差异,除非你在Commodore 64或其他东西上运行它......

编辑:出于好奇,我采用了这个版本并将其推广到4,6和8位数的情况下 - 没有任何重大优化,它可以在<10秒内找到所有8位数的吸血鬼数字. .