Найти а[i+1]—наименьшее число больше a[i], в котором нет цифр из a[i]

#алгоритм #числовые_последовательности

Числовая последовательность {an} строится следующим образом: a0 = 1, для любого i
≥ 0 число ai+1, больше ai, равно наименьшему натуральному числу, в десятичном представлении
которого нет десятичных цифр ai. По номеру i вывести ai.

Так будет выглядеть последовательность:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111, 200, 311, 400,
511, 600, 711, 800, 911, 2000, 3111, 4000, 5111, 6000, 7111, 8000, 9111, 20000, 31111,
40000, 51111, 60000, 71111, 80000, 91111, 200000...

Как реализовать это? Или хотя бы основной принцип подскажите,
мучаюсь уже 3 дня, а сдавать завтра
    

Ответы

Ответ 1

Напишите метод, который вернет следующий элемент последовательности по предыдущему:

static int Next(int current)
{
    // Запоминаем все цифры, которые есть в текущем числе
    var digits = current.ToString().Distinct().ToList();
    // Увеличиваем число на 1 до тех пор, пока в новом числе встречаются цифры из
входного
    while ((++current).ToString().Distinct().Intersect(digits).Any());
    // Пересечений по цифрам нет, возвращаем результат
    return current;
}


Остается только вызвать его нужное количество раз:

int n = 20;
int a = 1;
for (int i = 1; i <= n; ++i) a = Next(a);
Console.WriteLine(a);




Если требуется вычислять a для больших индексов, то можно придумать решение O(1)
(верно?). Как заметил в комментариях @AnT, в последовательности есть "стабильные" участки,
можно этим воспользоваться так:

static string GetA(int index)
{
    if (index <= 9) return (index + 1).ToString();
    if (index == 10) return "22";
    if (index <= 17) return (index - 8).ToString() + ((index - 1) % 2).ToString();
    if (index == 18) return "111";
    return ((index - 3) % 8 + 2).ToString() + new string((char)((index - 1) % 2 +
'0'), (index - 3) / 8);
}


Например, GetA(4321) вычисляется мгновенно и возвращает:


  800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


Ответ 2

Начало последовательности - до 200 - можно сохранить в явном виде. А с 200 и далее
последовательность ведет себя периодично-предсказуемо: первая цифра равна (i - 3) %
8 + 2, а за ней следует либо (i - 3) / 8 нулей (для нечетных i), либо столько же единиц
(для четных i)

#include 

unsigned long long ai(unsigned i)
{
  static const unsigned long long prefix[] = 
    { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111 };

  if (i < 19)
    return prefix[i];

  i -= 3;

  unsigned long long v = i % 8 + 2;
  for (unsigned p = i / 8; p > 0; --p)
    v = v * 10 + i % 2;

  return v;
}

int main()
{
  for (unsigned i = 0; i < 100; ++i)
    std::cout << ai(i) << std::endl;
}


Ответ 3

function next(/* string */ s) {
  // преобразовать строку в массив
  var a = [...s]

  // отметить использованные символы в словаре
  var used = Object.create(null)
  for (var ch of a) used[ch] = true
  
  // найти минимальный свободный символ
  var ch = 0
  for (ch = 0; ch <= 9; ++ch)
    if (!used[ch])
      break
  
  // Попробовать увеличить первый символ
  if (++a[0] == 10) {
    // если не вышло, добавляем ещё один в начало
    a.unshift(ch)
    
    // лидирующих нулей быть не должно, ищем следующий символ, если добавили 0
    if (ch == 0)
      while (++a[0]<=9)
        if (!used[a[0]])
          break
  }
  
  // все остальные символы заменяем на минимальный
  for (var q=1; q

Найти а[i+1]—наименьшее число больше a[i], в котором нет цифр из a[i]

Числовая последовательность {an} строится следующим образом: a0 = 1, для любого i ≥ 0 число ai+1, больше ai, равно наименьшему натуральному числу, в десятичном представлении которого нет десятичных цифр ai. По номеру i вывести ai.
Так будет выглядеть последовательность
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 22, 30, 41, 50, 61, 70, 81, 90, 111, 200, 311, 400, 511, 600, 711, 800, 911, 2000, 3111, 4000, 5111, 6000, 7111, 8000, 9111, 20000, 31111, 40000, 51111, 60000, 71111, 80000, 91111, 200000...
Как реализовать это? Или хотя бы основной принцип подскажите мучаюсь уже 3 дня, а сдавать завтра

Ответ

Напишите метод, который вернет следующий элемент последовательности по предыдущему:
static int Next(int current) { // Запоминаем все цифры, которые есть в текущем числе var digits = current.ToString().Distinct().ToList(); // Увеличиваем число на 1 до тех пор, пока в новом числе встречаются цифры из входного while ((++current).ToString().Distinct().Intersect(digits).Any()); // Пересечений по цифрам нет, возвращаем результат return current; }
Остается только вызвать его нужное количество раз:
int n = 20; int a = 1; for (int i = 1; i <= n; ++i) a = Next(a); Console.WriteLine(a);

Если требуется вычислять a для больших индексов, то можно придумать решение O(1) (верно?). Как заметил в комментариях @AnT, в последовательности есть "стабильные" участки, можно этим воспользоваться так:
static string GetA(int index) { if (index <= 9) return (index + 1).ToString(); if (index == 10) return "22"; if (index <= 17) return (index - 8).ToString() + ((index - 1) % 2).ToString(); if (index == 18) return "111"; return ((index - 3) % 8 + 2).ToString() + new string((char)((index - 1) % 2 + '0'), (index - 3) / 8); }
Например, GetA(4321) вычисляется мгновенно и возвращает:
800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000