Задача
Решение
Нечто подобное было в задаче про числительные. Мы имеем некое пространство с интересными характеристиками, и нужно уметь отображать любой линейный порядковый номер на порядковый номер в этом пространстве.
Разделим его на сегменты, где у каждого сегмента своя длина:
Структура типа Range описывает сегмент: позиция начала, длина (количество элементов) и размер одного элемента.
Сначала идёт сегмент от 0 до 9 длиной 10 элементов с размером 1. Затем сегмент от 10 до 99 длиной 90 элементов с размером 2. И так далее.
Далее надо выяснить, в какой сегмент попадает интересующая нас позиция цифры.
Для этого из позиции последовательно вычитаем длины сегментов. Эффективная длина сегмента это количество элементов умножить на размер элемента.
Когда вычесть из позиции длину сегмента уже нельзя, позиция представляет собой остаток внутри сегмента.
Каждое число внутри сегмента занимает сколько-то цифр, поэтому чтобы узнать, в какое число мы попали, делим остаток нашей позиции на размер числа (stride). И прибавляем стартовое число сегмента.
После этого остаётся понять, в какую цифру внутри числа мы попали. Рассмотрим пример, когда размер числа равен 3. Остаток от деления позиции на 3 даст нам следующую информацию:
- Если остаток 0, мы попали на начало числа (самую старшую цифру)
- Если остаток 1, мы попали на вторую цифру
- Если остаток 2, мы попали на третью цифру
Следовательно, если остаток 0, мы должны два раза разделить число на 10, чтобы получить старшую цифру. Если остаток 1, разделить на 10 один раз, и если остаток 2, то не делить вообще.
Следовательно, счётчик для деления rem получаем как размер числа, минус остаток от деления на размер, минус 1.
Ну и программа:
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач
