본문 바로가기

수열

 (5)
제곱근 근사 뉴튼방법 def isqrt(n): x = n y = (x+1)/2 while y < x: x = y y = (x+n/x)/2 return x 루트 n 을 구하는 뉴튼의 방법인데. 어떻게 구해지는 건가? ---f(x) = x, g(x) = n/x 두 그래프는 (sqrt(n), sqrt(n)) 에서 교차한다. 하나는 단조증가, 하나는 단조감소함수이다.위 코드에서는 x_(k+1) = ( f(x_k) + g(x_k) )/2 점화식으로 x_k 수열을 만들어 나간다. 그래프에서는 삼각주 모양을 점점 줄여 나가면서 교차점에 다다르게 되는 형상이다. f(x), g(x) 가 (sqrt(n), sqrt(n)) 에서 교차하는 단조증가/감수 함수이기만 하면 되나? 위 파란색 부분 뻘생각이니까 혹시 검색을 통해 들어오신 분들은 크게 신..
[JAVA] 원탁에서 n 칸씩 건너 빼와서 만들어진 수열 다음 지식에서 재미있어 보이는 문제가 있어서 한번 짜 봤다. 문제는 다음과 같다. 2010년 4월 1일 추가 : 여기에 좀 더 재미있는 분석과 코드가 있다. Josephus Problem 이란 이름이 붙은 것 같다. http://k.daum.net/qna/view.html?qid=44T6T 친구가 질문했는데 너무 어려워서 지인들의 설명을 듣고자 질문합니다. 1부터 30까지의 수를 가진 사람이 순서대로 원 주위로 앉아있을 때, 먼저, 9번째 앉아있는 사람을 쫓아내고, 그로부터 9칸을 더 간 18번째 사람을 쫓아낸다. 마찬가지로 9칸을 더 간 27번 사람을 쫓아내고, 그 다음, 또 9칸을 더 간 사람(6번)을 쫓아낸다. 그리 고 나서 9칸을 갈 때에는 9번째 앉았던 쫓겨난 사람은 없는 것으로 치고 9칸 뒤,..
생성함수 수열을 점화식으로 표현할 수도 있지만, 생성함수(generating function)라는 다항식을 이용해서 표현하는 방법도 있다고 한다. 뭔가 싶었다. 그런데, 좀 생각을 해 보니, 소수표현과 분수에 비유해서 설명할 수 있지 않을까 하는 생각이 들었다. 그러니까, 3/7 이라는 소수는 0부터 9까지의 수만 갖는 무한수열을 표현한다. 0.428571428571... 을 4, 2, 8, 5, 7, 1... 이렇게 이어지는 무한수열을 나타내는 것이라고 보자는 거다. 그럼, 좀 복잡한 점화식 대신에, 3/7 이라는 간단한 수로 무한한 수열을 표현할 수 있다. 그런데, 정수의 소수표현은 0부터 9까지의 수만 수열의 한 항으로 가질 수 있다는 한계가 있다. 이건 진법을 바꾸면 무한하게 늘어날 수 있겠지만, 아무리 ..
[Euler Project 101] 수열 다항식으로 근사하기 #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=101 coff = [ 0 ] * 11 def OP(ord, n): if ord == 0: return coff[0] r = OP(ord-1, n) term = coff[ord] for j in range(1, ord+1): term*=(n-j) for j in range(1, ord+1): term/= j r += term return r def f(n): return 1 - n + n**2 - n**3 + n**4 - n**5 + n**6 - n**7 + n**8 - n**9 + n**10 a = [ f(n) for n in range(1, 12) ] coff[0..
[Py] 신이 보여준 정리 신이 보여준 정리를 보고 재미있을 것 같아서 짜봤다. 답을 대충 짐작하고 나서는 예쁘게 n + 1 = sqrt(1 + (n) sqrt(1 + (n+1) sqrt(..))) 이 n x (n + 1) = n x sqrt(1 + (n+1) sqrt(...)) 으로 정리되는 걸 알았다. #!/usr/bin/env python # _____________________________ # / ___________________ # / 1 + 2 / ___________ = ? # |/ |/ 1 + 3 |/ ..... # # import math def get_prev(x, n): return math.sqrt(1 + n*x) def eval_first(x0, n): #print "" #print "=========..

티스토리툴바