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

Ответ 1

Или вы можете использовать свойство номеров вампиров, описанное на этой странице (ссылка из Википедии):

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

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

Доказательство. Пусть mod - бинарный по модулю оператор, а d (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 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.

Теперь вы можете легко масштабировать, чтобы найти вампиров с более чем четырьмя цифрами =)

Ответ 2

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

Ответ 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;
}

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

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

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

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

Ответ 4

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

Wikipedia утверждает, что есть 7 номеров вампира, которые составляют 4 цифры. Полный код нашел их все, даже некоторые дубликаты.

Изменить: Здесь немного лучшая функция компаратора.

Изменить 2: Здесь версия С++, которая уникально отображает результаты (поэтому она избегает дубликатов) с помощью std::map (и хранит последнее вхождение конкретного номера вампира вместе с его факторами в нем). Он также соответствует критерию того, что по крайней мере один из факторов не должен заканчиваться на 0, i. е. число не является номером вампира, если оба мультипликатора к тому времени делятся. Этот тест ищет 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;
}

Ответ 5

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

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

Может возникнуть подход производителей/потребителей.

Ответ 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;
    }
}

Ответ 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]

Ответ 8

Версия для переборки в С# с 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);
        }
    }
}

Ответ 9

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

Еще одно интересное обсуждение выше - сколько перестановок может иметь число. Вот мое мнение: (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
}
}
}

Ответ 10

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

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

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

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

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

Ответ 11

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

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

EDIT:

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

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;
}

Ответ 12

<?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 цифры плюс некоторые повторяются. Вы можете обрабатывать данные и удалять дубликаты.

Ответ 13

1260 1395 1435 1530 1827 2187 6880 - вампир

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

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()

Ответ 14

Я немного изменил алгоритм 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;
}

}

Ответ 15

Этот код python выполняется очень быстро (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)