숫자에서 n'th 숫자를 찾는 방법 1491625 ....?

Question

1로 시작하는 숫자의 제곱을 연결합시다.이 문자열에서 n 번째 숫자는 무엇입니까?

예를 들어, 10 자리 그것은 광산에 보통의 마음을 와서 그냥 평범한 질문 4.

1 4 9 16 25 36 49 64 81 

입니다. 어떻게하면 오늘 밤에 잘 수 있을까요? 어떤 알고리즘을 반복하지 않고?

Answer 1

당신은 힘-의-10의 제곱근을 취함으로써이 순서에 얼마나 많은 1 자리, 2 자리 등 3 자리 숫자를 열거 작업 할 수 있습니다. 이렇게하면 n 번째 자리가 어느 숫자인지 파악할 수 있습니다. 거기에서 꽤 사소한 것이어야합니다.

이것은 O (log n) 복잡해야합니다.

Answer 2

하스켈에있는 게으른 무한한 목록은 이처럼 사소한 표현을하지 않고 자연스럽게 표현합니다.

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

Answer 3

왜 반복하지 않고 각 숫자를 취하고 제곱하고 n에 도달하면 각 단계마다 1 단위 검사에서 카운트를 증가 시키시겠습니까? 전체 번호를 추적 할 필요가 없습니다. 간단한 시뮬레이션 연습입니다. 나는 두려워서, 나는 이것을위한 패턴이나 공식을 식별 할 수 없다.

Answer 4

ceil (log (x + 1))은 숫자의 자릿수를 제공합니다. 사각형을 반복하여 전체 길이의 수를 유지하고 목표 길이 n에 도달하거나 초과하면 일부 m에 대해 마지막 숫자의 m 번째 숫자가 필요하다는 것을 알게됩니다 (쉽게 해결할 수 있음). 이 숫자의 m 번째 숫자를 mod 10으로 마지막 숫자를 취하는 것보다 ^m-1으로 나눈 값을 얻습니다.

올인원, 일정한 공간 오버 헤드 및 O (n) 런타임.

Answer 5

이 스칼라

에 ephemient의 하스켈 응답의 직접적인 포트

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

반환

O (n)이

• Iterator.from(1)이 1,2,3,4,....를 계산 무한 반복자를 생성 4이다.
• 그런 다음 (x*x).toString은 각각의 제곱을 계산하여 문자열로 변환합니다.
• flatMap(... .iterator)
는 이러한
• drop(9) 반복자에서 첫 번째 9 개 요소 (인덱스 8-0)을 제거하고 우리에게 인덱스 9
• 에서 기다리고 새로운 반복자를 제공합니다 질문에 일련의 문자의 무한 반복자가 될 연결합니다 next는 그 단일 문자를 제공합니다.

Answer 6

이 문제를 해결하기 위해 Python Generators을 사용했습니다.파이썬에서 내 솔루션 :

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'