Что представляет собой более эффективная реализация этой головоломки?

Question

Головоломка

Для каждого входного числа п (п < 10) существует номер выходного т таким образом, что: первая цифра

• М является п
• м является п-значный номер
• каждые 2-значная последовательность внутри m должно быть другим простым числом

Выход должен m, где m - наименьшее число, удовлетворяющее указанным выше условиям. Если такого номера нет, выход должен быть равен -1;

Примеры

п = 3 -> т = 311

п = 4 -> т = 4113 (заметим, что это не 4111, как будет повторять 11)

п = 9 -> т = 971131737

Мой несколько рабочий раствор

Вот мой первый удар в этом, подход «грубой силы». Я ищу более элегантное решение, так как это очень неэффективно, так как n растет.

public long GetM(int n) 
{ 
    long start = n * (long)Math.Pow((double)10, (double)n - 1); 
    long end = n * (long)Math.Pow((double)10, (double)n); 
    for (long x = start; x < end; x++) 
    { 
     long xCopy = x; 
     bool allDigitsPrime = true; 
     List<int> allPrimeNumbers = new List<int>(); 
     while (xCopy >= 10) 
     { 
      long lastDigitsLong = xCopy % 100; 
      int lastDigits = (int)lastDigitsLong; 
      bool lastDigitsSame = allPrimeNumbers.Count != 0 && allPrimeNumbers.Contains(lastDigits); 
      if (!IsPrime(lastDigits) || lastDigitsSame) 
      { 
       allDigitsPrime = false; 
       break; 
      } 

      xCopy /= 10; 
      allPrimeNumbers.Add(lastDigits); 
     } 

     if (n != 1 && allDigitsPrime) 
     { 
      return x; 
     } 
    } 

    return -1; 
} 

Первые мысли о том, как это можно было бы сделать более эффективным

Таким образом, очевидно, узким местом здесь прохождения через весь список номеров, которые могли бы выполнить это условие из п .... к (n + 1) ..... Вместо того, чтобы просто увеличивать количество каждой итерации цикла, должен быть некоторый умный способ пропуски чисел, основанный на требовании, чтобы 2-значные последовательности были первыми. Например, для n = 5 нет точки, проходящей через 50000 - 50999 (50 не является простым), 51200 - 51299 (12 не является простым), но я не был уверен, как это можно реализовать или если это было бы достаточно оптимизации, чтобы алгоритм выполнялся для n = 9.

Любые идеи относительно этого подхода или другого подхода к оптимизации?

Answer 1

Это возможное решение, в R, с использованием рекурсии. Интересно было бы построить дерево всех возможных путей

# For every input number n (n < 10) 
# there is an output number m such that: 

# m's first digit is n 
# m is an n digit number 
# every 2 digit sequence inside m must be a different prime number 
# Need to select the smallest m that meets the criteria 

library('numbers') 

mNumHelper <- function(cn,n,pr,cm=NULL) { 
    if (cn == 1) { 
    if (n==1) { 
     return(1) 
    } 
    firstDigit <- n 
    } else { 
    firstDigit <- mod(cm,10) 
    } 
    possibleNextNumbers <- pr[floor(pr/10) == firstDigit] 
    nPossible = length(possibleNextNumbers) 
    if (nPossible == 1) { 
    nextPrime <- possibleNextNumbers 
    } else{ 
    # nextPrime <- sample(possibleNextNumbers,1) 
    nextPrime <- min(possibleNextNumbers) 
    } 
    pr <- pr[which(pr!=nextPrime)] 
    if (is.null(cm)) { 
    cm <- nextPrime 
    } else { 
    cm = cm * 10 + mod(nextPrime,10) 
    } 
    cn = cn + 1 
    if (cn < n) { 
    cm = mNumHelper(cn,n,pr,cm) 
    } 
    return(cm) 
} 

mNum <- function(n) { 
    pr<-Primes(10,100) 
    m <- mNumHelper(1,n,pr) 
} 
for (i in seq(1,9)) { 
    print(paste('i',i,'m',mNum(i))) 
} 

Пример вывода

[1] "i 1 m 1" 
[1] "i 2 m 23" 
[1] "i 3 m 311" 
[1] "i 4 m 4113" 
[1] "i 5 m 53113" 
[1] "i 6 m 611317" 
[1] "i 7 m 7113173" 
[1] "i 8 m 83113717" 
[1] "i 9 m 971131737" 

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

Answer 2

Вам не нужно пробовать все номера. Вместо этого вы можете использовать другую стратегию, суммированную как «попытаться добавить цифру».

Какая цифра? Ну, цифра таких, что

1. образует простой вместе с вашей текущей последней цифрой
2. премьер формируется не произошли в числе перед

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

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

Answer 3

Я только что составил список двузначных простых чисел, а затем решил проблему вручную; это заняло всего несколько минут. Не каждая проблема требует компьютера!