Статья Автор: Лебедев Дмитрий

TUZ_4-07 Слово Чампернауна

TUZ_4-07 Слово Чампернауна

TUZ_4-07 Слово Чампернауна
4.7. Слово Чампернауна
Слово Чампернауна – это длинная строка, не содержащая разделителей-запятых.
Оно состоит из последовательности чисел начиная с единицы и увеличивающихся на единицу.
Цель этой задачи – вернуть цифру, соответствующую данному индексу.
Важно отметить, что эту задачу невозможно решить с помощью обычного метода, такого как list.index,
из- за ограничений во времени и пространстве.
Для решения данной задачи следует написать функцию, которая принимает положительное целое число n,
представляющее желаемый индекс, и возвращает соответствующую цифру.
Например, в седьмой позиции (счет начинается с 0) в последовательности «1, 2, 3, 4, 5, 6, 7, 8, 9, 10, …» находится цифра 8.
В табл. 4.7 показаны ожидаемые результаты для некоторых входных данных.
Таблица 4.7. Некоторые ожидаемые результаты для задачи получения слова Чампернауна
X Ожидаемый результат
12**214 9
7 8
717897987691852588770047 2
3111111198765431001 1
При решении задачи количество цифр в каждой последовательности определяется по следующей таблице.
Номер последовательности Диапазон Число слов Число цифр в каждой последовательности
1 1-9 9 9
2 10-99 90 180
3 100-999 900 2700
4 1000-9999 9000 36000

Алгоритм
1. Принимается один входной параметр: n (номер искомой цифры n-я цифра).
2. Инициализируются переменные d (цифры), p_i (передаваемые ин- дексы),
    p_n (передаваемые числа) и w (количество слов) значениями 0 и 9 соответственно.
3. Пока n больше или равно p_i + w * (d + 1), увеличивать d на 1,
    обновлять p_i до p_i + w * (d + 1), p_n до p_n + w и w до w * 10.
4. Вычисляется индекс p как (n – p_i)//(d + 1).
5. Вычисляется искомое число как p_n + p + 1.
6. Полученное число преобразуется в строку, и выбирается символ по индексу (n – p_i) % (d + 1).
7. Возвращается n-я цифра как результат работы алгоритма.


Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать