Определить, является ли число обводным числом

Question

Определение обтекания #:

• Это целое число с ровно N цифрами, каждая из которых составляет от 1 до 9 включительно.
• Цифры образуют последовательность, где каждая цифра указывает, где находится следующая цифра в последовательности. Это делается путем указания количества цифр справа от цифры, где встречается следующая цифра в последовательности. При необходимости, подсчет оборачивается от самой правой цифры до самой левой.
• Самая левая цифра в номере является первой цифрой в последовательности, и последовательность должна вернуться к этой цифре после того, как все цифры в номере были использованы ровно один раз.
• Никакая цифра не появится более одного раза в номере.

Проверка на повторяющиеся цифры не является проблемой, но я не могу придумать, как найти способ «обойти» часть. Я ищу больше предложений / псевдокода, чем реальный c ++.

Answer 1

если вы преобразуете целое число в строку, это не должно быть сложным: все, что вам нужно, это оператор [] (который предоставляет класс std :: string) и массив логических значений для записи, элемент которого уже проверен :

string value = input_integer;
vector<bool> checked;

int index = value[0];
checked[0] = true;
bool done = false;
while (!done) {
   index = get_wrapped_index(value, index);
   if (!checked[index])
      checked[index] = true;
   else 
      return false; // not a roundaround

   if allTrue(checked) && index == 0
      done = true;
}
return true;

Вы должны кодировать get_wrapped_index (строка s, индекс i), который должен возвращать целое число, указанное в s [i], с учетом правильного переноса стоимости, указанного в проблеме.

Answer 2

У вас есть 4 правила, поэтому просто напишите код, чтобы проверить каждое правило.

• Число состоит из N цифр.Определите, что такое Н.Может быть сделано путем преобразования в строку или вектор для каждой цифры.Возможно, вам придется использовать деление на 10 и mod (%) 10 несколько раз.

• Метод перехода от одной цифры к другой.Поэтому, если вы находитесь в позиции с цифрой x со значением y, вы переходите к x + y mod N, то есть (x + y)% N.Конечно, первая позиция считается позицией 0.

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

12 - ошибка.Потому что, хотя после 2 итераций вы не достигнете индекса 0, но вернетесь к индексу 1 (2 возвращает вас от индекса 1 к индексу 1)

11 - ошибка, потому что вы видите еще одну 1, когда у вас не было всех вашихитераций пока нет.

123 - ошибка, потому что вы возвращаетесь к 1 итерации слишком раноВам не нужно знать, что вы не видели 3 или что вы вернулись к индексу 0, просто вы слишком рано увидели еще 1.

285 работает.Вы видите 2, затем 5, затем 8, затем 2. Вы находитесь в индексе 0 и у вас было 3 итерации.

Вам необходимо сохранить набор увиденных цифр.vector немного противоречив, так что вы можете использовать std :: bitset или даже bool [10] подойдет для этого примера, или vector.Вы также можете использовать std :: set, последний случай которого позволит вам проверить его размер, чтобы увидеть количество итераций.