Ответ 1

ОК, это заняло несколько дней, чтобы понять. Первое, что нужно понять, состоит в том, что единственное конкретное требование головоломки Эйлера 442, из которого вытекает этот вопрос, состоит в том, чтобы решить для E (10-18). Несвязанные примеры того, что означает 11-бесплатный номер, - это просто отвлекающие факторы.

Вариант грубой силы не может быть и речи по двум причинам.

• Для этого требуется буквально сравнение строк в quintilian и потребуется неделя для решения на большинстве домашних компьютеров.

• Леонард Эйлер был математиком, поэтому дух этого вопроса должен интерпретироваться в этом контексте.

Через некоторое время я начал фокусироваться на сопоставлении с образцом для степеней 10, вместо того, чтобы постоянно включать в мои алгоритмы мощности 11. После того, как вы подсчитаете, каковы полномочия 11, вы закончили с чем-то связанным с этим. Они представляют только строки. Они даже не включены в окончательный алгоритм, они просто используются в детективной работе.

Я начал пытаться получить подробное представление о том, как вводится новые 11-содержащие числа между степенями 10 и если существует предсказуемая картина. Если бы это было так, то было бы просто использовать этот шаблон для вывода всех 11-содержащих чисел, введенных до любой точки остановки 10 ^.

Основные понятия

Для каждого нового 10 ^ число предыдущих 11 ^ совпадений строк совпадает с предыдущим диапазоном 10 ^. Это проще объяснить с помощью диаграммы.

Вот список из 10 ^ 2 - 10 ^ 6, который показывает количество новых 11-содержащих чисел, введенных до сих пор и сгруппированных по номеру 11, который соответствует строке.

Рисунок 1.) Число совпадений 11 ^ в диапазонах 10 ^, сгруппированных по символу строки 11 ^

---------------------------
10^2 range (10 - 100)
---------------------------
    11            1
---------------------------
10^3 range (100 - 1000)
---------------------------
    11           18
    121           1
---------------------------
10^4 range (1000 - 10000)
---------------------------
    11          260
    121          18
    1331          1
---------------------------
10^5 range (10000 - 100000)
---------------------------
    11         3392
    121         260
    1331         18
    14641         1
---------------------------
10^6 range (100000 - 1000000)
---------------------------
    11        41760
    121        3392
    1331        260
    14641        18
    161051        1

etc...

Для составления этого списка есть два требования.

• Если несколько 11-содержащих чисел соответствуют последовательно (например, 11000-11999), все эти элементы должны быть отнесены к 11 ^ группе первого совпадения. Это означает, что хотя в этом примере будут совпадения для 121 и 1331, все совпадения в этом диапазоне относятся к 11, потому что они первыми.

• Матчи создаются на основе кратчайшей возможности. то есть 11, 121, 1331 и т.д. Это связано с тем, что некоторые числа соответствуют нескольким 11 ^ строкам, а другие - внутри смежного диапазона. И, сопоставление их от высокого к низкому не создает предсказуемой картины. Функционально это все равно. Это просто привносит в картину большую ясность.

Обратите внимание, что в каждом новом диапазоне 10 ^ вводится только 1 новое совпадение 11 ^. И количество совпадений для каждого предыдущего 11 ^ номера одинаково, независимо от предыдущей мощности. Трудность здесь состоит в том, что количество совпадений строк * 11 не может быть непосредственно выведено из предыдущего значения.

Рис. 2). Дифференцируя другие 11 ^ шаблоны из соответствия * 11

    ****11
    ***110 pattern
    **1100 pattern
    *11000 pattern
    110000 pattern
    etc...

Все совпадения "шаблоны" очень предсказуемы в пределах 10 мк. Только цифры * 11 не являются очевидными в том, как они накапливаются. На самом деле не так, что нет шаблона, проблема в том, что вам придется предполагать числа, которые были отсканированы справа налево и, как результат, нет, если другие шаблоны будут более предсказуемыми.

Как выясняется, необходимо отслеживать отдельный аккумулятор, который позволяет нам использовать предыдущие совпадения * 11 для расчета количества новых совпадений * 11. Для любого из вас, гениальных гениев, может быть более элегантное решение. Но, вот моя.

Вы всегда должны отдельно отслеживать количество совпадений * 11 от полномочий предыдущий 2. Используя их как операнды, вы можете рассчитать количество совпадений * 11 для текущей мощности.

Пример:

Число совпадений * 11 в диапазоне 10 ^ 3 равно 8. Также есть 10 совпадений на "110", но они здесь неважно, мы просто отслеживаем номера, заканчивающиеся на "11" . Итак, мы начинаем с двух предыдущих совпадений совпадений * 11, равных 8 и 0 из 2 предыдущих 10 ^ диапазонов.

Важно: Для любого числа меньше 10 ^ 2, 0 - это предыдущий счетчик совпадений для этого вычисления. Вот почему 0 - второй операнд обратного хода при работе с 10 ^ 3.

Рис. 3.). Как рассчитать * 11 совпадений в диапазоне 10 ^, используя обратный отслеживание

    10^3 |   80 = 8 * 10 - 0;
    10^4 |  792 = 80 * 10 - 8;
    10^5 | 7840 = 792 * 10 - 80;

Однако этот номер полезен, если посмотреть на него, опять же, с другой точки зрения.

Рисунок 4.)Иллюстрация того, как масштабные группы масштабируются по степеням 10

    ==================================
      #    Formulas for 10^4
    ==================================
     80    **11         = 8 * 10 - 0
     80    *110 pattern = previous power *11 times 10
    100    1100 pattern = previous power 110 times 10
    ==================================
    260   Total matches in range

    ==================================
       #  Formulas for 10^5
    ==================================
     792  ***11         = 80 * 10 - 8
     800  **110 pattern = previous power **11 times 10
     800  *1100 pattern = previous power *110 times 10
    1000  11000 pattern = previous power 1100 times 10
    ==================================
    3392  Total matches in range

В этих примерах только число * 11 должно рассчитываться отдельно. Увидев, что эти цифры сложены таким образом, он чувствует себя более сложным, чем есть. Это важно только для понимания концепции. На практике мы абстрагируем все, кроме расчета * 11, посредством кумулятивного умножения.

Теперь, прежде чем мы перейдем к рабочему алгоритму, последнее, что нужно понять концептуально, - это использовать эти шаблоны для вычисления N-го 11-бесплатного числа, заканчивающегося на каждом ^ 10.

Это двухэтапный процесс, поэтому я продемонстрирую пример. Давайте посмотрим на диапазон 1000 - 10000 от Рис. 1. 10000 - 10 ^ 4, так что это диапазон, который мы решаем для.

Следующие 11 ^ группы находятся в этом диапазоне. 18 и 1 могут быть получены из предыдущих степеней (см. Рис. 1).

    match         #
    ---------------
    11          260
    121          18
    1331          1

• Рассчитайте итоговые 11-содержащие совпадения в текущем диапазоне 10 ^ 4. Для этого сначала нужно вычислить значение для категории соответствия "11" . Значение 260 выше может быть рассчитано с использованием чисел от и предыдущих диапазонов и отдельных операндов отслеживания * 11 следующим образом:

  Вычисление * 11 для 10 ^ 4

      260 = (18 * 10) + (8 * 10 - 0)        
  

  • Где 18 - общее количество всех совпадений "11" (не обязательно * 11) из диапазона 10 ^ 3 (см. рис. 1).
  • 10 являются константами.
  • И 8 и 0 являются нашими отправными точками, упомянутыми ранее, для отдельного расчета изменений * 11.

• Объедините результат 10 ^ 4 со всеми остальными результатами до 10 ^ 2. Примечание.. Всего совпадений для 10 ^ 2 равно 1, потому что есть только одно 11-содержащее число от 0 до 100.

  Total 11-containing numbers in 10^4 range:  279 = 260 + 18 + 1
  Total 10^4 range plus previous totals    :  299 = 279 + 19 + 1
                                             ---------------------
                                10^4 solved: 9701 = 10^4 - 299
  

Рабочий алгоритм

Вот алгоритм, написанный на С#, который решает для каждого из 10 ^ 1 до 10 ^ 18. Он возвращается почти мгновенно. Из уважения к эйлеру проекта я не публиковал ответ на свою головоломку напрямую. Однако вывод является точным. Сейчас вопрос № 442 показывает только 163 человека, которые решили проблему по сравнению с 336260 людьми, решающими проблему №1. Если это число начнет расти без причины, я удалю это сообщение.

    private ulong GetNthElevenFreeForPow10(uint pow){

        if(pow > 18)
            throw new ArgumentException("Argument must be a positive integer between 1 and 18", "pow");

        // All of the numbers up to 10^0 & 10^1 are 11-free
        // if 1 is considered 11-free as the euler question 
        // states.
        if (pow == 0 || pow == 1)
            return (ulong)Math.Pow(10, pow);

        // The sequence of 11s doesn't form a repeatable pattern
        // until 10^4 because it requires back tracking to 
        // calculated running totals.
        if (pow == 2)
            return (ulong)Math.Pow(10, pow) - 1;

        if (pow == 3)
            return (ulong)Math.Pow(10, pow) - (18 + 1 + 1);

        // At each new power the number of elevens created is 
        // easily predicted based on the previous power. But, 
        // the number of new entries ending with 11 i.e.) xxx11
        // is a little trickier. It requires a lookback at the 
        // two previous powers. This array stores the lookback 
        // operands used to make that calculation.
        ulong[] lookbackOperands = new ulong[] { 
            0, 8
        };

        // this number is used to calculate all of the new 11-containing 
        // numbers for each power. The next power is always a calculation 
        // on the previous.
        ulong elevensConsumedCurrent = 18;
        ulong elevensConsumedPrevious = 18 + 1;

        // this number holds a running total all 11-containing
        // numbers consumed so far.
        ulong elevensConsumedTotal = 20;

        for (int n = 4; n <= pow; n++) {
            // Calculate the number of new items added that end with "11".
            ulong endsWith11Current = lookbackOperands[1] * 10 - lookbackOperands[0];
            lookbackOperands[0] = lookbackOperands[1];
            lookbackOperands[1] = endsWith11Current;

            elevensConsumedCurrent = elevensConsumedCurrent * 10 + endsWith11Current;
            elevensConsumedPrevious += elevensConsumedCurrent;
            elevensConsumedTotal += elevensConsumedPrevious;
        }

        return (ulong)Math.Pow(10, pow) - elevensConsumedTotal;

    }

Использование:

        StringBuilder sb = new StringBuilder();
        for (uint n = 1; n <= 18; n++)
            sb.AppendLine(String.Format(
                    "Nth 11-Free Number @ 10^{0}\t{1}", 
                    n, 
                    GetNthElevenFreeForPow10(n).ToString()
                )
            );

        Console.WriteLine(sb.ToString());

Вот первые 15.

Nth 11-Free Number @ 10^1   10
Nth 11-Free Number @ 10^2   99
Nth 11-Free Number @ 10^3   980
Nth 11-Free Number @ 10^4   9701
Nth 11-Free Number @ 10^5   96030
Nth 11-Free Number @ 10^6   950599
Nth 11-Free Number @ 10^7   9409960
Nth 11-Free Number @ 10^8   93149001
Nth 11-Free Number @ 10^9   922080050
Nth 11-Free Number @ 10^10  9127651499
Nth 11-Free Number @ 10^11  90354434940
Nth 11-Free Number @ 10^12  894416697901
Nth 11-Free Number @ 10^13  8853812544070
Nth 11-Free Number @ 10^14  87643708742799
Nth 11-Free Number @ 10^15  867583274883920

Ответ 2

Интересно, как легко люди пугаются термином "грубая сила", даже не пытаясь количественно оценить его:)

Решение грубой силы на самом деле O (R * log R)

где R - результат (k -й одиннадцати несвободный номер). Вы просто проверяете все номера 1..R, и для каждого из них вы выполняете поиск строк для 11, 121, 1331, 14641 и т.д., Используя подготовленный автомат (для заданного количества цифр). O(R * log R) не выглядит так плохо, если вы посмотрите на него таким образом, не так ли?: -)

Решение для генерации?

Умная идея - попытаться сгенерировать число больше:

• либо путем создания непосредственно k -ного числа;
• или последовательно, генерируя все 1- k одиннадцать несвободных номеров;
• или путем создания всех одиннадцати несвободных чисел < 10 ^ n сразу и сортировать их.

Решение 1 должно быть очень умным, если не близко к невозможному. Решение 2 кажется лучше, чем решение грубой силы, потому что оно пропускает те числа, которые не являются одиннадцатью несвободными. Решение 3 будет легко реализованной альтернативой, что подводит нас к важному вопросу:

Сколько одиннадцати несвободных чисел < 10 ⁿ существуют?

Легкая комбинаторика (работает точно для n <= 10, для более высоких n это близкое приближение, пренебрегая тем, что 11 ² является подстрокой 11 ¹³ а 11 - подстрокой из 11 ¹¹ и 11 ¹⁹):

так что для предела 10 ⁿ вы получаете более 10 решений ^n-2! Это означает, что количество решений является постоянной долей предела, что означает, что

O (R) = O (k)

откуда следует, что

Решение грубой силы на самом деле равно O (k * log k), а также решение для всех решений!

Ужасное решение грубой силы теперь намного лучше, не так ли? Тем не менее он все тот же:)

Можем ли мы стать лучше этого?

• Решение 1 - это шанс, но близко к магии.
• Решение 2 - лучшее, на что вы можете надеяться, - это O(k), но вы должны быть очень осторожны, чтобы достичь этого. Будет много осложнений, из-за которых будет непросто выбрать следующий наименьший одиннадцати несвободный номер. Например. при генерации всех 11xxx, 121xx, 1331x, например. 13121 находится между ними, что затрудняет автоматическую генерацию упорядоченных номеров, не говоря уже о двойственности, вызванной шаблоном, появляющимся в цифрах xxx и т.д. Вероятно, у вас будет какая-то сложная структура данных, которая заставит O(log k) на каждом шаге и, таким образом, O(k log k) в целом.
• Решение 3 - это, как мы уже знаем, O(k log k), то же самое, что найти k -th number.

Ответ 3

В качестве хорошей отправной точки стоит рассмотреть связанную проблему подсчета количества одиннадцати несвободных (ENF) целых чисел из N цифр. Это не совсем то же самое, что найти n-го ENF целое число, но последняя проблема может быть сведена к прежнему довольно легко (см. Конец этого сообщения для Java-кода, который делает это).

Идея состоит в том, чтобы делать динамическое программирование на префиксах. Для любой строки цифр s и любого целого k обозначим N(k,s) количество строк ENF длиной k, которые начинаются с s. И для любой строки s пусть s_0 будет самым длинным суффиксом s, который также встречается как префикс любой мощности одиннадцати (POE) длины k или меньше. Тогда, считая, что s сам по себе не содержит подстрок POE, мы имеем уравнение:

N(k,s) = N(k-length(s)+length(s_0),s_0)

Обоснование этого уравнения заключается в следующем. Поскольку s_0 является суффиксом s, напишем s как конкатенацию некоторой другой строки q и s_0: s=[q,s_0]. Теперь пусть r - любая цифровая строка, начинающаяся с s и снова напишем это как конкатенацию, как r=[s,r_0] = [q,s_0,r_0].

Если r содержит POE в качестве подстроки, то либо этот POE содержится в r_0, либо пересекает границу между s и r_0. В этом случае s должен заканчиваться префиксом POE, и, поскольку мы знаем, что самый длинный префикс POE, который встречается как суффикс s, s_0, следует, что если r содержит подстроку POE, то эта подстрока должна содержаться в [s_0,r_0]. Это дает нам взаимно однозначное соответствие между ENF, которые начинаются с s=[q,s_0] и ENF, начинающихся с s_0.

Это вышеприведенное уравнение порождает рекурсивный алгоритм для подсчета числа k-значных ENF с заданным префиксом. Базовые случаи заканчиваются экземплярами, где length(s_0)=length(s), что означает, что s сам является префиксом POE длины k или меньше. Так как таких префиксов POE не так много (не более k выбирает 2, то есть O (k ^ 2)), эта формула приводит к эффективному алгоритму. Вот псевдокод:

Given a prefix s and an integer k, this function computes N(k,s)

if s contains a POE then return 10^(k-length(s))
if length(s) = k return 0 
let s0 = longest POE prefix which is a suffix of s
if(length(s0)<length(s))
  return N(k-length(s)+length(s0),s0)
total = 0
for d = "0" to "9"
  total += N(k,concatenate(s,d))
return total

Используя динамическое программирование, время работы этого алгоритма будет полиномиальным по k, числом цифр. Алгоритм только рекурсирует на POE-префиксах, и поскольку из них O (k ^ 2), время работы будет равно O (k ^ 2) от времени работы каждой итерации. Используя наивный алгоритм O (k ^ 2) для нахождения самого длинного суффикса, который соответствует префиксу POE, таким образом приведет к алгоритму O (k ^ 4), а использование дерева оснований для поиска совпадений в линейном времени приведет к тому, что O (k ^ 3). В приведенном ниже java-коде используется наивный алгоритм, и экспериментально для значений до около k = 100, как представляется, Θ (k ^ 4.5), хотя это несоответствие может быть связано с деталями реализации или постоянными факторами, влияющими на время автономной работы при малых входных размерах, Вот код:

public class Eleven {

  public static final String[] digits = 
    {"0","1","2","3","4","5","6","7","8","9"};

  public static BigInteger countENF(String prefix, int k){
    return countENF(prefix,k,new HashMap(),getPowers(k));
  }

  public static BigInteger countENF(String prefix, 
      int k, 
      // This map contains stored results for dynamic programming
      // Pair is an auxiliary class that does what you think it does
      Map<Pair<String,Integer>,BigInteger> resultMap,
      // precomputed list of powers of 11
      List<String> powers
      ){
    // Dynamic programming case
    BigInteger res = resultMap.get(new Pair(prefix,k));
    if(res != null)
      return res;

    // base cases
    if(!isEFree(prefix, powers)){
      res = new BigInteger("10").pow(k-prefix.length());
      resultMap.put(new Pair<>(prefix,k), res);
      return res;
    }
    if(prefix.length() >= k){
      res = new BigInteger("0");
      resultMap.put(new Pair<>(prefix,k), res);
      return res;
    }    
    String s0 = getMaxPrefix(prefix, powers);
    if(s0.length() < prefix.length()){
      return countENF(s0,k+s0.length()-prefix.length(),resultMap,powers);
    }

    // recursive summation
    res = new BigInteger("0");
    for(String d : digits){
      String s1 = prefix + d;
      res = res.add(countENF(s1,k,resultMap,powers));
    }
    resultMap.put(new Pair<>(prefix, k), res);
    return res;
  }  


  //
  // helper functions
  //

  // returns all POEs of at most length digits
  private static List<String> getPowers(int length) {
    List<String> ret = new ArrayList<>();
    BigInteger val = new BigInteger("11");
    BigInteger eleven = new BigInteger("11");
    while(val.toString().length() <= length){
      ret.add(val.toString());
      val = val.multiply(eleven);
    }
    return ret;
  }

  // finds the longest string that is both a prefix of s and a suffix of a POE
  private static String getMaxSuffix(String s, List<String> powers){
    for(int i=s.length(); i>0; i--){
      String sub = s.substring(0,i);
      for(String p : powers){
        if(p.endsWith(sub))
          return sub;
      }
    }
    return "";
  }

  public static boolean isEFree(String s, List<String> powers){
    for(String p : powers){
      if(s.indexOf(p)>=0)
        return false;
    }
    return true;
  }

Как упоминалось выше, этот алгоритм не решает точной проблемы в OP. Но, изменяя этот код, чтобы на самом деле найти n-й номер ENF, довольно просто. Изготовление повторный вызов countENF, мы сначала выясним, сколько цифр имеет номер n'th ENF, а затем, по одной цифре за раз, мы вычисляем цифры n-го ENF слева направо.

 public static String getNthENF(BigInteger i){
    int k = i.toString().length();
    HashMap results = new HashMap();
    List<String> powers = getPowers(k);
    while(countENF("",k,results,powers).compareTo(i) < 0){
      k++;
     powers = getPowers(k);
    }
    String solution = "";
    BigInteger total = new BigInteger("0");

    while(solution.length() < k){
      for(String d : digits){
        BigInteger newTotal = total.add(countENF(solution + d,k,results,powers));
        int comp = newTotal.compareTo(i);
        if(comp >= 0){
          solution = solution + d;
          break;
        }
        total = newTotal;
      }
    }
    return solution;
  }

Вот пример вывода, который дает N'th ENF, вычисляемый с использованием динамического программирования, а также использование грубой силы для степеней 10.

Dynamic Programming:
10^1: 118
10^2: 1178
10^3: 11680
10^4: 115730
10^5: 1146628
10^6: 11360558
10^7: 112558960
10^8: 1115229050
10^9: 11049731548
10^10: 103258311161
10^11: 935443232311
10^12: 8576360477119
10^13: 79330786951511
10^14: 732117130575070
10^15: 6880811638385388
10^16: 64284911460844887
10^17: 610616803411054857
10^18: 5759459802926457113
10^19: 54555977711878792498
10^20: 518773721711219891634
Brute Force:
10^1: 118
10^2: 1178
10^3: 11680
10^4: 115730
10^5: 1146628
10^6: 11360558
10^7: 112558960

Ответ 4

Изменить: этот подход пропустит, например, одиннадцати несвободный номер 1011. Я знаю, что неправильно, и исправит это, но не могу сделать это сейчас.

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

Пусть S - последовательность степеней 11:

11, 121, 1331, 14641, 161051,...

Пусть E (n) - множество чисел, которые содержат строковое представление n в качестве подстроки. Множество, которое вы ищете, представляет собой объединение E (n) над n в S.

Как мы генерируем элементы E (n) для некоторого n? (Возьмем, например, n = 121).

Сделайте ориентированный ациклический граф, где n - корень node. Сделайте n точкой для всех 19 следующих чисел:

Добавить 0-9: n0 n1 n2 n3 n4 n5 n6 n7 n8 n9
Prepend 1-9: 1n 2n 3n 4n 5n 6n 7n 8n 9n

Повторите процесс для каждого из этих новых узлов. Обратите внимание, что некоторые узлы могут иметь более одного родителя, поэтому вы хотите сохранить хэш-карту от числа до указателя node. (Вы можете добраться до 71217 по 121 → 1217 → 71217 или 121 → 7121 → 71217.)

Этот граф обладает тем свойством, что для любого ребра от u до v имеем u < v. Это важно, потому что это означает, что мы можем генерировать элементы E (n) в порядке возрастания, выполняя графа первого поколения графика, всегда расширяя нерасширенный node с наименьшим числом.

Теперь объедините эти графики для всех n из S.

У вас есть один большой ациклический граф (который бесконечен), который вы можете генерировать с широким интервалом, всегда расширяя нерасширенный node с наименьшим числом, испуская следующий (kth) одиннадцати несвободный номер.

псевдокод

Это работает, я тестировал его. Здесь С# gist: https://gist.github.com/timothy-shields/8026924

procedure generate_eleven_non_free
i = 1
n = 11^i
//frontier nodes; F.insert(x) does nothing if x already in F
F = empty-min-heap-set
while (true)
{
    if (F.empty() or F.min() > n)
    {
        F.insert(n)
        i = i + 1
        n = 11^i
    }
    else
    {
        m = F.extractmin()
        yield m
        for j = 0:9        
            F.insert(append(m,j))
        for j = 1:9
            F.insert(append(j,m))
    }
}

Чтобы получить k-ый одиннадцати несвободный номер, просто сделайте что-то вроде generate_eleven_non_free(). element_at (k), где это должно выбрать значение k-го числа.

Ответ 5

10^18 действительно, действительно большой. Грубая сила не твой друг.

Однако отметим некоторые удобства:

• Если строка s представляет одиннадцати несвободное число, то тривиально так же d s (где d - строка цифр).
• Если вы хотите узнать, сколько k -дигретных номеров одиннадцать-несвободных, вы можете определить, что из числа k-1 -digit чисел одиннадцать-несвободных.
• (например, сколько 1xx-номеров одиннадцать-несвободных?) Ну, сколько хх-номеров одиннадцать-несвободных? Очевидно, по крайней мере, что много чисел 1xx - одиннадцать-несвободных. Единственными дополнительными случаями являются: сила одиннадцати начинается с цифры в начале - с 1, которая только что была прикреплена спереди.)
• Это предполагает относительно простой подход к динамическому программированию, чтобы выяснить, сколько одиннадцати несвободных чисел находится в строке известной длины с фиксированным префиксом. (например, сколько одиннадцати несвободных чисел находятся в 934xxxxx)

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

Ответ 6

Для меня это звучит как алгоритм разделения и покорения.

Эта проблема очень похожа на: http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/

и это: http://en.wikipedia.org/wiki/Maximum_subarray_problem

Когда вы делите, вы разбиваете исходную строку s на 2 части, которые примерно равны 1/2. В нижней части вашей рекурсии у вас есть легкие проблемы с небольшими 1 char Строками, которые все одиннадцать бесплатно (потому что они не содержат достаточного количества символов, чтобы иметь любую силу внутри внутри).

"трюк" приходит, когда вы "подходите" к рекурсии. На этом этапе вам нужно воспользоваться тем фактом, что любая "сила" (т.е. 121), которую вы ищете, ДОЛЖНА соединить "середину" входной строки.

Например, когда вы "подходите" из строк длиной 1 к строкам длины 2, вы будете знать, что некоторая сила, которую вы ищете, находится в первой половине, а некоторые находятся во второй половине входная строка.

Ответ 7

Это выглядит как алгоритм O(klog^2(k)):

def add(vals, new_vals, m, val):
    if val < m and val not in vals and val not in new_vals:
        new_vals.append(val)

def kth11(k):
    vals = [ 11**i for i in range(1, k+1) ]
    new_vals = [ ]
    while True:
        vals = sorted(vals + new_vals)
        vals = vals[:k]
        m = vals[-1]
        new_vals = [ ] 
        for v in vals:
            for s in range(1, 10):
                val = int(str(s) + str(v))
                add(vals, new_vals, m, val)
            for s in range(0, 10):
                val = int(str(v) + str(s))
                add(vals, new_vals, m, val)
        if len(new_vals) == 0: break
    return vals[-1]

print kth11(130)

Ответ 8

given a k, find the kth eleven-non-free number.... это большой вопрос.

Поскольку это вопрос времени, я пишу псевдокод.

• Первый шаг Держите полномочия одиннадцать удобными

var eleven_powers = []; for (var i=0; i<1000; i++) eleven_powers.push(Math.pow(11,i));

• Второй шаг Сохраняйте все возможные номера non-eleven-free в той степени, в которой вы можете. Это будет иметь дело с большими целыми числами.

for (var i=11; i<Integer.MAX_VALUE; i++){ if(string(i).substring(for each of eleven_powers) == true) store it sequentially results_array }

• Третий шаг Take k, return results_array[k]