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


3

Числовая последовательность {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 дня, а сдавать завтра

Источник
  •  30
  •  3
  • 5 янв 2018 2018-01-05 01:28:17
20 нельзя, потому что предыдущем есть нули уже — 4 янв 20182018-01-04 16:58:57.000000
Я не понимаю из условия, почему 20 нельзя, а 30 - можно. — 4 янв 20182018-01-04 16:58:19.000000
Ого, понял, а как это можно вычислить по формуле или алгоритмично? — 4 янв 20182018-01-04 00:02:49.000000
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... Начиная с 200 поведение последовательности стабилизируется. — 3 янв 20182018-01-03 18:07:47.000000
Ну то есть требование такое: "a[i+1] - это наименьшее натуральное число, большее a[i], в десятичном представлении которого нет десятичных цифр a[i]" — 3 янв 20182018-01-03 17:58:11.000000

3 ответа

3

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

#include <iostream>

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;
}
  • 5 янв 2018 2018-01-05 01:56:57
@Андрей NOP: Точно. Я почему-то решил, что нумерация с единицы. Подправил ответ. — 5 янв 20182018-01-05 00:38:44.000000
a(0)=1 по условию — 5 янв 20182018-01-05 00:21:07.000000
2

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<a.length; ++q) a[q] = ch
  
  // собираем из массива строку
  return a.join("")
}

// выводим первые 50 чисел
var s = "0"
for (var q=0; q<50; ++q) console.log(s = next(s))
.as-console-wrapper.as-console-wrapper { max-height: 100vh }

  • 4 янв 2018 2018-01-04 18:27:53
4

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

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

@Qwertiy, зато просто и понятно и делает именно то, что просят в условии — 4 янв 20182018-01-04 17:23:34.000000
Ну ведь неэффективно же... — 4 янв 20182018-01-04 17:22:15.000000
Спасибо большое — 4 янв 20182018-01-04 17:12:32.000000
Ну простите, изначально вы просили C#-код, блок-схему уж самостоятельно нарисуйте. Комментарии к методу добавил, можете взять их для словесного описания алгоритма. — 4 янв 20182018-01-04 17:08:45.000000
Проблема в том, что это необходимо реализовать в псевдокоде или блок-схеме. А такие штуки там провернуть не получится. — 4 янв 20182018-01-04 17:07:37.000000