Найти все 4 цифры вампиров

Question

Я решаю проблему, чтобы узнать все 4 цифры вампиров.

Количество вампира у = х * у определяется как число с «п» четным числом цифр, образованных путем умножения пару «п/2'-х цифр (где цифры взяты из оригинала число в любом порядке) x и y вместе. Если v - число вампиров, то x & y и называются его «клыками».

Примеров чисел вампиров являются:

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

Я попробовал алгоритм грубой силы, чтобы объединить различные цифры заданного числа и умножить их вместе. Но этот метод очень неэффективен и занимает много времени.

Есть ли более эффективное алгоритмическое решение этой проблемы?

Answer 1

Или вы можете использовать свойство чисел вампира, описанных на this page (связанный из Википедии):

важный теоретический результат, полученный Пит Хартли:

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

Доказательство: Пусть мод будет бинарный модульный оператор, а d (x) - сумма десятичной цифры цифр x. Хорошо известно, что d (x) mod 9 = x mod 9 для всех x. Предположим, 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

Решения для congruence являются (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

Я бы так не отказался от грубой силы. У вас есть отличный набор чисел от 1000 до 9999, которые вы должны пройти. Я бы разделил набор на некоторое количество подмножеств, а затем разворачивал потоки для обработки каждого подмножества.

Вы могли бы разделить работу, которая должна появляться с различными комбинациями каждого числа; IIRC моя дискретная математика, у вас есть 4 * 3 * 2 или 24 комбинации для каждого числа, чтобы попробовать.

Подход производителя/потребителя может оказаться полезным.

Answer 3

Это уродливый взлом (грубая сила, ручная проверка на перестановки, небезопасные операции с буфером, создание обманов и т. Д.), Но он выполняет эту работу. Ваше новое упражнение должно улучшить его: P

Wikipedia claims что есть 7 номеров вампиров, длина которых составляет 4 цифры. full code has found them all, даже некоторые дубликаты.

Edit:Here's a slightly better comparator function.

Edit 2:Here's a C++ version что Уникальные результаты (поэтому он избегает дубликатов) с использованием std::map (и сохраняют последнее появление определенного числа вампира вместе с ее факторами в ней). Он также соответствует критерию того, что по крайней мере один из факторов не должен заканчиваться 0, т.е. е. число не является номером вампира, если оба мультипликатора к тому времени делятся. Этот тест ищет 6-значные числа вампиров, и он действительно находит ровно 148 из них, в соответствии с тем, что Википедия.

---

Исходный код:

#include <stdio.h> 

void getdigits(char buf[], int n) 
{ 
    while (n) { 
     *buf++ = n % 10; 
     n /= 10; 
    } 
} 

int is_vampire(const char n[4], const char i[2], const char j[2]) 
{ 
    /* maybe a bit faster if unrolled manually */ 
    if (i[0] == n[0] 
    && i[1] == n[1] 
    && j[0] == n[2] 
    && j[1] == n[3]) 
     return 1; 

    if (i[0] == n[1] 
    && i[1] == n[0] 
    && j[0] == n[2] 
    && j[1] == n[3]) 
      return 1; 

    if (i[0] == n[0] 
    && i[1] == n[1] 
    && j[0] == n[3] 
    && j[1] == n[2]) 
      return 1; 

    if (i[0] == n[1] 
    && i[1] == n[0] 
    && j[0] == n[3] 
    && j[1] == n[2]) 
      return 1; 

    // et cetera, the following 20 repetitions are redacted for clarity 
    // (this really should be a loop, shouldn't it?) 

    return 0; 
} 

int main() 
{ 
    for (int i = 10; i < 100; i++) { 
     for (int j = 10; j < 100; j++) { 
      int n = i * j; 
      if (n < 1000) 
       continue; 

      char ndigits[4]; 
      getdigits(ndigits, n); 

      char idigits[2]; 
      char jdigits[2]; 
      getdigits(idigits, i); 
      getdigits(jdigits, j); 

      if (is_vampire(ndigits, idigits, jdigits)) 
       printf("%d * %d = %d\n", i, j, n); 
     } 
    } 

    return 0; 
} 

Answer 4

Подход, который я хотел бы попробовать бы Переберите каждого числа в [1000, 9999], и испытание, если любая перестановка его цифр (раскол в середине) умножается, чтобы сделать это.

Для этого потребуется (9999 - 1000) * 24 = 215,976 тестов, которые должны выполняться на быстродействующей быстроте на современной машине.

Я бы определенно сохранил цифры отдельно, поэтому вы можете избежать необходимости делать что-то вроде кучи деления, чтобы извлекать цифры из одного целого.

Если вы пишете свой код так, чтобы вы делали только добавление и умножение целого числа (и, возможно, случайное деление на перенос), оно должно быть довольно быстрым. Вы могли бы дополнительно увеличить скорость, пропустив пары с двумя цифрами, которые «очевидно» не будут работать, например, с начальными нулями (обратите внимание, что наибольший продукт, который может быть получен с помощью однозначного числа и двухзначного числа, равен 9 * 99, или 891).

Также обратите внимание, что этот подход неудобно параллелен (http://en.wikipedia.org/wiki/Embarrassingly_parallel), поэтому, если вам действительно нужно ускорить его еще больше, вы должны изучить тестирование чисел в отдельных потоках.

Answer 5

Итерируйте все возможные клыки (100 x 100 = 10000 возможностей) и найдите, имеют ли их продукты те же цифры, что и клыки.

Answer 6

EDIT: полный перебор, что отсеивает идентичную X и Y значения ...

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

public class Vampire { 

    public static void main(String[] args) { 
     for (int x = 10; x < 100; x++) { 
      String sx = String.valueOf(x); 
      for (int y = x; y < 100; y++) { 
       int v = x * y; 
       String sy = String.valueOf(y); 
       String sv = String.valueOf(v); 
       if (sortVampire(sx + sy).equals(sortVampire(sv))) { 
        System.out.printf("%d * %d = %d%n", x, y, v); 
       } 
      } 
     } 
    } 

    private static List<Character> sortVampire(String v) { 
     List<Character> vc = new ArrayList<Character>(); 
     for (int j = 0; j < v.length(); j++) { 
      vc.add(v.charAt(j)); 
     } 
     Collections.sort(vc); 
     return vc; 
    } 
} 

Answer 7

Итерация кажется хорошо для меня, так как вам нужно только сделать это один раз, чтобы найти все значения, и вы можете просто затем их кешируйте. Python (3) версия, которая занимает около 1,5 секунд:

# just some setup 
from itertools import product, permutations 
dtoi = lambda *digits: int(''.join(str(digit) for digit in digits)) 
gen = ((dtoi(*digits), digits) for digits in product(range(10), repeat=4) if digits[0] != 0) 
l = [] 

for val, digits in gen: 
    for check1, check2 in ((dtoi(*order[:2]), dtoi(*order[2:])) for order in permutations(digits) if order[0] > 0 and order[2] > 0): 
     if check1 * check2 == val: 
      l.append(val) 
      break 

print(l) 

Который даст вам [1260, 1395, 1435, 1530, 1827, 2187, 6880]

Answer 8

Мне кажется, что для выполнения минимально возможное количество тестов, не полагаясь на каких-либо особенно абстрактные идеи, вы, вероятно, хотите перебирать клыки и отбирать любые явно бессмысленные кандидаты.

Например, если x*y == y*x примерно половина вашего поиска может быть уничтожена, только при оценке случаев, когда y > x. Если наибольшие двузначное клык является 99, то самым маленьким, который может сделать четыре-значный номер 11, поэтому не начинайте ниже 11.

EDIT:

OK, выбрасывая все, что я думал о в (хотя это выглядит глупо против ведущего решения).

for (x = 11; x < 100; x++) 
{ 
    /* start y either at x, or if x is too small then 1000/x */ 
    for (y = (x * x < 1000 ? 1000/x : x); y < 100; y++) 
    { 
     int p = x * y; 

     /* if sum of digits in product is != sum of digits in x+y, then skip */ 
     if ((p - (x + y)) % 9 != 0) 
      continue; 

     if (is_vampire(p, x, y)) 
      printf("%d\n", p); 
    } 
} 

и испытание, так как я не видел никого использовать гистограмму, но:

int is_vampire(int p, int x, int y) 
{ 
    int h[10] = { 0 }; 
    int i; 
    for (i = 0; i < 4; i++) 
    { 
     h[p % 10]++; 
     p /= 10; 
    } 
    for (i = 0; i < 2; i++) 
    { 
     h[x % 10]--; 
     h[y % 10]--; 
     x /= 10; 
     y /= 10; 
    } 
    for (i = 0; i < 10; i++) 
     if (h[i] != 0) 
      return 0; 
    return 1; 
} 

Answer 9

еще одна грубая сила (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; 
} 

Выполняется в значительной степени мгновенно. Имена переменных не слишком описательны, но должны быть довольно очевидными ...

Основная идея - начать с двух потенциальных клыков, разбить их на цифры и отсортировать цифры для удобства сравнения. Затем мы делаем то же самое с продуктом - разбиваем его на цифры и сортируем. Затем мы переформатируем два целых числа из отсортированных цифр, и если они равны, у нас есть совпадение.

Возможные улучшения: 1) начать j на 1000/i вместо i, чтобы избежать необходимости делать if (p < 1000) ..., 2) возможно использовать сортировку вставками вместо пузырьковой сортировки (но кто собирается уведомление эти 2 дополнительных свопы), 3) использовать реальный swap(), 4) сравнить массивы напрямую, а не строить из них синтетическое целое. Не уверен, что любой из них сделает какую-либо измеримую разницу, хотя, если вы не запустите ее на Commodore 64 или что-то еще ...

Редактировать: Просто из любопытства я принял эту версию и немного обобщил ее для работы с 4, 6 и 8-значными случаями - без какой-либо значительной оптимизации он может найти все 8-значные номера вампиров в < 10 секунд ...

Answer 10

<?php 
for ($i = 10; $i <= 99; $j++) { 

    // Extract digits 
    $digits = str_split($i); 

    // Loop through 2nd number 
    for ($j = 10; $j <= 99; $j++) { 

     // Extract digits 
     $j_digits = str_split($j); 
     $digits[2] = $j_digits[0]; 
     $digits[3] = $j_digits[1]; 

     $product = $i * $j; 

     $product_digits = str_split($product); 

     // check if fangs 

     $inc = 0; 

     while (in_array($digits[$inc], $product_digits)) { 

      // Remove digit from product table 
       /// So AAAA -> doesnt match ABCD 
      unset($product_digits[$array_serach($digits[$inc], $product_digits)]); 

      $inc++; 

      // If reached 4 -> vampire number 
      if ($inc == 4) { 

        $vampire[] = $product; 
        break; 
      } 
     } 
    } 
} 

// Print results 
print_r($vampire); 
?> 

Взял менее секунды на PHP. не мог даже сказать, что ему нужно было выполнить 8100 вычислений ... компьютеры быстрей!

Результаты:

дает вам все 4 цифры плюс некоторые из них повторяются. Вы можете обрабатывать данные и удалять дубликаты.

Answer 11

Brute версию силы в C# с помощью LINQ:

class VampireNumbers 
{ 
    static IEnumerable<int> numberToDigits(int number) 
    { 
     while(number > 0) 
     { 
      yield return number % 10; 
      number /= 10; 
     } 
    } 

    static bool isVampire(int first, int second, int result) 
    { 
     var resultDigits = numberToDigits(result).OrderBy(x => x); 

     var vampireDigits = numberToDigits(first) 
          .Concat(numberToDigits(second)) 
          .OrderBy(x => x);         

     return resultDigits.SequenceEqual(vampireDigits); 
    } 

    static void Main(string[] args) 
    { 
     var vampires = from fang1 in Enumerable.Range(10, 89) 
         from fang2 in Enumerable.Range(10, 89) 
         where fang1 < fang2 
          && isVampire(fang1, fang2, fang1 * fang2)  
         select new { fang1, fang2 }; 

     foreach(var vampire in vampires) 
     { 
      Console.WriteLine(vampire.fang1 * vampire.fang2 
           + " = " 
           + vampire.fang1 
           + " * " 
           + vampire.fang2); 
     } 
    } 
} 

Answer 12

1260 1395 1435 1530 1827 2187 6880 является вампиром

Я новичок в программировании ... Но есть только 12 комбинаций в поиске всех четырехзначных чисел вампиров. Мой бедный ответ:

public class VampNo { 

    public static void main(String[] args) { 
     for(int i = 1000; i < 10000; i++) { 

      int a = i/1000; 
      int b = i/100%10; 
      int c = i/10%10; 
      int d = i%10; 

       if((a * 10 + b) * (c * 10 + d) == i || (b * 10 + a) * (d * 10 + c) == i || 
        (a * 10 + d) * (b * 10 + c) == i || (d * 10 + a) * (c * 10 + b) == i || 
        (a * 10 + c) * (b * 10 + d) == i || (c * 10 + a) * (d * 10 + b) == i || 
        (a * 10 + b) * (d * 10 + c) == i || (b * 10 + a) * (c * 10 + d) == i || 
        (b * 10 + c) * (d * 10 + a) == i || (c * 10 + b) * (a * 10 + d) == i || 
        (a * 10 + c) * (d * 10 + b) == i || (c * 10 + a) * (b * 10 + d) == i) 
       System.out.println(i + " is vampire"); 

     } 
    } 
} 

Основная задача теперь заключается в упрощении логического выражения в If() блок

Answer 13

Я отредактированный алгоритм Owlstead немного, чтобы сделать его более понятным для начинающих Java/учащихся.

import java.util.Arrays; 

public class Vampire { 

    public static void main(String[] args) { 
    for (int x = 10; x < 100; x++) { 
     String sx = Integer.toString(x); 
     for (int y = x; y < 100; y++) { 
      int v = x * y; 
      String sy = Integer.toString(y); 
      String sv = Integer.toString(v); 
      if(Arrays.equals(sortVampire(sx + sy), sortVampire(sv))) 
       System.out.printf("%d * %d = %d%n", x, y, v); 
     } 
    } 
} 
private static char[] sortVampire (String v){ 
    char[] sortedArray = v.toCharArray(); 
    Arrays.sort(sortedArray); 
    return sortedArray; 
} 

}

Answer 14

Подобно кому-то уже упоминалось выше, мой метод является первым найти все перестановки ряда, а затем разделить их пополам, чтобы сформировать два 2-значных чисел, и тест, если их произведение равно первоначальный номер.

Еще одно интересное обсуждение выше - сколько перестановок может иметь номер. Вот мое мнение: (1) номер, у которого четыре цифры одинаковы, имеет 1 перестановку; (2) число, у которого есть только две разные цифры, имеет 6 перестановок (не имеет значения, содержит ли он нули, потому что мы не заботимся о перестановке, если это еще 4-значное число); (3) число, у которого три разных цифры, имеет 12 перестановок; (4) число со всеми четырьмя разными цифрами имеет 24 перестановки.

public class VampireNumber { 

// method to find all permutations of a 4-digit number 
public static void permuta(String x, String s, int v) 
{for(int i = 0; i < s.length(); i++) 
{permuta(x + s.charAt(i), s.substring(0,i) + s.substring(i+1), v); 
if (s.length() == 1) 
    {x = x + s; 
    int leftpart = Integer.parseInt(x.substring(0,2)); 
    int rightpart = Integer.parseInt(x.substring(2)); 
    if (leftpart*rightpart == v) 
     {System.out.println("Vampir = " + v); 
     } 
    } 
    } 
} 

public static void main(String[] args){ 
for (int i = 1000; i < 10000; i++) { 
permuta("", Integer.toString(i), i); //convert the integer to a string 
} 
} 
} 

Answer 15

Этот питон код запуска очень быстро (O (n2))

result = [] 
for i in range(10,100): 
    for j in range(10, 100): 
     list1 = [] 
     list2 = [] 
     k = i * j 
     if k < 1000 or k > 10000: 
      continue 
     else: 
      for item in str(i): 
       list1.append(item) 
      for item in str(j): 
       list1.append(item) 
      for item in str(k): 
       list2.append(item) 
      flag = 1 
      for each in list1: 
       if each not in list2: 
        flag = 0 
       else: 
        list2.remove(each) 
      for each in list2: 
       if each not in list1: 
        flag = 0 

      if flag == 1: 
       if k not in result: 
        result.append(k) 
for each in result: 
    print(each)   

Answer 16

И вот мой код. Для того, чтобы генерировать числа зомби, мы должны использовать случайный класс :)

import java.io.PrintStream; 
import java.util.Set; 
import java.util.HashSet; 
import java.util.Iterator; 

class VampireNumbers { 
    static PrintStream p = System.out; 

    private static Set<Integer> findVampireNumber() { 
     Set<Integer> vampireSet = new HashSet<Integer>(); 
     for (int y = 1000; y <= 9999; y++) { 
      char[] numbersSeparately = ("" + y).toCharArray(); 
      int numberOfDigits = numbersSeparately.length; 
      for (int i = 0; i < numberOfDigits; i++) { 
       for (int j = 0; j < numberOfDigits; j++) { 
        if (i != j) { 
         int value1 = Integer.valueOf("" + numbersSeparately[i] + numbersSeparately[j]); 
         int ki = -1; 
         for (int k = 0; k < numberOfDigits; k++) { 
          if (k != i && k != j) { 
           ki = k; 
          } 
         } 
         int kj = -1; 
         for (int t = 0; t < numberOfDigits; t++) { 
          if (t != i && t != j && t != ki) { 
           kj = t; 
          } 
         } 

         int value21 = Integer.valueOf("" + numbersSeparately[ki] + numbersSeparately[kj]); 
         int value22 = Integer.valueOf("" + numbersSeparately[kj] + numbersSeparately[ki]); 
         if (value1 * value21 == y && !(numbersSeparately[j] == 0 && numbersSeparately[kj] == 0) 
           || value1 * value22 == y 
             && !(numbersSeparately[j] == 0 && numbersSeparately[ki] == 0)) { 
          vampireSet.add(y); 
         } 
        } 
       } 
      } 
     } 
     return vampireSet; 
    } 

    public static void main(String[] args) { 
     Set<Integer> vampireSet = findVampireNumber(); 
     Iterator<Integer> i = vampireSet.iterator(); 
     int number = 1; 
     while (i.hasNext()) { 
      p.println(number + ": " + i.next()); 
      number++; 
     } 
    } 
}