как найти n-ую цифру, например 1491625 ....?

Question

Давайте объединим квадраты чисел, которые начинаются с 1. Итак, что за n-ая цифра в этой строке?

Например, десятая цифра - 4.

1 4 9 16 25 36 49 64 81

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

Answer 1

Вы можете перечислить, сколько 1-значных, 2-значных, 3-значных и т. Д. Чисел существует в этой последовательности, взяв квадратные корни из степеней 10. Это позволит вам определить, к какому числу относится n -я цифра. Оттуда она должна быть довольно тривиальной.

Это должно быть O (log n) сложность.

Answer 2

ceil (log ₁₀ (x + 1)) даст вам количество цифр в числе.Перебирайте квадраты, сохраняя счет общей длины, и как только вы достигли или превысили целевую длину n, вы знаете, что вам нужна m-тая цифра последнего числа для некоторого m (легко понять).Получите m-ую цифру этого числа, разделив ее на 10 ^m-1 , чем взяв последнюю цифру с модом 10.

Все-в-целом, постоянные пробелы и O (n)во время выполнения.

Answer 3

Для решения этой проблемы я использовал Python Generators . Мое решение в Python:

def _countup(n):
    while True:
        yield n
        n += 1

def get_nth_element(n):
    i = 0 # Initialized just to keep track of iterations.
    final_string = ''
    cu_generator = _countup(0)

    while True:
        num = cu_generator.next()
        final_string += str(num * num)
        if len(final_string) > n:
            print "Number of iterations %s" % i
            return final_string[n]
        i += 1

RUN:

>>> get_nth_element(1000)
Number of iterations 229
'2'

>>> get_nth_element(10000)
Number of iterations 1637
'7'

Answer 4

Ленивые бесконечные списки в Haskell делают это тривиальным, чтобы выразить наивно.

ghci> concat [show $ i*i | i <- [1..]] !! 9
'4'

Answer 5

Это прямой порт ответа Haskell от ephemient на Scala

Iterator.from(1).flatMap(x=>(x*x).toString.iterator).drop(9).next

возвращает 4

O (n)

• Iterator.from(1) создаетбесконечный итератор, который считает 1,2,3,4,.....
• Затем (x*x).toString вычисляет квадраты каждого из них и превращает их в строки.
• flatMap( ... .iterator) объединяет их, чтобы стать бесконечным итератором символов из рассматриваемой последовательности
• drop(9) удаляет первые 9 элементов (индексы от 0 до 8) из итератора и дает намновый итератор, ожидающий с индексом 9
• next, дает нам этот единственный символ.

Answer 6

Почему бы вам не повторить цикл, взяв каждое число, возводя в квадрат и увеличивая счет от 1, проверяя на каждом шаге, достиг ли вы n? Вам не нужно отслеживать весь номер. Это простое симуляционное упражнение. Боюсь, я не могу определить образец или формулу для этого.