본문 바로가기

점화식

 (4)
파이썬 자리수곱의합 문제 P(n)은 n을 십진수로 표시했을 때 0이 아닌 각 자리수의 곱으로 정의한다. 다음 값을 구하라. P(1) + P(2) + P(3) + ... + P(999999) 우선 무식한 방법 #!/usr/bin/python ########################################################## # ZiffernProdukte # --------------------------------------------------------- # # --------------------------------------------------------- # Mit P(n) bezeichnen wir das Produkt aller Ziffern # 1,2,3,4,5,6,7,8,9 in d..
제곱근 근사 뉴튼방법 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)) 에서 교차하는 단조증가/감수 함수이기만 하면 되나? 위 파란색 부분 뻘생각이니까 혹시 검색을 통해 들어오신 분들은 크게 신..
생성함수 수열을 점화식으로 표현할 수도 있지만, 생성함수(generating function)라는 다항식을 이용해서 표현하는 방법도 있다고 한다. 뭔가 싶었다. 그런데, 좀 생각을 해 보니, 소수표현과 분수에 비유해서 설명할 수 있지 않을까 하는 생각이 들었다. 그러니까, 3/7 이라는 소수는 0부터 9까지의 수만 갖는 무한수열을 표현한다. 0.428571428571... 을 4, 2, 8, 5, 7, 1... 이렇게 이어지는 무한수열을 나타내는 것이라고 보자는 거다. 그럼, 좀 복잡한 점화식 대신에, 3/7 이라는 간단한 수로 무한한 수열을 표현할 수 있다. 그런데, 정수의 소수표현은 0부터 9까지의 수만 수열의 한 항으로 가질 수 있다는 한계가 있다. 이건 진법을 바꾸면 무한하게 늘어날 수 있겠지만, 아무리 ..
[Euler Project 078] 분할함수 (Partition Function) 76, 77번을 풀었던 방법으로 풀었는데, 끝까지 계산하지 못하고 오버플로우가 났다. 삼각형 형태로 메모리가 늘어나서 13000 까지 찍고 죽는 것이었다. 그래서 위키백과의 점화식을 이용하여 푸는 코드를 짜서 풀었다. 점화식은 2차원인 아닌 1차원으로 기억하고 있으면 되서 답을 내 줬다. 죽는 코드와 죽는 모습 #!/usr/bin/env python # euler 78 P = [] n = 0 P.append([]) P[n].append(0) # P[0][0] n = 1 P.append([]) P[n].append(0) # P[1][0] P[n].append(1) # P[1][1] n = 2 while 1: cnt = 0 P.append([]) for i in range(n+1): if i == 0: cn..

티스토리툴바